SphinxBase  5prealpha
heap.c
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3  * Copyright (c) 1999-2004 Carnegie Mellon University. All rights
4  * reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  *
18  * This work was supported in part by funding from the Defense Advanced
19  * Research Projects Agency and the National Science Foundation of the
20  * United States of America, and the CMU Sphinx Speech Consortium.
21  *
22  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
23  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
26  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33  *
34  * ====================================================================
35  *
36  */
37 /*
38  * heap.c -- Generic heap structure for inserting in any and popping in sorted
39  * order.
40  *
41  * **********************************************
42  * CMU ARPA Speech Project
43  *
44  * Copyright (c) 1999 Carnegie Mellon University.
45  * ALL RIGHTS RESERVED.
46  * **********************************************
47  *
48  * HISTORY
49  * $Log: heap.c,v $
50  * Revision 1.4 2005/06/22 03:05:49 arthchan2003
51  * 1, Fixed doxygen documentation, 2, Add keyword.
52  *
53  * Revision 1.3 2005/03/30 01:22:48 archan
54  * Fixed mistakes in last updates. Add
55  *
56  *
57  * 05-Mar-99 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
58  * Fixed bug in heap_destroy() (in while loop exit condition).
59  *
60  * 23-Dec-96 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University
61  * Started.
62  */
63 
64 
65 #include <stdio.h>
66 #include <stdlib.h>
67 #include <string.h>
68 #include <assert.h>
69 
70 #include "sphinxbase/heap.h"
71 #include "sphinxbase/err.h"
72 #include "sphinxbase/ckd_alloc.h"
73 
77 typedef struct heapnode_s {
78  void *data;
79  int32 val;
81  int32 nl, nr;
82  struct heapnode_s *l;
83  struct heapnode_s *r;
84 } heapnode_t;
85 
89 struct heap_s {
90  heapnode_t *top;
91 };
92 
93 
94 #if 0
95 static void
96 heap_dump(heapnode_t * top, int32 level)
97 {
98  int32 i;
99 
100  if (!top)
101  return;
102 
103  for (i = 0; i < level; i++)
104  printf(" ");
105  /* print top info */
106  heap_dump(top->l, level + 1);
107  heap_dump(top->r, level + 1);
108 }
109 #endif
110 
111 
112 heap_t *
113 heap_new(void)
114 {
115  heap_t *h = ckd_calloc(1, sizeof(*h));
116  return h;
117 }
118 
119 
120 static heapnode_t *
121 subheap_insert(heapnode_t * root, void *data, int32 val)
122 {
123  heapnode_t *h;
124  void *tmpdata;
125  int32 tmpval;
126 
127  if (!root) {
128  h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
129  h->data = data;
130  h->val = val;
131  h->l = h->r = NULL;
132  h->nl = h->nr = 0;
133  return h;
134  }
135 
136  /* Root already exists; if new value is less, replace root node */
137  if (root->val > val) {
138  tmpdata = root->data;
139  tmpval = root->val;
140  root->data = data;
141  root->val = val;
142  data = tmpdata;
143  val = tmpval;
144  }
145 
146  /* Insert new or old (replaced) node in right or left subtree; keep them balanced */
147  if (root->nl > root->nr) {
148  root->r = subheap_insert(root->r, data, val);
149  root->nr++;
150  }
151  else {
152  root->l = subheap_insert(root->l, data, val);
153  root->nl++;
154  }
155 
156  return root;
157 }
158 
159 
160 int
161 heap_insert(heap_t *heap, void *data, int32 val)
162 {
163  heap->top = subheap_insert(heap->top, data, val);
164  return 0;
165 }
166 
167 
168 static heapnode_t *
169 subheap_pop(heapnode_t * root)
170 {
171  heapnode_t *l, *r;
172 
173  /* Propagate best value from below into root, if any */
174  l = root->l;
175  r = root->r;
176 
177  if (!l) {
178  if (!r) {
179  ckd_free((char *) root);
180  return NULL;
181  }
182  else {
183  root->data = r->data;
184  root->val = r->val;
185  root->r = subheap_pop(r);
186  root->nr--;
187  }
188  }
189  else {
190  if ((!r) || (l->val < r->val)) {
191  root->data = l->data;
192  root->val = l->val;
193  root->l = subheap_pop(l);
194  root->nl--;
195  }
196  else {
197  root->data = r->data;
198  root->val = r->val;
199  root->r = subheap_pop(r);
200  root->nr--;
201  }
202  }
203 
204  return root;
205 }
206 
207 
208 int
209 heap_pop(heap_t *heap, void **data, int32 * val)
210 {
211  if (heap->top == NULL)
212  return 0;
213  *data = heap->top->data;
214  *val = heap->top->val;
215  heap->top = subheap_pop(heap->top);
216  return 1;
217 }
218 
219 
220 int
221 heap_top(heap_t *heap, void **data, int32 * val)
222 {
223  if (heap->top == NULL)
224  return 0;
225  *data = heap->top->data;
226  *val = heap->top->val;
227  return 1;
228 }
229 
230 static int
231 heap_remove_one(heap_t *heap, heapnode_t *top, void *data)
232 {
233  if (top == NULL)
234  return -1;
235  else if (top->data == data) {
236  assert(top == heap->top);
237  heap->top = subheap_pop(heap->top);
238  return 0;
239  }
240  if (top->l) {
241  if (top->l->data == data) {
242  top->l = subheap_pop(top->l);
243  --top->nl;
244  return 0;
245  }
246  else if (heap_remove_one(heap, top->l, data) == 0) {
247  --top->nl;
248  return 0;
249  }
250  }
251  if (top->r) {
252  if (top->r->data == data) {
253  top->r = subheap_pop(top->r);
254  --top->nr;
255  return 0;
256  }
257  else if (heap_remove_one(heap, top->r, data) == 0) {
258  --top->nr;
259  return 0;
260  }
261  }
262  return -1;
263 }
264 
265 int
266 heap_remove(heap_t *heap, void *data)
267 {
268  return heap_remove_one(heap, heap->top, data);
269 }
270 
271 
272 size_t
274 {
275  if (heap->top == NULL)
276  return 0;
277  return heap->top->nl + heap->top->nr + 1;
278 }
279 
280 int
282 {
283  void *data;
284  int32 val;
285 
286  /* Empty the heap and free it */
287  while (heap_pop(heap, &data, &val) > 0)
288  ;
289  ckd_free(heap);
290 
291  return 0;
292 }
void * data
Application data at this node.
Definition: heap.c:78
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
struct heapnode_s * l
Root of left descendant heap.
Definition: heap.c:82
SPHINXBASE_EXPORT int heap_destroy(heap_t *heap)
Destroy the given heap; free the heap nodes.
Definition: heap.c:281
Sphinx&#39;s memory allocation/deallocation routines.
SPHINXBASE_EXPORT heap_t * heap_new(void)
Allocate a new heap and return handle to it.
Definition: heap.c:113
SPHINXBASE_EXPORT int heap_remove(heap_t *heap, void *data)
Remove an item from the heap.
Definition: heap.c:266
One node on the heap.
Definition: heap.c:77
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
SPHINXBASE_EXPORT int heap_insert(heap_t *heap, void *data, int32 val)
Insert a new item into the given heap.
Definition: heap.c:161
SPHINXBASE_EXPORT int heap_pop(heap_t *heap, void **data, int32 *val)
Like heap_top but also pop the top item off the heap.
Definition: heap.c:209
Heap Implementation.
struct heapnode_s * r
Root of right descendant heap.
Definition: heap.c:83
SPHINXBASE_EXPORT size_t heap_size(heap_t *heap)
Return the number of items in the heap.
Definition: heap.c:273
Implementation of logging routines.
int32 nr
left/right descendants of this node (for balancing heap)
Definition: heap.c:81
SPHINXBASE_EXPORT int heap_top(heap_t *heap, void **data, int32 *val)
Return the topmost item in the heap.
Definition: heap.c:221
int32 val
Associated with above application data; according to which heap is sorted (in ascending order) ...
Definition: heap.c:79
Internal heap data structure.
Definition: heap.c:89