su 1.12.11devel
Loading...
Searching...
No Matches
heap.h
Go to the documentation of this file.
1/*
2 * This file is part of the Sofia-SIP package
3 *
4 * Copyright (C) 2007 Nokia Corporation.
5 *
6 * Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden>
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation; either version 2.1 of
11 * the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
21 * 02110-1301 USA
22 *
23 */
24
25#ifndef SOFIA_SIP_HEAP_H
27#define SOFIA_SIP_HEAP_H
28
77#define HEAP_MIN_SIZE 31
78
85#define HEAP_TYPE struct { void *private; }
86
111#define HEAP_DECLARE(scope, heaptype, prefix, type) \
112scope int prefix##resize(void *, heaptype *, size_t); \
113scope int prefix##free(void *, heaptype *); \
114scope int prefix##is_full(heaptype const); \
115scope size_t prefix##size(heaptype const); \
116scope size_t prefix##used(heaptype const); \
117scope void prefix##sort(heaptype); \
118scope int prefix##add(heaptype, type); \
119scope type prefix##remove(heaptype, size_t); \
120scope type prefix##get(heaptype, size_t)
121
162#define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
163scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
164{ \
165 struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
166 struct prefix##priv *_priv; \
167 size_t _offset = \
168 (offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
169 size_t _min_size = 32 - _offset; \
170 size_t _bytes; \
171 size_t _used = 0; \
172 \
173 _priv = *(void **)h; \
174 \
175 if (_priv) { \
176 if (new_size == 0) \
177 new_size = 2 * _priv->_size + _offset + 1; \
178 _used = _priv->_used; \
179 if (new_size < _used) \
180 new_size = _used; \
181 } \
182 \
183 if (new_size < _min_size) \
184 new_size = _min_size; \
185 \
186 _bytes = (_offset + 1 + new_size) * sizeof (type); \
187 \
188 (void)realloc_arg; /* avoid warning */ \
189 _priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
190 if (!_priv) \
191 return -1; \
192 \
193 *(struct prefix##priv **)h = _priv; \
194 _priv->_size = new_size; \
195 _priv->_used = _used; \
196 \
197 return 0; \
198} \
199 \
200 \
201scope int prefix##free(void *realloc_arg, heaptype h[1]) \
202{ \
203 (void)realloc_arg; \
204 *(void **)h = alloc(realloc_arg, *(void **)h, 0); \
205 return 0; \
206} \
207 \
208 \
209scope int prefix##is_full(heaptype h) \
210{ \
211 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
212 struct prefix##priv *_priv = *(void **)&h; \
213 \
214 return _priv == NULL || _priv->_used >= _priv->_size; \
215} \
216 \
217 \
218scope int prefix##add(heaptype h, type e) \
219{ \
220 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
221 struct prefix##priv *_priv = *(void **)&h; \
222 type *heap = _priv->_heap - 1; \
223 size_t i, parent; \
224 \
225 if (_priv == NULL || _priv->_used >= _priv->_size) \
226 return -1; \
227 \
228 for (i = ++_priv->_used; i > 1; i = parent) { \
229 parent = i / 2; \
230 if (!less(e, heap[parent])) \
231 break; \
232 set(heap, i, heap[parent]); \
233 } \
234 \
235 set(heap, i, e); \
236 \
237 return 0; \
238} \
239 \
240 \
241scope type prefix##remove(heaptype h, size_t index) \
242{ \
243 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
244 struct prefix##priv *_priv = *(void **)&h; \
245 type *heap = _priv->_heap - 1; \
246 type retval[1]; \
247 type e; \
248 \
249 size_t top, left, right, move; \
250 \
251 if (index - 1 >= _priv->_used) \
252 return (null); \
253 \
254 move = _priv->_used--; \
255 set(retval, 0, heap[index]); \
256 \
257 for (top = index;;index = top) { \
258 left = 2 * top; \
259 right = 2 * top + 1; \
260 \
261 if (left >= move) \
262 break; \
263 if (right < move && less(heap[right], heap[left])) \
264 top = right; \
265 else \
266 top = left; \
267 set(heap, index, heap[top]); \
268 } \
269 \
270 if (index == move) \
271 return *retval; \
272 \
273 e = heap[move]; \
274 for (; index > 1; index = top) { \
275 top = index / 2; \
276 if (!less(e, heap[top])) \
277 break; \
278 set(heap, index, heap[top]); \
279 } \
280 \
281 set(heap, index, e); \
282 \
283 return *retval; \
284} \
285 \
286scope \
287type prefix##get(heaptype h, size_t index) \
288{ \
289 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
290 struct prefix##priv *_priv = *(void **)&h; \
291 \
292 if (--index >= _priv->_used) \
293 return (null); \
294 \
295 return _priv->_heap[index]; \
296} \
297 \
298scope \
299size_t prefix##size(heaptype const h) \
300{ \
301 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
302 struct prefix##priv *_priv = *(void **)&h; \
303 return _priv ? _priv->_size : 0; \
304} \
305 \
306scope \
307size_t prefix##used(heaptype const h) \
308{ \
309 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
310 struct prefix##priv *_priv = *(void **)&h; \
311 return _priv ? _priv->_used : 0; \
312} \
313static int prefix##_less(void *h, size_t a, size_t b) \
314{ \
315 type *_heap = h; return less(_heap[a], _heap[b]); \
316} \
317static void prefix##_swap(void *h, size_t a, size_t b) \
318{ \
319 type *_heap = h; type _swap = _heap[a]; \
320 set(_heap, a, _heap[b]); set(_heap, b, _swap); \
321} \
322scope void prefix##sort(heaptype h) \
323{ \
324 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
325 struct prefix##priv *_priv = *(void **)&h; \
326 if (_priv) \
327 su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
328} \
329extern int const prefix##dummy_heap
330
331#include <sofia-sip/su_types.h>
332
333SOFIA_BEGIN_DECLS
334
335SOFIAPUBFUN void su_smoothsort(void *base, size_t r0, size_t N,
336 int (*less)(void *base, size_t a, size_t b),
337 void (*swap)(void *base, size_t a, size_t b));
338
339SOFIA_END_DECLS
340
341#endif
#define SOFIAPUBFUN
SOFIAPUBFUN declares an exported function.
Definition su_config.h:66
Basic integer types for su library.

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