Loading...
Searching...
No Matches
heap.h
Go to the documentation of this file.
/*
* This file is part of the Sofia-SIP package
*
* Copyright (C) 2007 Nokia Corporation.
*
* Contact: Pekka Pessi <pekka.pessi@nokia-email.address.hidden>
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public License
* as published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
* 02110-1301 USA
*
*/
#ifndef SOFIA_SIP_HEAP_H
#define SOFIA_SIP_HEAP_H
#define HEAP_MIN_SIZE 31
#define HEAP_TYPE struct { void *private; }
#define HEAP_DECLARE(scope, heaptype, prefix, type) \
scope int prefix##resize(void *, heaptype *, size_t); \
scope int prefix##free(void *, heaptype *); \
scope int prefix##is_full(heaptype const); \
scope size_t prefix##size(heaptype const); \
scope size_t prefix##used(heaptype const); \
scope void prefix##sort(heaptype); \
scope int prefix##add(heaptype, type); \
scope type prefix##remove(heaptype, size_t); \
scope type prefix##get(heaptype, size_t)
#define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
struct prefix##priv *_priv; \
size_t _offset = \
(offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
size_t _min_size = 32 - _offset; \
size_t _bytes; \
size_t _used = 0; \
\
_priv = *(void **)h; \
\
if (_priv) { \
if (new_size == 0) \
new_size = 2 * _priv->_size + _offset + 1; \
_used = _priv->_used; \
if (new_size < _used) \
new_size = _used; \
} \
\
if (new_size < _min_size) \
new_size = _min_size; \
\
_bytes = (_offset + 1 + new_size) * sizeof (type); \
\
(void)realloc_arg; /* avoid warning */ \
_priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
if (!_priv) \
return -1; \
\
*(struct prefix##priv **)h = _priv; \
_priv->_size = new_size; \
_priv->_used = _used; \
\
return 0; \
} \
\
\
scope int prefix##free(void *realloc_arg, heaptype h[1]) \
{ \
(void)realloc_arg; \
*(void **)h = alloc(realloc_arg, *(void **)h, 0); \
return 0; \
} \
\
\
scope int prefix##is_full(heaptype h) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
\
return _priv == NULL || _priv->_used >= _priv->_size; \
} \
\
\
scope int prefix##add(heaptype h, type e) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
type *heap = _priv->_heap - 1; \
size_t i, parent; \
\
if (_priv == NULL || _priv->_used >= _priv->_size) \
return -1; \
\
for (i = ++_priv->_used; i > 1; i = parent) { \
parent = i / 2; \
if (!less(e, heap[parent])) \
break; \
set(heap, i, heap[parent]); \
} \
\
set(heap, i, e); \
\
return 0; \
} \
\
\
scope type prefix##remove(heaptype h, size_t index) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
type *heap = _priv->_heap - 1; \
type retval[1]; \
type e; \
\
size_t top, left, right, move; \
\
if (index - 1 >= _priv->_used) \
return (null); \
\
move = _priv->_used--; \
set(retval, 0, heap[index]); \
\
for (top = index;;index = top) { \
left = 2 * top; \
right = 2 * top + 1; \
\
if (left >= move) \
break; \
if (right < move && less(heap[right], heap[left])) \
top = right; \
else \
top = left; \
set(heap, index, heap[top]); \
} \
\
if (index == move) \
return *retval; \
\
e = heap[move]; \
for (; index > 1; index = top) { \
top = index / 2; \
if (!less(e, heap[top])) \
break; \
set(heap, index, heap[top]); \
} \
\
set(heap, index, e); \
\
return *retval; \
} \
\
scope \
type prefix##get(heaptype h, size_t index) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
\
if (--index >= _priv->_used) \
return (null); \
\
return _priv->_heap[index]; \
} \
\
scope \
size_t prefix##size(heaptype const h) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
return _priv ? _priv->_size : 0; \
} \
\
scope \
size_t prefix##used(heaptype const h) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
return _priv ? _priv->_used : 0; \
} \
static int prefix##_less(void *h, size_t a, size_t b) \
{ \
type *_heap = h; return less(_heap[a], _heap[b]); \
} \
static void prefix##_swap(void *h, size_t a, size_t b) \
{ \
type *_heap = h; type _swap = _heap[a]; \
set(_heap, a, _heap[b]); set(_heap, b, _swap); \
} \
scope void prefix##sort(heaptype h) \
{ \
struct prefix##priv { size_t _size, _used; type _heap[1];}; \
struct prefix##priv *_priv = *(void **)&h; \
if (_priv) \
su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
} \
extern int const prefix##dummy_heap
#include <sofia-sip/su_types.h>
SOFIA_BEGIN_DECLS
SOFIAPUBFUN void su_smoothsort(void *base, size_t r0, size_t N,
int (*less)(void *base, size_t a, size_t b),
void (*swap)(void *base, size_t a, size_t b));
SOFIA_END_DECLS
#endif
su_smoothsort
void su_smoothsort(void *base, size_t r0, size_t N, int(*less)(void *base, size_t a, size_t b), void(*swap)(void *base, size_t a, size_t b))
Sort array using smoothsort.
Definition foo.c:213
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.