00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
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
00161 #define HEAP_BODIES(scope, heaptype, prefix, type, less, set, alloc, null) \
00162 scope int prefix##resize(void *realloc_arg, heaptype h[1], size_t new_size) \
00163 { \
00164 struct prefix##priv { size_t _size, _used; type _heap[2]; }; \
00165 struct prefix##priv *_priv; \
00166 size_t _offset = \
00167 (offsetof(struct prefix##priv, _heap[1]) - 1) / sizeof (type); \
00168 size_t _min_size = 32 - _offset; \
00169 size_t _bytes; \
00170 size_t _used = 0; \
00171 \
00172 _priv = *(void **)h; \
00173 \
00174 if (_priv) { \
00175 if (new_size == 0) \
00176 new_size = 2 * _priv->_size + _offset + 1; \
00177 _used = _priv->_used; \
00178 if (new_size < _used) \
00179 new_size = _used; \
00180 } \
00181 \
00182 if (new_size < _min_size) \
00183 new_size = _min_size; \
00184 \
00185 _bytes = (_offset + 1 + new_size) * sizeof (type); \
00186 \
00187 (void)realloc_arg; \
00188 _priv = alloc(realloc_arg, *(struct prefix##priv **)h, _bytes); \
00189 if (!_priv) \
00190 return -1; \
00191 \
00192 *(struct prefix##priv **)h = _priv; \
00193 _priv->_size = new_size; \
00194 _priv->_used = _used; \
00195 \
00196 return 0; \
00197 } \
00198 \
00199 \
00200 scope int prefix##free(void *realloc_arg, heaptype h[1]) \
00201 { \
00202 (void)realloc_arg; \
00203 *(void **)h = alloc(realloc_arg, *(void **)h, 0); \
00204 return 0; \
00205 } \
00206 \
00207 \
00208 scope int prefix##is_full(heaptype h) \
00209 { \
00210 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00211 struct prefix##priv *_priv = *(void **)&h; \
00212 \
00213 return _priv == NULL || _priv->_used >= _priv->_size; \
00214 } \
00215 \
00216 \
00217 scope int prefix##add(heaptype h, type e) \
00218 { \
00219 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00220 struct prefix##priv *_priv = *(void **)&h; \
00221 type *heap = _priv->_heap - 1; \
00222 size_t i, parent; \
00223 \
00224 if (_priv == NULL || _priv->_used >= _priv->_size) \
00225 return -1; \
00226 \
00227 for (i = ++_priv->_used; i > 1; i = parent) { \
00228 parent = i / 2; \
00229 if (!less(e, heap[parent])) \
00230 break; \
00231 set(heap, i, heap[parent]); \
00232 } \
00233 \
00234 set(heap, i, e); \
00235 \
00236 return 0; \
00237 } \
00238 \
00239 \
00240 scope type prefix##remove(heaptype h, size_t index) \
00241 { \
00242 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00243 struct prefix##priv *_priv = *(void **)&h; \
00244 type *heap = _priv->_heap - 1; \
00245 type retval[1]; \
00246 type e; \
00247 \
00248 size_t top, left, right, move; \
00249 \
00250 if (index - 1 >= _priv->_used) \
00251 return (null); \
00252 \
00253 move = _priv->_used--; \
00254 set(retval, 0, heap[index]); \
00255 \
00256 for (top = index;;index = top) { \
00257 left = 2 * top; \
00258 right = 2 * top + 1; \
00259 \
00260 if (left >= move) \
00261 break; \
00262 if (right < move && less(heap[right], heap[left])) \
00263 top = right; \
00264 else \
00265 top = left; \
00266 set(heap, index, heap[top]); \
00267 } \
00268 \
00269 if (index == move) \
00270 return *retval; \
00271 \
00272 e = heap[move]; \
00273 for (; index > 1; index = top) { \
00274 top = index / 2; \
00275 if (!less(e, heap[top])) \
00276 break; \
00277 set(heap, index, heap[top]); \
00278 } \
00279 \
00280 set(heap, index, e); \
00281 \
00282 return *retval; \
00283 } \
00284 \
00285 scope \
00286 type prefix##get(heaptype h, size_t index) \
00287 { \
00288 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00289 struct prefix##priv *_priv = *(void **)&h; \
00290 \
00291 if (--index >= _priv->_used) \
00292 return (null); \
00293 \
00294 return _priv->_heap[index]; \
00295 } \
00296 \
00297 scope \
00298 size_t prefix##size(heaptype const h) \
00299 { \
00300 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00301 struct prefix##priv *_priv = *(void **)&h; \
00302 return _priv ? _priv->_size : 0; \
00303 } \
00304 \
00305 scope \
00306 size_t prefix##used(heaptype const h) \
00307 { \
00308 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00309 struct prefix##priv *_priv = *(void **)&h; \
00310 return _priv ? _priv->_used : 0; \
00311 } \
00312 scope int prefix##_less(void *h, size_t a, size_t b) \
00313 { \
00314 type *_heap = h; return less(_heap[a], _heap[b]); \
00315 } \
00316 scope void prefix##_swap(void *h, size_t a, size_t b) \
00317 { \
00318 type *_heap = h; type _swap = _heap[a]; \
00319 set(_heap, a, _heap[b]); set(_heap, b, _swap); \
00320 } \
00321 void su_smoothsort(void *base, size_t r0, size_t N, \
00322 int (*less)(void *base, size_t a, size_t b), \
00323 void (*swap)(void *base, size_t a, size_t b)); \
00324 scope void prefix##sort(heaptype h) \
00325 { \
00326 struct prefix##priv { size_t _size, _used; type _heap[1];}; \
00327 struct prefix##priv *_priv = *(void **)&h; \
00328 if (_priv) \
00329 su_smoothsort(_priv->_heap - 1, 1, _priv->_used, prefix##_less, prefix##_swap); \
00330 } \
00331 extern int const prefix##dummy_heap
00332
00333 #endif