su 1.12.10

sofia-sip/heap.h

Go to the documentation of this file.
00001 /*
00002  * This file is part of the Sofia-SIP package
00003  *
00004  * Copyright (C) 2007 Nokia Corporation.
00005  *
00006  * Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden>
00007  *
00008  * This library is free software; you can redistribute it and/or
00009  * modify it under the terms of the GNU Lesser General Public License
00010  * as published by the Free Software Foundation; either version 2.1 of
00011  * the License, or (at your option) any later version.
00012  *
00013  * This library is distributed in the hope that it will be useful, but
00014  * WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
00016  * Lesser General Public License for more details.
00017  *
00018  * You should have received a copy of the GNU Lesser General Public
00019  * License along with this library; if not, write to the Free Software
00020  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
00021  * 02110-1301 USA
00022  *
00023  */
00024 
00025 #ifndef SOFIA_SIP_HEAP_H
00026 
00027 #define SOFIA_SIP_HEAP_H
00028 
00077 #define HEAP_MIN_SIZE 31
00078 
00085 #define HEAP_TYPE struct { void *private; }
00086 
00111 #define HEAP_DECLARE(scope, heaptype, prefix, type) \
00112 scope int prefix##resize(void *, heaptype *, size_t); \
00113 scope int prefix##free(void *, heaptype *); \
00114 scope int prefix##is_full(heaptype const); \
00115 scope size_t prefix##size(heaptype const); \
00116 scope size_t prefix##used(heaptype const); \
00117 scope void prefix##sort(heaptype); \
00118 scope int prefix##add(heaptype, type); \
00119 scope type prefix##remove(heaptype, size_t); \
00120 scope type prefix##get(heaptype, size_t)
00121 
00162 #define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
00163 scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
00164 { \
00165   struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
00166   struct prefix##priv *_priv; \
00167   size_t _offset = \
00168     (offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
00169   size_t _min_size = 32 - _offset; \
00170   size_t _bytes; \
00171   size_t _used = 0; \
00172  \
00173   _priv = *(void **)h; \
00174  \
00175   if (_priv) { \
00176     if (new_size == 0) \
00177       new_size = 2 * _priv->_size + _offset + 1; \
00178     _used = _priv->_used; \
00179     if (new_size < _used) \
00180       new_size = _used; \
00181   } \
00182  \
00183   if (new_size < _min_size) \
00184     new_size = _min_size; \
00185  \
00186   _bytes = (_offset + 1 + new_size) * sizeof (type); \
00187  \
00188   (void)realloc_arg; /* avoid warning */ \
00189   _priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
00190   if (!_priv) \
00191     return -1; \
00192  \
00193   *(struct prefix##priv **)h = _priv; \
00194   _priv->_size = new_size; \
00195   _priv->_used = _used; \
00196  \
00197   return 0; \
00198 } \
00199  \
00200  \
00201 scope int prefix##free(void *realloc_arg, heaptype h[1]) \
00202 { \
00203   (void)realloc_arg; \
00204   *(void **)h = alloc(realloc_arg, *(void **)h, 0); \
00205   return 0; \
00206 } \
00207  \
00208  \
00209 scope int prefix##is_full(heaptype h) \
00210 { \
00211   struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00212   struct prefix##priv *_priv = *(void **)&h; \
00213  \
00214   return _priv == NULL || _priv->_used >= _priv->_size; \
00215 } \
00216  \
00217  \
00218 scope int prefix##add(heaptype h, type e) \
00219 { \
00220   struct prefix##priv { size_t _size, _used; type _heap[1];};   \
00221   struct prefix##priv *_priv = *(void **)&h; \
00222   type *heap = _priv->_heap - 1; \
00223   size_t i, parent; \
00224  \
00225   if (_priv == NULL || _priv->_used >= _priv->_size) \
00226     return -1; \
00227  \
00228   for (i = ++_priv->_used; i > 1; i = parent) { \
00229     parent = i / 2; \
00230     if (!less(e, heap[parent])) \
00231       break; \
00232     set(heap, i, heap[parent]); \
00233   } \
00234  \
00235   set(heap, i, e); \
00236  \
00237   return 0; \
00238 } \
00239  \
00240  \
00241 scope type prefix##remove(heaptype h, size_t index) \
00242 { \
00243   struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00244   struct prefix##priv *_priv = *(void **)&h; \
00245   type *heap = _priv->_heap - 1; \
00246   type retval[1]; \
00247   type e; \
00248  \
00249   size_t top, left, right, move; \
00250  \
00251   if (index - 1 >= _priv->_used) \
00252     return (null); \
00253  \
00254   move = _priv->_used--; \
00255   set(retval, 0, heap[index]); \
00256  \
00257   for (top = index;;index = top) { \
00258     left = 2 * top; \
00259     right = 2 * top + 1; \
00260  \
00261     if (left >= move) \
00262       break; \
00263     if (right < move && less(heap[right], heap[left])) \
00264       top = right; \
00265     else \
00266       top = left; \
00267     set(heap, index, heap[top]); \
00268   } \
00269  \
00270   if (index == move) \
00271     return *retval; \
00272  \
00273   e = heap[move]; \
00274   for (; index > 1; index = top) { \
00275     top = index / 2; \
00276     if (!less(e, heap[top])) \
00277       break; \
00278     set(heap, index, heap[top]); \
00279   } \
00280  \
00281   set(heap, index, e); \
00282  \
00283   return *retval; \
00284 } \
00285  \
00286 scope \
00287 type prefix##get(heaptype h, size_t index) \
00288 { \
00289   struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00290   struct prefix##priv *_priv = *(void **)&h; \
00291  \
00292   if (--index >= _priv->_used) \
00293     return (null); \
00294  \
00295   return _priv->_heap[index]; \
00296 } \
00297  \
00298 scope \
00299 size_t prefix##size(heaptype const h) \
00300 { \
00301   struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00302   struct prefix##priv *_priv = *(void **)&h; \
00303   return _priv ? _priv->_size : 0; \
00304 } \
00305  \
00306 scope \
00307 size_t prefix##used(heaptype const h) \
00308 { \
00309   struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00310   struct prefix##priv *_priv = *(void **)&h; \
00311   return _priv ? _priv->_used : 0; \
00312 } \
00313 scope int prefix##_less(void *h, size_t a, size_t b) \
00314 { \
00315   type *_heap = h; return less(_heap[a], _heap[b]);     \
00316 } \
00317 scope void prefix##_swap(void *h, size_t a, size_t b) \
00318 { \
00319   type *_heap = h; type _swap = _heap[a]; \
00320   set(_heap, a, _heap[b]); set(_heap, b, _swap); \
00321 } \
00322 void su_smoothsort(void *base, size_t r0, size_t N,             \
00323                    int (*less)(void *base, size_t a, size_t b), \
00324                    void (*swap)(void *base, size_t a, size_t b));       \
00325 scope void prefix##sort(heaptype h) \
00326 { \
00327   struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00328   struct prefix##priv *_priv = *(void **)&h; \
00329   if (_priv) \
00330     su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
00331 } \
00332 extern int const prefix##dummy_heap
00333 
00334 #endif 
 All Data Structures Files Functions Variables Typedefs Enumerator Defines

Sofia-SIP 1.12.10 - Copyright (C) 2006 Nokia Corporation. All rights reserved. Licensed under the terms of the GNU Lesser General Public License.