1 /***************************************************************************** 2 * $Id: list.h,v 1.2 2008-08-12 18:14:34 chu11 Exp $ 3 ***************************************************************************** 4 * Copyright (C) 2012-2015 Lawrence Livermore National Security, LLC. 5 * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). 6 * Written by Albert Chu <chu11@llnl.gov> 7 * LLNL-CODE-559172 8 * 9 * This file is part of Ipmiseld, an IPMI SEL syslog logging daemon. 10 * For details, see http://www.llnl.gov/linux/. 11 * 12 * Ipmiseld is free software; you can redistribute it and/or modify 13 * it under the terms of the GNU General Public License as published by the 14 * Free Software Foundation; either version 3 of the License, or (at your 15 * option) any later version. 16 * 17 * Ipmiseld is distributed in the hope that it will be useful, but 18 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 19 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 20 * for more details. 21 * 22 * You should have received a copy of the GNU General Public License along 23 * with Ipmiseld. If not, see <http://www.gnu.org/licenses/>. 24 ***************************************************************************** 25 * Copyright (C) 2001-2002 The Regents of the University of California. 26 * Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER). 27 * Written by Chris Dunlap <cdunlap@llnl.gov>. 28 * 29 * This file is from LSD-Tools, the LLNL Software Development Toolbox. 30 * 31 * LSD-Tools is free software; you can redistribute it and/or modify it under 32 * the terms of the GNU General Public License as published by the Free 33 * Software Foundation; either version 2 of the License, or (at your option) 34 * any later version. 35 * 36 * LSD-Tools is distributed in the hope that it will be useful, but WITHOUT 37 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 38 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 39 * more details. 40 * 41 * You should have received a copy of the GNU General Public License along 42 * with LSD-Tools; if not, write to the Free Software Foundation, Inc., 43 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 44 *****************************************************************************/ 45 46 47 #ifndef LSD_HEAP_H 48 #define LSD_HEAP_H 49 50 51 /*********** 52 * Notes * 53 ***********/ 54 55 /* API emulates Chris Dunlap's (dunlap6 at llnl dot gov) List library. 56 * Lots of code was copied. 57 */ 58 /* 59 * If NDEBUG is not defined, internal debug code will be enabled. This is 60 * intended for development use only and production code should define NDEBUG. 61 * 62 * If WITH_LSD_FATAL_ERROR_FUNC is defined, the linker will expect to 63 * find an external lsd_fatal_error(file,line,mesg) function. By default, 64 * lsd_fatal_error(file,line,mesg) is a macro definition that outputs an 65 * error message to stderr. This macro may be redefined to invoke another 66 * routine instead. 67 * 68 * If WITH_LSD_NOMEM_ERROR_FUNC is defined, the linker will expect to 69 * find an external lsd_nomem_error(file,line,mesg) function. By default, 70 * lsd_nomem_error(file,line,mesg) is a macro definition that returns NULL. 71 * This macro may be redefined to invoke another routine instead. 72 * 73 * If WITH_PTHREADS is defined, these routines will be thread-safe. 74 */ 75 76 77 /**************** 78 * Data Types * 79 ****************/ 80 81 typedef struct heap * Heap; 82 /* 83 * Heap opaque data type. 84 */ 85 86 typedef void (*HeapDelF) (void *x); 87 /* 88 * Function prototype to deallocate data stored in a heap. 89 * This function is responsible for freeing all memory associated 90 * with an item, including all subordinate items (if applicable). 91 */ 92 93 typedef int (*HeapCmpF) (void *x, void *y); 94 /* 95 * Function prototype for comparing two items in a heap. 96 * Returns less-than-zero if (x<y), zero if (x==y), and 97 * greather-than-zero if (x>y). 98 */ 99 100 /******************************* 101 * General-Purpose Functions * 102 *******************************/ 103 104 Heap heap_create (int size, HeapCmpF fCmp, HeapDelF fDel); 105 /* 106 * Creates and returns a new empty heap, or lsd_nomem_error() on failure. 107 * The [size] is guidance on the number of slots in the heap; If set 108 * <= 0, the default size is used. Usually, the next power of 2 109 * will be used for size, but with a minimum used internally. 110 * The comparison function [fCmp] is used for comparison of items 111 * added to the heap. This heap operates as a max heap when utilizing 112 * the HeapCmpF. To implement a min heap, adjust the HeapCmpF function 113 * appropriately. 114 * The deletion function [fDel] is used to deallocate memory used by items 115 * in the heap; if this is NULL, memory associated with these items 116 * will not be freed when the heap is destroyed. 117 * Note: Abandoning a heap without calling heap_destroy() will result 118 * in a memory leak. 119 */ 120 121 void heap_destroy (Heap h); 122 /* 123 * Destroys heap [h], freeing memory used for heap iterators and the 124 * heap itself; if a deletion function was specified when the heap 125 * was created, it will be called for each item in the heap. 126 */ 127 128 int heap_is_empty (Heap h); 129 /* 130 * Returns non-zero if heap [h] is empty; o/w returns zero. 131 */ 132 133 int heap_is_full (Heap h); 134 /* 135 * Returns non-zero if heap [h] is full; o/w returns zero. 136 */ 137 138 /**************************** 139 * Access Functions * 140 ****************************/ 141 142 void * heap_insert (Heap h, void *x); 143 /* 144 * Pushes data [x] onto the top of heap [h]. 145 * Returns the data's ptr, or lsd_nomem_error() if insertion failed. 146 */ 147 148 void * heap_pop (Heap h); 149 /* 150 * Pops the data item at the top of the heap [h]. 151 * Returns the data's ptr, or NULL if the heap is empty. 152 */ 153 154 void * heap_peek (Heap h); 155 /* 156 * Peeks at the data item at the top of the heap [h]. 157 * Returns the data's ptr, or NULL if the heap is empty. 158 * Note: The item is not removed from the heap. 159 */ 160 161 #endif /* !LSD_HEAP_H */ 162