• 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 "err.h"
00072 #include "ckd_alloc.h"
00073 
00074 
00076 typedef struct heap_s {
00077     void *data;                 /* Application data at this node */
00078     int32 val;                  /* Associated with above application data; according to which
00079                                    heap is sorted (in ascending order) */
00080     int32 nl, nr;               /* #left/right descendants of this node (for balancing heap) */
00081     struct heap_s *l;           /* Root of left descendant heap */
00082     struct heap_s *r;           /* Root of right descendant heap */
00083 } heapnode_t;
00084 
00085 
00086 #if 0
00087 static void
00088 heap_dump(heapnode_t * top, int32 level)
00089 {
00090     int32 i;
00091 
00092     if (!top)
00093         return;
00094 
00095     for (i = 0; i < level; i++)
00096         printf("  ");
00097     /* print top info */
00098     heap_dump(top->l, level + 1);
00099     heap_dump(top->r, level + 1);
00100 }
00101 #endif
00102 
00103 
00104 heap_t
00105 heap_new(void)
00106 {
00107     heapnode_t **h;
00108 
00109     h = (heapnode_t **) ckd_calloc(1, sizeof(heapnode_t *));
00110     *h = NULL;
00111 
00112     return ((heap_t) h);
00113 }
00114 
00115 
00116 static heapnode_t *
00117 subheap_insert(heapnode_t * root, void *data, int32 val)
00118 {
00119     heapnode_t *h;
00120     void *tmpdata;
00121     int32 tmpval;
00122 
00123     if (!root) {
00124         h = (heapnode_t *) ckd_calloc(1, sizeof(heapnode_t));
00125         h->data = data;
00126         h->val = val;
00127         h->l = h->r = NULL;
00128         h->nl = h->nr = 0;
00129         return h;
00130     }
00131 
00132     /* Root already exists; if new value is less, replace root node */
00133     if (root->val > val) {
00134         tmpdata = root->data;
00135         tmpval = root->val;
00136         root->data = data;
00137         root->val = val;
00138         data = tmpdata;
00139         val = tmpval;
00140     }
00141 
00142     /* Insert new or old (replaced) node in right or left subtree; keep them balanced */
00143     if (root->nl > root->nr) {
00144         root->r = subheap_insert(root->r, data, val);
00145         root->nr++;
00146     }
00147     else {
00148         root->l = subheap_insert(root->l, data, val);
00149         root->nl++;
00150     }
00151 
00152     return root;
00153 }
00154 
00155 
00156 int32
00157 heap_insert(heap_t heap, void *data, int32 val)
00158 {
00159     heapnode_t **hp;
00160 
00161     hp = (heapnode_t **) heap;
00162 
00163     *hp = subheap_insert(*hp, data, val);
00164 
00165     return 0;
00166 }
00167 
00168 
00169 static heapnode_t *
00170 subheap_pop(heapnode_t * root)
00171 {
00172     heapnode_t *l, *r;
00173 
00174     /* Propagate best value from below into root, if any */
00175     l = root->l;
00176     r = root->r;
00177 
00178     if (!l) {
00179         if (!r) {
00180             ckd_free((char *) root);
00181             return NULL;
00182         }
00183         else {
00184             root->data = r->data;
00185             root->val = r->val;
00186             root->r = subheap_pop(r);
00187             root->nr--;
00188         }
00189     }
00190     else {
00191         if ((!r) || (l->val < r->val)) {
00192             root->data = l->data;
00193             root->val = l->val;
00194             root->l = subheap_pop(l);
00195             root->nl--;
00196         }
00197         else {
00198             root->data = r->data;
00199             root->val = r->val;
00200             root->r = subheap_pop(r);
00201             root->nr--;
00202         }
00203     }
00204 
00205     return root;
00206 }
00207 
00208 
00209 int32
00210 heap_pop(heap_t heap, void **data, int32 * val)
00211 {
00212     heapnode_t **hp, *h;
00213 
00214     hp = (heapnode_t **) heap;
00215     h = *hp;
00216 
00217     if (!h)
00218         return 0;
00219 
00220     *data = h->data;
00221     *val = h->val;
00222 
00223     *hp = subheap_pop(h);
00224 
00225     return 1;
00226 }
00227 
00228 
00229 int32
00230 heap_top(heap_t heap, void **data, int32 * val)
00231 {
00232     heapnode_t **hp, *h;
00233 
00234     hp = (heapnode_t **) heap;
00235     h = *hp;
00236 
00237     if (!h)
00238         return 0;
00239 
00240     *data = h->data;
00241     *val = h->val;
00242 
00243     return 1;
00244 }
00245 
00246 int32
00247 heap_size(heap_t heap)
00248 {
00249     heapnode_t **hp, *h;
00250 
00251     hp = (heapnode_t **) heap;
00252     h = *hp;
00253 
00254     if (h == NULL)
00255         return 0;
00256     return h->nl + h->nr + 1;
00257 }
00258 
00259 int32
00260 heap_destroy(heap_t heap)
00261 {
00262     void *data;
00263     int32 val;
00264 
00265     /* Empty the heap and free it */
00266     while (heap_pop(heap, &data, &val) > 0);
00267     ckd_free((char *) heap);
00268 
00269     return 0;
00270 }

Generated on Thu Jan 6 2011 for SphinxBase by  doxygen 1.7.1