File: heap.c

package info (click to toggle)
dspam 3.10.1+dfsg-11
  • links: PTS, VCS
  • area: main
  • in suites: wheezy
  • size: 6,656 kB
  • sloc: ansic: 26,034; sh: 12,546; perl: 5,469; makefile: 690; sql: 379
file content (151 lines) | stat: -rw-r--r-- 3,676 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/* $Id: heap.c,v 1.94 2011/06/28 00:13:48 sbajic Exp $ */

/*
 DSPAM
 COPYRIGHT (C) 2002-2011 DSPAM PROJECT

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as
 published by the Free Software Foundation, either version 3 of the
 License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

/*
 * heap.c - fast heap-based sorting algorithm with maximum window size
 *
 * DESCRIPTION
 *   This sorting algorithm is designed to perform very efficiently when there 
 *   is a small window-size of 'peak' values, such as the 15 bayes slots.
 */

#include <stdlib.h>
#include <math.h>
#include "heap.h"

ds_heap_t
ds_heap_create(int size, int type)
{
  ds_heap_t h;

  h = calloc(1, sizeof(struct _ds_heap));
  h->size = size;
  h->type = type;
  return h;
}

void
ds_heap_destroy(ds_heap_t h)
{
  if (h) {
    ds_heap_element_t node, next;
    node = h->root;
    while(node) {
      next = node->next;
      free(node);
      node = next;
    }
    free(h);
  }
  return;
}

ds_heap_element_t
ds_heap_element_create (double probability, 
                  unsigned long long token, 
                  unsigned long frequency,
                  int complexity)
{
  ds_heap_element_t element = calloc(1, sizeof(struct _ds_heap_element));

  if (!element)
    return NULL;

  element->delta       = fabs(0.5-probability);
  element->probability = probability;
  element->token       = token;
  element->frequency   = frequency;
  element->complexity  = complexity;

  return element;
}

ds_heap_element_t
ds_heap_insert (ds_heap_t h,
             double probability,
             unsigned long long token,
             unsigned long frequency,
             int complexity)
{
  ds_heap_element_t current = NULL;
  ds_heap_element_t insert = NULL;
  ds_heap_element_t node;
  float delta = fabs(0.5-probability);

  current = h->root;

  /* Determine if and where we should insert this item */
  if (h->type == HP_DELTA) {
    while(current) {
      if (delta > current->delta) 
        insert = current;
      else if (delta == current->delta) {
        if (frequency > current->frequency)
          insert = current;
        else if (frequency == current->frequency)
          if (complexity >= current->complexity)
            insert = current;
      }
      if (!insert)
        break;
      else
        current = current->next;
    }
  } else {
   while(current) {
      if (probability > current->probability)
        insert = current;
      if (!insert)
        break;
      else
        current = current->next;
    }
  }

  if (insert != NULL) {

    /* Insert item, throw out new least significant item if necessary */
    node = ds_heap_element_create( probability, token, frequency, complexity);
    node->next = insert->next;
    insert->next = node;
    h->items++;
    if (h->items > h->size) {
      node = h->root;
      h->root = node->next;
      free(node);
      h->items--;
    }
  } else {
    
    /* Item is least significant; throw it out or grow the heap */
    if (h->items == h->size)
      return NULL;

    /* Grow heap */
    node = ds_heap_element_create(probability, token, frequency, complexity);
    node->next = h->root;
    h->root = node;
    h->items++;
  }

  return node;
}