• Main Page
  • Related Pages
  • Data Structures
  • Files
  • File List
  • Globals

src/libsphinxbase/util/heap.c

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 "heap.h"
00071 #include "ckd_alloc.h"
00072 
00073 
00075 typedef struct heap_s {
00076     void *data;                 /* Application data at this node */
00077     int32 val;                  /* Associated with above application data; according to which
00078                                    heap is sorted (in ascending order) */
00079     int32 nl, nr;               /* #left/right descendants of this node (for balancing heap) */
00080     struct heap_s *l;           /* Root of left descendant heap */
00081     struct heap_s *r;           /* Root of right descendant heap */
00082 } heapnode_t;
00083 
00084 
00085 #if 0
00086 static void
00087 heap_dump(heapnode_t * top, int32 level)
00088 {
00089     int32 i;
00090 
00091     if (!top)
00092         return;
00093 
00094     for (i = 0; i < level; i++)
00095         printf("  ");
00096     /* print top info */
00097     heap_dump(top->l, level + 1);
00098     heap_dump(top->r, level + 1);
00099 }
00100 #endif
00101 
00102 
00103 heap_t
00104 heap_new(void)
00105 {
00106     heapnode_t **h;
00107 
00108     h = (heapnode_t **) ckd_calloc(1, sizeof(heapnode_t *));
00109     *h = NULL;
00110 
00111     return ((heap_t) h);
00112 }
00113 
00114 
00115 static heapnode_t *
00116 subheap_insert(heapnode_t * root, void *data, int32 val)
00117 {
00118     heapnode_t *h;
00119     void *tmpdata;
00120     int32 tmpval;
00121 
00122     if (!root) {
00123         h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
00124         h->data = data;
00125         h->val = val;
00126         h->l = h->r = NULL;
00127         h->nl = h->nr = 0;
00128         return h;
00129     }
00130 
00131     /* Root already exists; if new value is less, replace root node */
00132     if (root->val > val) {
00133         tmpdata = root->data;
00134         tmpval = root->val;
00135         root->data = data;
00136         root->val = val;
00137         data = tmpdata;
00138         val = tmpval;
00139     }
00140 
00141     /* Insert new or old (replaced) node in right or left subtree; keep them balanced */
00142     if (root->nl > root->nr) {
00143         root->r = subheap_insert(root->r, data, val);
00144         root->nr++;
00145     }
00146     else {
00147         root->l = subheap_insert(root->l, data, val);
00148         root->nl++;
00149     }
00150 
00151     return root;
00152 }
00153 
00154 
00155 int32
00156 heap_insert(heap_t heap, void *data, int32 val)
00157 {
00158     heapnode_t **hp;
00159 
00160     hp = (heapnode_t **) heap;
00161 
00162     *hp = subheap_insert(*hp, data, val);
00163 
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 int32
00209 heap_pop(heap_t heap, void **data, int32 * val)
00210 {
00211     heapnode_t **hp, *h;
00212 
00213     hp = (heapnode_t **) heap;
00214     h = *hp;
00215 
00216     if (!h)
00217         return 0;
00218 
00219     *data = h->data;
00220     *val = h->val;
00221 
00222     *hp = subheap_pop(h);
00223 
00224     return 1;
00225 }
00226 
00227 
00228 int32
00229 heap_top(heap_t heap, void **data, int32 * val)
00230 {
00231     heapnode_t **hp, *h;
00232 
00233     hp = (heapnode_t **) heap;
00234     h = *hp;
00235 
00236     if (!h)
00237         return 0;
00238 
00239     *data = h->data;
00240     *val = h->val;
00241 
00242     return 1;
00243 }
00244 
00245 
00246 int32
00247 heap_destroy(heap_t heap)
00248 {
00249     void *data;
00250     int32 val;
00251 
00252     /* Empty the heap and free it */
00253     while (heap_pop(heap, &data, &val) > 0);
00254     ckd_free((char *) heap);
00255 
00256     return 0;
00257 }

Generated on Fri Jan 14 2011 for SphinxBase by  doxygen 1.7.1