src/libsphinxbase/util/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
  74 /**
  75  * One node on the heap
  76  */
  77 typedef struct heapnode_s {
  78     void *data;                 /**< Application data at this node */
  79     int32 val;                  /**< Associated with above application data; according to which
  80                                    heap is sorted (in ascending order) */
  81     int32 nl, nr;               /**< #left/right descendants of this node (for balancing heap) */
  82     struct heapnode_s *l;       /**< Root of left descendant heap */
  83     struct heapnode_s *r;       /**< Root of right descendant heap */
  84 } heapnode_t;
  85
  86 /**
  87  * Internal heap data structure.
  88  */
  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
 273 heap_size(heap_t *heap)
 274 {
 275     if (heap->top == NULL)
 276         return 0;
 277     return heap->top->nl + heap->top->nr + 1;
 278 }
 279
 280 int
 281 heap_destroy(heap_t *heap)
 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 }