su
1.12.11
|
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 static int prefix##_less(void *h, size_t a, size_t b) \ 00314 { \ 00315 type *_heap = h; return less(_heap[a], _heap[b]); \ 00316 } \ 00317 static 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 scope void prefix##sort(heaptype h) \ 00323 { \ 00324 struct prefix##priv { size_t _size, _used; type _heap[1];}; \ 00325 struct prefix##priv *_priv = *(void **)&h; \ 00326 if (_priv) \ 00327 su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \ 00328 } \ 00329 extern int const prefix##dummy_heap 00330 00331 #include <sofia-sip/su_types.h> 00332 00333 SOFIA_BEGIN_DECLS 00334 00335 SOFIAPUBFUN void su_smoothsort(void *base, size_t r0, size_t N, 00336 int (*less)(void *base, size_t a, size_t b), 00337 void (*swap)(void *base, size_t a, size_t b)); 00338 00339 SOFIA_END_DECLS 00340 00341 #endif