heap.h 10.1 KB
Newer Older
1 2 3
/*
 * This file is part of the Sofia-SIP package
 *
4
 * Copyright (C) 2007 Nokia Corporation.
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 *
 * Contact: Pekka Pessi <pekka.pessi@nokia.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA
 *
 */

#ifndef SOFIA_SIP_HEAP_H
/** Defined when <sofia-sip/heap.h> has been included. */
#define SOFIA_SIP_HEAP_H

/**@file sofia-sip/heap.h
 *
31
 * Heap template implemented with dynamic array.
32
 *
33
 * This file contain template macros implementing @a heap in C. The @a heap
34
 * keeps its element in a known order and it can be used to implement, for
35
 * example, a prioritye queue or an ordered queue.
36 37
 *
 * The ordering within the heap is defined as follows:
38
 * - indexing starts from 1
39
 * - for each element with index @a [i] in the heap there are two descendant
40
 *   elements with indices @a [2*i] and @a [2*i+1],
41 42
 * - the heap guarantees that the descendant elements are never smaller than
 *   their parent element.
43 44
 * Therefore it follows that there is no element smaller than element at
 * index [1] in the rest of the heap.
45 46 47
 *
 * Adding and removing elements to the heap is an @a O(logN)
 * operation.
48
 *
49 50 51 52 53 54
 * The heap array is resizeable, and it usually contain pointers to the
 * actual entries. The template macros define two functions used to add and
 * remove entries to the heap. The @a add() function takes the element to be
 * added as its argument, the @a remove() function the index of the element
 * to be removed. The template defines also a predicate used to check if the
 * heap is full, and a function used to resize the heap.
55
 *
56 57
 * The heap user must define four primitives:
 * - less than comparison
58 59
 * - array setter
 * - heap array allocator
60
 * - empty element
61 62
 *
 * Please note that in order to remove an entry in the heap, the application
63
 * must know its index in the heap array.
64 65 66 67 68 69 70
 *
 * The heap struct is declared with macro HEAP_DECLARE(). The prototypes for
 * heap functions are instantiated with macro HEAP_PROTOS(). The
 * implementation is instantiated with macro HEAP_BODIES().
 *
 * Example code can be found from <su/torture_heap.c> and
 * <sresolv/sres_cache.c>.
71
 *
72 73
 * @author Pekka Pessi <Pekka.Pessi@nokia.com>.
 * @NEW_1_12_7.
74 75 76 77 78 79
 */

/** Minimum size of heap */
#define HEAP_MIN_SIZE 31

/** Declare heap structure type.
80
 *
81
 * The macro #HEAP_TYPE contains declaration of the heap structure.
82
 *
83
 * @showinitializer
84
 */
85
#define HEAP_TYPE struct { void *private; }
86 87 88

/** Prototypes for heap.
 *
89
 * The macro HEAP_PROTOS() expands to the prototypes of heap functions:
90 91
 * - prefix ## resize(argument, in_out_heap, size)
 * - prefix ## free(argument, in_heap)
92
 * - prefix ## is_full(heap)
93 94
 * - prefix ## size(heap)
 * - prefix ## used(heap)
95 96
 * - prefix ## add(heap, entry)
 * - prefix ## remove(heap, index)
97
 * - prefix ## get(heap, index)
98 99
 *
 * @param scope     scope of functions
100
 * @param heaptype  type of heap
101
 * @param prefix    function prefix
102
 * @param type      type of entries
103
 *
104 105
 * The declared functions will have scope @a scope (for example, @c static
 * or @c static inline). The declared function names will have prefix @a
106 107
 * prefix. The heap structure has type @a heaptype. The heap element type is
 * @a entrytype.
108 109
 *
 * @showinitializer
110
 */
111 112 113 114 115 116
#define HEAP_DECLARE(scope, heaptype, prefix, type) \
scope int prefix##resize(void *, heaptype *, size_t); \
scope int prefix##free(void *, heaptype *); \
scope int prefix##is_full(heaptype const); \
scope size_t prefix##size(heaptype const); \
scope size_t prefix##used(heaptype const); \
Pekka Pessi's avatar
Pekka Pessi committed
117
scope void prefix##sort(heaptype); \
118 119 120
scope int prefix##add(heaptype, type); \
scope type prefix##remove(heaptype, size_t); \
scope type prefix##get(heaptype, size_t)
121

122
/**Heap implementation.
123
 *
124 125
 * The macro HEAP_BODIES() expands to the bodies of heap functions:
 * - prefix ## resize(argument, heap, size)
126
 * - prefix ## free(argument, in_heap)
127
 * - prefix ## is_full(heap)
128 129
 * - prefix ## size(heap)
 * - prefix ## used(heap)
Pekka Pessi's avatar
Pekka Pessi committed
130
 * - prefix ## sort(heap)
131 132
 * - prefix ## add(heap, entry)
 * - prefix ## remove(heap, index)
133
 * - prefix ## get(heap, index)
134 135 136
 *
 * @param scope     scope of functions
 * @param prefix    function prefix for heap
137
 * @param heaptype  type of heap
138
 * @param type      type of heaped elements
139
 * @param less      function or macro comparing two entries
140
 * @param set       function or macro assigning entry to array
141 142
 * @param alloc     function allocating or freeing memory
 * @param null      empty element (returned when index is invalid)
143 144 145 146
 *
 * Functions have scope @a scope, e.g., @c static @c inline.
 * The heap structure has type @a type.
 * The function names start with @a prefix, the field names start
147
 * with @a pr. The entry type is @a entrytype.
148 149 150 151 152 153 154 155 156 157 158 159 160

 * The function (or macro) @a less compares two entries in heap. It gets two
 * arguments and it returns true if its left argument is less than its right
 * argument.

 * The function (or macro) @a set stores an entry in heap array. It gets
 * three arguments, first is heap array, second index to the array and third
 * the element to store at the given index.
 *
 * The function (or macro) @a halloc re-allocates the heap array. It
 * receives three arguments, first is the first @a argument given to @a
 * resize(), second the pointer to existing heap and third is the number of
 * bytes in the heap.
161
 */
162 163
#define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
164
{ \
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
  struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
  struct prefix##priv *_priv; \
  size_t _offset = \
    (offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
  size_t _min_size = 32 - _offset; \
  size_t _bytes; \
  size_t _used = 0; \
 \
  _priv = *(void **)h; \
 \
  if (_priv) { \
    if (new_size == 0) \
      new_size = 2 * _priv->_size + _offset + 1; \
    _used = _priv->_used; \
    if (new_size < _used) \
      new_size = _used; \
  } \
 \
  if (new_size < _min_size) \
    new_size = _min_size; \
 \
  _bytes = (_offset + 1 + new_size) * sizeof (type); \
 \
  (void)realloc_arg; /* avoid warning */ \
  _priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
  if (!_priv) \
191
    return -1; \
192 193 194 195 196
 \
  *(struct prefix##priv **)h = _priv; \
  _priv->_size = new_size; \
  _priv->_used = _used; \
 \
197 198
  return 0; \
} \
199 200 201 202 203 204 205 206 207
 \
/** Free heap. */ \
scope int prefix##free(void *realloc_arg, heaptype h[1]) \
{ \
  (void)realloc_arg; \
  *(void **)h = alloc(realloc_arg, *(void **)h, 0); \
  return 0; \
} \
 \
208
/** Check if heap is full */ \
209
scope int prefix##is_full(heaptype h) \
210
{ \
211 212 213 214
  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
  struct prefix##priv *_priv = *(void **)&h; \
 \
  return _priv == NULL || _priv->_used >= _priv->_size; \
215
} \
216
 \
217
/** Add an element to the heap */ \
218
scope int prefix##add(heaptype h, type e) \
219
{ \
220 221 222
  struct prefix##priv { size_t _size, _used; type _heap[1];};	\
  struct prefix##priv *_priv = *(void **)&h; \
  type *heap = _priv->_heap - 1; \
223
  size_t i, parent; \
224 225
 \
  if (_priv == NULL || _priv->_used >= _priv->_size) \
226
    return -1; \
227 228 229
 \
  for (i = ++_priv->_used; i > 1; i = parent) { \
    parent = i / 2; \
230
    if (!less(e, heap[parent])) \
231 232 233
      break; \
    set(heap, i, heap[parent]); \
  } \
234
 \
235
  set(heap, i, e); \
236
 \
237 238
  return 0; \
} \
239
 \
240
/** Remove element from heap */ \
241
scope type prefix##remove(heaptype h, size_t index) \
242
{ \
243 244 245
  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
  struct prefix##priv *_priv = *(void **)&h; \
  type *heap = _priv->_heap - 1; \
246
  type retval[1]; \
247 248 249 250 251 252 253 254
  type e; \
 \
  size_t top, left, right, move; \
 \
  if (index - 1 >= _priv->_used) \
    return (null); \
 \
  move = _priv->_used--; \
255
  set(retval, 0, heap[index]); \
256
 \
257
  for (top = index;;index = top) { \
258 259 260
    left = 2 * top; \
    right = 2 * top + 1; \
 \
261
    if (left >= move) \
262
      break; \
263
    if (right < move && less(heap[right], heap[left])) \
264 265 266 267 268
      top = right; \
    else \
      top = left; \
    set(heap, index, heap[top]); \
  } \
269 270
 \
  if (index == move) \
271
    return *retval; \
272 273 274 275
 \
  e = heap[move]; \
  for (; index > 1; index = top) { \
    top = index / 2; \
276 277 278 279
    if (!less(e, heap[top])) \
      break; \
    set(heap, index, heap[top]); \
  } \
280
 \
281
  set(heap, index, e); \
282
 \
283
  return *retval; \
284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
} \
 \
scope \
type prefix##get(heaptype h, size_t index) \
{ \
  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
  struct prefix##priv *_priv = *(void **)&h; \
 \
  if (--index >= _priv->_used) \
    return (null); \
 \
  return _priv->_heap[index]; \
} \
 \
scope \
size_t prefix##size(heaptype const h) \
{ \
  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
  struct prefix##priv *_priv = *(void **)&h; \
  return _priv ? _priv->_size : 0; \
} \
 \
scope \
size_t prefix##used(heaptype const h) \
{ \
  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
  struct prefix##priv *_priv = *(void **)&h; \
  return _priv ? _priv->_used : 0; \
312
} \
Pekka Pessi's avatar
Pekka Pessi committed
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331
scope int prefix##_less(void *h, size_t a, size_t b) \
{ \
  type *_heap = h; return less(_heap[a], _heap[b]);	\
} \
scope void prefix##_swap(void *h, size_t a, size_t b) \
{ \
  type *_heap = h; type _swap = _heap[a]; \
  set(_heap, a, _heap[b]); set(_heap, b, _swap); \
} \
void su_smoothsort(void *base, size_t r0, size_t N,		\
		   int (*less)(void *base, size_t a, size_t b), \
		   void (*swap)(void *base, size_t a, size_t b));	\
scope void prefix##sort(heaptype h) \
{ \
  struct prefix##priv { size_t _size, _used; type _heap[1];}; \
  struct prefix##priv *_priv = *(void **)&h; \
  if (_priv) \
    su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
} \
332
extern int const prefix##dummy_heap
333

334
#endif /** !defined(SOFIA_SIP_HEAP_H) */