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.h -- 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.h,v $ 50 * Revision 1.7 2005/06/22 03:05:49 arthchan2003 51 * 1, Fixed doxygen documentation, 2, Add keyword. 52 * 53 * Revision 1.4 2005/06/15 04:21:46 archan 54 * 1, Fixed doxygen-documentation, 2, Add keyword such that changes will be logged into a file. 55 * 56 * Revision 1.3 2005/03/30 01:22:48 archan 57 * Fixed mistakes in last updates. Add 58 * 59 * 60 * 23-Dec-96 M K Ravishankar (rkm@cs.cmu.edu) at Carnegie Mellon University 61 * Started. 62 */ 63 64 65 #ifndef _LIBUTIL_HEAP_H_ 66 #define _LIBUTIL_HEAP_H_ 67 68 #include <stdlib.h> 69 70 /* Win32/WinCE DLL gunk */ 71 #include <sphinxbase/sphinxbase_export.h> 72 #include <sphinxbase/prim_type.h> 73 74 /** \file heap.h 75 * \brief Heap Implementation. 76 * 77 * General Comment: Sorted heap structure with three main operations: 78 * 79 * 1. Insert a data item (with two attributes: an application supplied pointer and an 80 * integer value; the heap is maintained in ascending order of the integer value). 81 * 2. Return the currently topmost item (i.e., item with smallest associated value). 82 * 3. Return the currently topmost item and pop it off the heap. 83 */ 84 85 #ifdef __cplusplus 86 extern "C" { 87 #endif 88 #if 0 89 /* Fool Emacs. */ 90 } 91 #endif 92 93 94 typedef struct heap_s heap_t; 95 96 97 /** 98 * Allocate a new heap and return handle to it. 99 */ 100 SPHINXBASE_EXPORT 101 heap_t *heap_new(void); 102 103 104 /** 105 * Insert a new item into the given heap. 106 * Return value: 0 if successful, -1 otherwise. 107 */ 108 SPHINXBASE_EXPORT 109 int heap_insert(heap_t *heap, /**< In: Heap into which item is to be inserted */ 110 void *data, /**< In: Application-determined data pointer */ 111 int32 val /**< In: According to item entered in sorted heap */ 112 ); 113 /** 114 * Return the topmost item in the heap. 115 * Return value: 1 if heap is not empty and the topmost value is returned; 116 * 0 if heap is empty; -1 if some error occurred. 117 */ 118 SPHINXBASE_EXPORT 119 int heap_top(heap_t *heap, /**< In: Heap whose topmost item is to be returned */ 120 void **data, /**< Out: Data pointer associated with the topmost item */ 121 int32 *val /**< Out: Value associated with the topmost item */ 122 ); 123 /** 124 * Like heap_top but also pop the top item off the heap. 125 */ 126 SPHINXBASE_EXPORT 127 int heap_pop(heap_t *heap, void **data, int32 *val); 128 129 /** 130 * Remove an item from the heap. 131 */ 132 SPHINXBASE_EXPORT 133 int heap_remove(heap_t *heap, void *data); 134 135 /** 136 * Return the number of items in the heap. 137 */ 138 SPHINXBASE_EXPORT 139 size_t heap_size(heap_t *heap); 140 141 /** 142 * Destroy the given heap; free the heap nodes. NOTE: Data pointers in the nodes are NOT freed. 143 * Return value: 0 if successful, -1 otherwise. 144 */ 145 146 SPHINXBASE_EXPORT 147 int heap_destroy(heap_t *heap); 148 149 #ifdef __cplusplus 150 } 151 #endif 152 153 #endif 154