SphinxBase 0.6
|
00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */ 00002 /* ==================================================================== 00003 * Copyright (c) 1999-2004 Carnegie Mellon University. All rights 00004 * reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 00010 * 1. Redistributions of source code must retain the above copyright 00011 * notice, this list of conditions and the following disclaimer. 00012 * 00013 * 2. Redistributions in binary form must reproduce the above copyright 00014 * notice, this list of conditions and the following disclaimer in 00015 * the documentation and/or other materials provided with the 00016 * distribution. 00017 * 00018 * This work was supported in part by funding from the Defense Advanced 00019 * Research Projects Agency and the National Science Foundation of the 00020 * United States of America, and the CMU Sphinx Speech Consortium. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 00023 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 00024 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 00025 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY 00026 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00027 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00028 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00029 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00030 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00032 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00033 * 00034 * ==================================================================== 00035 * 00036 */ 00037 /* 00038 * heap.c -- Generic heap structure for inserting in any and popping in sorted 00039 * order. 00040 * 00041 * ********************************************** 00042 * CMU ARPA Speech Project 00043 * 00044 * Copyright (c) 1999 Carnegie Mellon University. 00045 * ALL RIGHTS RESERVED. 00046 * ********************************************** 00047 * 00048 * HISTORY 00049 * $Log: heap.c,v $ 00050 * Revision 1.4 2005/06/22 03:05:49 arthchan2003 00051 * 1, Fixed doxygen documentation, 2, Add keyword. 00052 * 00053 * Revision 1.3 2005/03/30 01:22:48 archan 00054 * Fixed mistakes in last updates. Add 00055 * 00056 * 00057 * 05-Mar-99 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University 00058 * Fixed bug in heap_destroy() (in while loop exit condition). 00059 * 00060 * 23-Dec-96 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University 00061 * Started. 00062 */ 00063 00064 00065 #include <stdio.h> 00066 #include <stdlib.h> 00067 #include <string.h> 00068 #include <assert.h> 00069 00070 #include "sphinxbase/heap.h" 00071 #include "sphinxbase/err.h" 00072 #include "sphinxbase/ckd_alloc.h" 00073 00077 typedef struct heapnode_s { 00078 void *data; 00079 int32 val; 00081 int32 nl, nr; 00082 struct heapnode_s *l; 00083 struct heapnode_s *r; 00084 } heapnode_t; 00085 00089 struct heap_s { 00090 heapnode_t *top; 00091 }; 00092 00093 00094 #if 0 00095 static void 00096 heap_dump(heapnode_t * top, int32 level) 00097 { 00098 int32 i; 00099 00100 if (!top) 00101 return; 00102 00103 for (i = 0; i < level; i++) 00104 printf(" "); 00105 /* print top info */ 00106 heap_dump(top->l, level + 1); 00107 heap_dump(top->r, level + 1); 00108 } 00109 #endif 00110 00111 00112 heap_t * 00113 heap_new(void) 00114 { 00115 heap_t *h = ckd_calloc(1, sizeof(*h)); 00116 return h; 00117 } 00118 00119 00120 static heapnode_t * 00121 subheap_insert(heapnode_t * root, void *data, int32 val) 00122 { 00123 heapnode_t *h; 00124 void *tmpdata; 00125 int32 tmpval; 00126 00127 if (!root) { 00128 h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t)); 00129 h->data = data; 00130 h->val = val; 00131 h->l = h->r = NULL; 00132 h->nl = h->nr = 0; 00133 return h; 00134 } 00135 00136 /* Root already exists; if new value is less, replace root node */ 00137 if (root->val > val) { 00138 tmpdata = root->data; 00139 tmpval = root->val; 00140 root->data = data; 00141 root->val = val; 00142 data = tmpdata; 00143 val = tmpval; 00144 } 00145 00146 /* Insert new or old (replaced) node in right or left subtree; keep them balanced */ 00147 if (root->nl > root->nr) { 00148 root->r = subheap_insert(root->r, data, val); 00149 root->nr++; 00150 } 00151 else { 00152 root->l = subheap_insert(root->l, data, val); 00153 root->nl++; 00154 } 00155 00156 return root; 00157 } 00158 00159 00160 int 00161 heap_insert(heap_t *heap, void *data, int32 val) 00162 { 00163 heap->top = subheap_insert(heap->top, data, val); 00164 return 0; 00165 } 00166 00167 00168 static heapnode_t * 00169 subheap_pop(heapnode_t * root) 00170 { 00171 heapnode_t *l, *r; 00172 00173 /* Propagate best value from below into root, if any */ 00174 l = root->l; 00175 r = root->r; 00176 00177 if (!l) { 00178 if (!r) { 00179 ckd_free((char *) root); 00180 return NULL; 00181 } 00182 else { 00183 root->data = r->data; 00184 root->val = r->val; 00185 root->r = subheap_pop(r); 00186 root->nr--; 00187 } 00188 } 00189 else { 00190 if ((!r) || (l->val < r->val)) { 00191 root->data = l->data; 00192 root->val = l->val; 00193 root->l = subheap_pop(l); 00194 root->nl--; 00195 } 00196 else { 00197 root->data = r->data; 00198 root->val = r->val; 00199 root->r = subheap_pop(r); 00200 root->nr--; 00201 } 00202 } 00203 00204 return root; 00205 } 00206 00207 00208 int 00209 heap_pop(heap_t *heap, void **data, int32 * val) 00210 { 00211 if (heap->top == NULL) 00212 return 0; 00213 *data = heap->top->data; 00214 *val = heap->top->val; 00215 heap->top = subheap_pop(heap->top); 00216 return 1; 00217 } 00218 00219 00220 int 00221 heap_top(heap_t *heap, void **data, int32 * val) 00222 { 00223 if (heap->top == NULL) 00224 return 0; 00225 *data = heap->top->data; 00226 *val = heap->top->val; 00227 return 1; 00228 } 00229 00230 static int 00231 heap_remove_one(heap_t *heap, heapnode_t *top, void *data) 00232 { 00233 if (top == NULL) 00234 return -1; 00235 else if (top->data == data) { 00236 assert(top == heap->top); 00237 heap->top = subheap_pop(heap->top); 00238 return 0; 00239 } 00240 if (top->l) { 00241 if (top->l->data == data) { 00242 top->l = subheap_pop(top->l); 00243 --top->nl; 00244 return 0; 00245 } 00246 else if (heap_remove_one(heap, top->l, data) == 0) { 00247 --top->nl; 00248 return 0; 00249 } 00250 } 00251 if (top->r) { 00252 if (top->r->data == data) { 00253 top->r = subheap_pop(top->r); 00254 --top->nr; 00255 return 0; 00256 } 00257 else if (heap_remove_one(heap, top->r, data) == 0) { 00258 --top->nr; 00259 return 0; 00260 } 00261 } 00262 return -1; 00263 } 00264 00265 int 00266 heap_remove(heap_t *heap, void *data) 00267 { 00268 return heap_remove_one(heap, heap->top, data); 00269 } 00270 00271 00272 size_t 00273 heap_size(heap_t *heap) 00274 { 00275 if (heap->top == NULL) 00276 return 0; 00277 return heap->top->nl + heap->top->nr + 1; 00278 } 00279 00280 int 00281 heap_destroy(heap_t *heap) 00282 { 00283 void *data; 00284 int32 val; 00285 00286 /* Empty the heap and free it */ 00287 while (heap_pop(heap, &data, &val) > 0) 00288 ; 00289 ckd_free(heap); 00290 00291 return 0; 00292 }