Go to the documentation of this file.
25 #ifndef SOFIA_SIP_HEAP_H
27 #define SOFIA_SIP_HEAP_H
77 #define HEAP_MIN_SIZE 31
85 #define HEAP_TYPE struct { void *private; }
111 #define HEAP_DECLARE(scope, heaptype, prefix, type) \
112 scope int prefix##resize(void *, heaptype *, size_t); \
113 scope int prefix##free(void *, heaptype *); \
114 scope int prefix##is_full(heaptype const); \
115 scope size_t prefix##size(heaptype const); \
116 scope size_t prefix##used(heaptype const); \
117 scope void prefix##sort(heaptype); \
118 scope int prefix##add(heaptype, type); \
119 scope type prefix##remove(heaptype, size_t); \
120 scope type prefix##get(heaptype, size_t)
162 #define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
163 scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
165 struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
166 struct prefix##priv *_priv; \
168 (offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
169 size_t _min_size = 32 - _offset; \
173 _priv = *(void **)h; \
177 new_size = 2 * _priv->_size + _offset + 1; \
178 _used = _priv->_used; \
179 if (new_size < _used) \
183 if (new_size < _min_size) \
184 new_size = _min_size; \
186 _bytes = (_offset + 1 + new_size) * sizeof (type); \
189 _priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
193 *(struct prefix##priv **)h = _priv; \
194 _priv->_size = new_size; \
195 _priv->_used = _used; \
201 scope int prefix##free(void *realloc_arg, heaptype h[1]) \
204 *(void **)h = alloc(realloc_arg, *(void **)h, 0); \
209 scope int prefix##is_full(heaptype h) \
211 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
212 struct prefix##priv *_priv = *(void **)&h; \
214 return _priv == NULL || _priv->_used >= _priv->_size; \
218 scope int prefix##add(heaptype h, type e) \
220 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
221 struct prefix##priv *_priv = *(void **)&h; \
222 type *heap = _priv->_heap - 1; \
225 if (_priv == NULL || _priv->_used >= _priv->_size) \
228 for (i = ++_priv->_used; i > 1; i = parent) { \
230 if (!less(e, heap[parent])) \
232 set(heap, i, heap[parent]); \
241 scope type prefix##remove(heaptype h, size_t index) \
243 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
244 struct prefix##priv *_priv = *(void **)&h; \
245 type *heap = _priv->_heap - 1; \
249 size_t top, left, right, move; \
251 if (index - 1 >= _priv->_used) \
254 move = _priv->_used--; \
255 set(retval, 0, heap[index]); \
257 for (top = index;;index = top) { \
259 right = 2 * top + 1; \
263 if (right < move && less(heap[right], heap[left])) \
267 set(heap, index, heap[top]); \
274 for (; index > 1; index = top) { \
276 if (!less(e, heap[top])) \
278 set(heap, index, heap[top]); \
281 set(heap, index, e); \
287 type prefix##get(heaptype h, size_t index) \
289 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
290 struct prefix##priv *_priv = *(void **)&h; \
292 if (--index >= _priv->_used) \
295 return _priv->_heap[index]; \
299 size_t prefix##size(heaptype const h) \
301 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
302 struct prefix##priv *_priv = *(void **)&h; \
303 return _priv ? _priv->_size : 0; \
307 size_t prefix##used(heaptype const h) \
309 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
310 struct prefix##priv *_priv = *(void **)&h; \
311 return _priv ? _priv->_used : 0; \
313 static int prefix##_less(void *h, size_t a, size_t b) \
315 type *_heap = h; return less(_heap[a], _heap[b]); \
317 static void prefix##_swap(void *h, size_t a, size_t b) \
319 type *_heap = h; type _swap = _heap[a]; \
320 set(_heap, a, _heap[b]); set(_heap, b, _swap); \
322 scope void prefix##sort(heaptype h) \
324 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
325 struct prefix##priv *_priv = *(void **)&h; \
327 su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
329 extern int const prefix##dummy_heap
336 int (*less)(
void *base,
size_t a,
size_t b),
337 void (*swap)(
void *base,
size_t a,
size_t b));
Sofia-SIP 1.12.11devel -
Copyright (C) 2006 Nokia Corporation. All rights reserved.
Licensed under the terms of the GNU Lesser General Public License.