Annotation of embedaddon/bird/lib/heap.h, revision 1.1
1.1 ! misho 1: /*
! 2: * UCW Library -- Universal Heap Macros
! 3: *
! 4: * (c) 2001 Martin Mares <mj@ucw.cz>
! 5: * (c) 2005 Tomas Valla <tom@ucw.cz>
! 6: *
! 7: * This software may be freely distributed and used according to the terms
! 8: * of the GNU Lesser General Public License.
! 9: */
! 10:
! 11: /**
! 12: * [[intro]]
! 13: * Introduction
! 14: * ------------
! 15: *
! 16: * Binary heap is a simple data structure, which for example supports efficient insertions, deletions
! 17: * and access to the minimal inserted item. We define several macros for such operations.
! 18: * Note that because of simplicity of heaps, we have decided to define direct macros instead
! 19: * of a <<generic:,macro generator>> as for several other data structures in the Libucw.
! 20: *
! 21: * A heap is represented by a number of elements and by an array of values. Beware that we
! 22: * index this array from one, not from zero as do the standard C arrays.
! 23: *
! 24: * Most macros use these parameters:
! 25: *
! 26: * - @type - the type of elements
! 27: * - @num - a variable (signed or unsigned integer) with the number of elements
! 28: * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
! 29: * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y
! 30: * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type).
! 31: *
! 32: * A valid heap must follow these rules:
! 33: *
! 34: * - `num >= 0`
! 35: * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
! 36: *
! 37: * The first element `heap[1]` is always lower or equal to all other elements.
! 38: *
! 39: * [[macros]]
! 40: * Macros
! 41: * ------
! 42: */
! 43:
! 44: /* For internal usage. */
! 45: #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \
! 46: for (;;) \
! 47: { \
! 48: _l = 2*_j; \
! 49: if (_l > num) \
! 50: break; \
! 51: if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1]))) \
! 52: break; \
! 53: if (_l != num && less(heap[_l+1],heap[_l])) \
! 54: _l++; \
! 55: swap(heap,_j,_l,x); \
! 56: _j = _l; \
! 57: }
! 58:
! 59: /* For internal usage. */
! 60: #define HEAP_BUBBLE_UP_J(heap,num,less,swap) \
! 61: while (_j > 1) \
! 62: { \
! 63: _u = _j/2; \
! 64: if (less(heap[_u], heap[_j])) \
! 65: break; \
! 66: swap(heap,_u,_j,x); \
! 67: _j = _u; \
! 68: }
! 69:
! 70: /**
! 71: * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear.
! 72: **/
! 73: #define HEAP_INIT(heap,num,type,less,swap) \
! 74: do { \
! 75: uint _i = num; \
! 76: uint _j, _l; \
! 77: type x; \
! 78: while (_i >= 1) \
! 79: { \
! 80: _j = _i; \
! 81: HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \
! 82: _i--; \
! 83: } \
! 84: } while(0)
! 85:
! 86: /**
! 87: * Delete the minimum element `heap[1]` in `O(log(n))` time.
! 88: * The removed value is moved just after the resulting heap (`heap[num + 1]`).
! 89: **/
! 90: #define HEAP_DELMIN(heap,num,type,less,swap) \
! 91: do { \
! 92: uint _j, _l; \
! 93: type x; \
! 94: swap(heap,1,num,x); \
! 95: num--; \
! 96: _j = 1; \
! 97: HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
! 98: } while(0)
! 99:
! 100: /**
! 101: * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before.
! 102: **/
! 103: #define HEAP_INSERT(heap,num,type,less,swap) \
! 104: do { \
! 105: uint _j, _u; \
! 106: type x; \
! 107: _j = num; \
! 108: HEAP_BUBBLE_UP_J(heap,num,less,swap); \
! 109: } while(0)
! 110:
! 111: /**
! 112: * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
! 113: * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
! 114: * The time complexity is `O(log(n))`.
! 115: **/
! 116: #define HEAP_INCREASE(heap,num,type,less,swap,pos) \
! 117: do { \
! 118: uint _j, _l; \
! 119: type x; \
! 120: _j = pos; \
! 121: HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
! 122: } while(0)
! 123:
! 124: /**
! 125: * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
! 126: * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
! 127: * The time complexity is `O(log(n))`.
! 128: **/
! 129: #define HEAP_DECREASE(heap,num,type,less,swap,pos) \
! 130: do { \
! 131: uint _j, _u; \
! 132: type x; \
! 133: _j = pos; \
! 134: HEAP_BUBBLE_UP_J(heap,num,less,swap); \
! 135: } while(0)
! 136:
! 137: /**
! 138: * Delete `heap[pos]` in `O(log(n))` time.
! 139: **/
! 140: #define HEAP_DELETE(heap,num,type,less,swap,pos) \
! 141: do { \
! 142: uint _j, _l, _u; \
! 143: type x; \
! 144: _j = pos; \
! 145: swap(heap,_j,num,x); \
! 146: num--; \
! 147: if (less(heap[_j], heap[num+1])) \
! 148: HEAP_BUBBLE_UP_J(heap,num,less,swap) \
! 149: else \
! 150: HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
! 151: } while(0)
! 152:
! 153: /**
! 154: * Default swapping macro.
! 155: **/
! 156: #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to heap.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib