Annotation of embedaddon/ntp/lib/isc/heap.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Copyright (C) 2004-2007 Internet Systems Consortium, Inc. ("ISC")
! 3: * Copyright (C) 1997-2001 Internet Software Consortium.
! 4: *
! 5: * Permission to use, copy, modify, and/or distribute this software for any
! 6: * purpose with or without fee is hereby granted, provided that the above
! 7: * copyright notice and this permission notice appear in all copies.
! 8: *
! 9: * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
! 10: * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
! 11: * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
! 12: * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
! 13: * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
! 14: * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
! 15: * PERFORMANCE OF THIS SOFTWARE.
! 16: */
! 17:
! 18: /* $Id: heap.c,v 1.37 2007/10/19 17:15:53 explorer Exp $ */
! 19:
! 20: /*! \file
! 21: * Heap implementation of priority queues adapted from the following:
! 22: *
! 23: * \li "Introduction to Algorithms," Cormen, Leiserson, and Rivest,
! 24: * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7.
! 25: *
! 26: * \li "Algorithms," Second Edition, Sedgewick, Addison-Wesley, 1988,
! 27: * ISBN 0-201-06673-4, chapter 11.
! 28: */
! 29:
! 30: #include <config.h>
! 31:
! 32: #include <isc/heap.h>
! 33: #include <isc/magic.h>
! 34: #include <isc/mem.h>
! 35: #include <isc/string.h> /* Required for memcpy. */
! 36: #include <isc/util.h>
! 37:
! 38: /*@{*/
! 39: /*%
! 40: * Note: to make heap_parent and heap_left easy to compute, the first
! 41: * element of the heap array is not used; i.e. heap subscripts are 1-based,
! 42: * not 0-based. The parent is index/2, and the left-child is index*2.
! 43: * The right child is index*2+1.
! 44: */
! 45: #define heap_parent(i) ((i) >> 1)
! 46: #define heap_left(i) ((i) << 1)
! 47: /*@}*/
! 48:
! 49: #define SIZE_INCREMENT 1024
! 50:
! 51: #define HEAP_MAGIC ISC_MAGIC('H', 'E', 'A', 'P')
! 52: #define VALID_HEAP(h) ISC_MAGIC_VALID(h, HEAP_MAGIC)
! 53:
! 54: /*%
! 55: * When the heap is in a consistent state, the following invariant
! 56: * holds true: for every element i > 1, heap_parent(i) has a priority
! 57: * higher than or equal to that of i.
! 58: */
! 59: #define HEAPCONDITION(i) ((i) == 1 || \
! 60: ! heap->compare(heap->array[(i)], \
! 61: heap->array[heap_parent(i)]))
! 62:
! 63: /*% ISC heap structure. */
! 64: struct isc_heap {
! 65: unsigned int magic;
! 66: isc_mem_t * mctx;
! 67: unsigned int size;
! 68: unsigned int size_increment;
! 69: unsigned int last;
! 70: void **array;
! 71: isc_heapcompare_t compare;
! 72: isc_heapindex_t index;
! 73: };
! 74:
! 75: isc_result_t
! 76: isc_heap_create(isc_mem_t *mctx, isc_heapcompare_t compare,
! 77: isc_heapindex_t index, unsigned int size_increment,
! 78: isc_heap_t **heapp)
! 79: {
! 80: isc_heap_t *heap;
! 81:
! 82: REQUIRE(heapp != NULL && *heapp == NULL);
! 83: REQUIRE(compare != NULL);
! 84:
! 85: heap = isc_mem_get(mctx, sizeof(*heap));
! 86: if (heap == NULL)
! 87: return (ISC_R_NOMEMORY);
! 88: heap->magic = HEAP_MAGIC;
! 89: heap->mctx = mctx;
! 90: heap->size = 0;
! 91: if (size_increment == 0)
! 92: heap->size_increment = SIZE_INCREMENT;
! 93: else
! 94: heap->size_increment = size_increment;
! 95: heap->last = 0;
! 96: heap->array = NULL;
! 97: heap->compare = compare;
! 98: heap->index = index;
! 99:
! 100: *heapp = heap;
! 101:
! 102: return (ISC_R_SUCCESS);
! 103: }
! 104:
! 105: void
! 106: isc_heap_destroy(isc_heap_t **heapp) {
! 107: isc_heap_t *heap;
! 108:
! 109: REQUIRE(heapp != NULL);
! 110: heap = *heapp;
! 111: REQUIRE(VALID_HEAP(heap));
! 112:
! 113: if (heap->array != NULL)
! 114: isc_mem_put(heap->mctx, heap->array,
! 115: heap->size * sizeof(void *));
! 116: heap->magic = 0;
! 117: isc_mem_put(heap->mctx, heap, sizeof(*heap));
! 118:
! 119: *heapp = NULL;
! 120: }
! 121:
! 122: static isc_boolean_t
! 123: resize(isc_heap_t *heap) {
! 124: void **new_array;
! 125: size_t new_size;
! 126:
! 127: REQUIRE(VALID_HEAP(heap));
! 128:
! 129: new_size = heap->size + heap->size_increment;
! 130: new_array = isc_mem_get(heap->mctx, new_size * sizeof(void *));
! 131: if (new_array == NULL)
! 132: return (ISC_FALSE);
! 133: if (heap->array != NULL) {
! 134: memcpy(new_array, heap->array, heap->size * sizeof(void *));
! 135: isc_mem_put(heap->mctx, heap->array,
! 136: heap->size * sizeof(void *));
! 137: }
! 138: heap->size = new_size;
! 139: heap->array = new_array;
! 140:
! 141: return (ISC_TRUE);
! 142: }
! 143:
! 144: static void
! 145: float_up(isc_heap_t *heap, unsigned int i, void *elt) {
! 146: unsigned int p;
! 147:
! 148: for (p = heap_parent(i) ;
! 149: i > 1 && heap->compare(elt, heap->array[p]) ;
! 150: i = p, p = heap_parent(i)) {
! 151: heap->array[i] = heap->array[p];
! 152: if (heap->index != NULL)
! 153: (heap->index)(heap->array[i], i);
! 154: }
! 155: heap->array[i] = elt;
! 156: if (heap->index != NULL)
! 157: (heap->index)(heap->array[i], i);
! 158:
! 159: INSIST(HEAPCONDITION(i));
! 160: }
! 161:
! 162: static void
! 163: sink_down(isc_heap_t *heap, unsigned int i, void *elt) {
! 164: unsigned int j, size, half_size;
! 165: size = heap->last;
! 166: half_size = size / 2;
! 167: while (i <= half_size) {
! 168: /* Find the smallest of the (at most) two children. */
! 169: j = heap_left(i);
! 170: if (j < size && heap->compare(heap->array[j+1],
! 171: heap->array[j]))
! 172: j++;
! 173: if (heap->compare(elt, heap->array[j]))
! 174: break;
! 175: heap->array[i] = heap->array[j];
! 176: if (heap->index != NULL)
! 177: (heap->index)(heap->array[i], i);
! 178: i = j;
! 179: }
! 180: heap->array[i] = elt;
! 181: if (heap->index != NULL)
! 182: (heap->index)(heap->array[i], i);
! 183:
! 184: INSIST(HEAPCONDITION(i));
! 185: }
! 186:
! 187: isc_result_t
! 188: isc_heap_insert(isc_heap_t *heap, void *elt) {
! 189: unsigned int i;
! 190:
! 191: REQUIRE(VALID_HEAP(heap));
! 192:
! 193: i = ++heap->last;
! 194: if (heap->last >= heap->size && !resize(heap))
! 195: return (ISC_R_NOMEMORY);
! 196:
! 197: float_up(heap, i, elt);
! 198:
! 199: return (ISC_R_SUCCESS);
! 200: }
! 201:
! 202: void
! 203: isc_heap_delete(isc_heap_t *heap, unsigned int index) {
! 204: void *elt;
! 205: isc_boolean_t less;
! 206:
! 207: REQUIRE(VALID_HEAP(heap));
! 208: REQUIRE(index >= 1 && index <= heap->last);
! 209:
! 210: if (index == heap->last) {
! 211: heap->array[heap->last] = NULL;
! 212: heap->last--;
! 213: } else {
! 214: elt = heap->array[heap->last];
! 215: heap->array[heap->last] = NULL;
! 216: heap->last--;
! 217:
! 218: less = heap->compare(elt, heap->array[index]);
! 219: heap->array[index] = elt;
! 220: if (less)
! 221: float_up(heap, index, heap->array[index]);
! 222: else
! 223: sink_down(heap, index, heap->array[index]);
! 224: }
! 225: }
! 226:
! 227: void
! 228: isc_heap_increased(isc_heap_t *heap, unsigned int index) {
! 229: REQUIRE(VALID_HEAP(heap));
! 230: REQUIRE(index >= 1 && index <= heap->last);
! 231:
! 232: float_up(heap, index, heap->array[index]);
! 233: }
! 234:
! 235: void
! 236: isc_heap_decreased(isc_heap_t *heap, unsigned int index) {
! 237: REQUIRE(VALID_HEAP(heap));
! 238: REQUIRE(index >= 1 && index <= heap->last);
! 239:
! 240: sink_down(heap, index, heap->array[index]);
! 241: }
! 242:
! 243: void *
! 244: isc_heap_element(isc_heap_t *heap, unsigned int index) {
! 245: REQUIRE(VALID_HEAP(heap));
! 246: REQUIRE(index >= 1);
! 247:
! 248: if (index <= heap->last)
! 249: return (heap->array[index]);
! 250: return (NULL);
! 251: }
! 252:
! 253: void
! 254: isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap) {
! 255: unsigned int i;
! 256:
! 257: REQUIRE(VALID_HEAP(heap));
! 258: REQUIRE(action != NULL);
! 259:
! 260: for (i = 1 ; i <= heap->last ; i++)
! 261: (action)(heap->array[i], uap);
! 262: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to heap.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / lib / isc