su
1.12.11devel
Loading...
Searching...
No Matches
libsofia-sip-ua
su
sofia-sip
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) \
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)
121
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) \
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
\
201
scope 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
\
209
scope 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
\
218
scope 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
\
241
scope 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
\
286
scope \
287
type 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
\
298
scope \
299
size_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
\
306
scope \
307
size_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
} \
313
static int prefix##_less(void *h, size_t a, size_t b) \
314
{ \
315
type *_heap = h; return less(_heap[a], _heap[b]); \
316
} \
317
static 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
} \
322
scope 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
} \
329
extern int const prefix##dummy_heap
330
331
#include <
sofia-sip/su_types.h
>
332
333
SOFIA_BEGIN_DECLS
334
335
SOFIAPUBFUN
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
339
SOFIA_END_DECLS
340
341
#endif
SOFIAPUBFUN
#define SOFIAPUBFUN
SOFIAPUBFUN declares an exported function.
Definition
su_config.h:66
su_types.h
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.