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"
73
77typedef struct heapnode_s {
78 void *data;
79 int32 val;
81 int32 nl, nr;
82 struct heapnode_s *l;
83 struct heapnode_s *r;
85
89struct heap_s {
90 heapnode_t *top;
91};
92
93
94#if 0
95static void
96heap_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
112heap_t *
114{
115 heap_t *h = ckd_calloc(1, sizeof(*h));
116 return h;
117}
118
119
120static heapnode_t *
121subheap_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
160int
161heap_insert(heap_t *heap, void *data, int32 val)
162{
163 heap->top = subheap_insert(heap->top, data, val);
164 return 0;
165}
166
167
168static heapnode_t *
169subheap_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
208int
209heap_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
220int
221heap_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
230static int
231heap_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
265int
266heap_remove(heap_t *heap, void *data)
267{
268 return heap_remove_one(heap, heap->top, data);
269}
270
271
272size_t
274{
275 if (heap->top == NULL)
276 return 0;
277 return heap->top->nl + heap->top->nr + 1;
278}
279
280int
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}
Sphinx's memory allocation/deallocation routines.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
Implementation of logging routines.
Heap Implementation.
SPHINXBASE_EXPORT size_t heap_size(heap_t *heap)
Return the number of items in the heap.
Definition: heap.c:273
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
SPHINXBASE_EXPORT heap_t * heap_new(void)
Allocate a new heap and return handle to it.
Definition: heap.c:113
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_remove(heap_t *heap, void *data)
Remove an item from the heap.
Definition: heap.c:266
SPHINXBASE_EXPORT int heap_destroy(heap_t *heap)
Destroy the given heap; free the heap nodes.
Definition: heap.c:281
SPHINXBASE_EXPORT int heap_top(heap_t *heap, void **data, int32 *val)
Return the topmost item in the heap.
Definition: heap.c:221
Internal heap data structure.
Definition: heap.c:89
One node on the heap.
Definition: heap.c:77
int32 val
Associated with above application data; according to which heap is sorted (in ascending order)
Definition: heap.c:79
void * data
Application data at this node.
Definition: heap.c:78
struct heapnode_s * r
Root of right descendant heap.
Definition: heap.c:83
int32 nr
left/right descendants of this node (for balancing heap)
Definition: heap.c:81
struct heapnode_s * l
Root of left descendant heap.
Definition: heap.c:82