1/* 2 * Copyright (c) 1998 Kungliga Tekniska H�gskolan 3 * (Royal Institute of Technology, Stockholm, Sweden). 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * 3. Neither the name of the Institute nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34/* 35 * an abstract heap implementation 36 */ 37 38#ifndef _HEIM_HEAP_H 39#define _HEIM_HEAP_H 1 40 41typedef int (*heap_cmp_fn)(const void *, const void *); 42 43typedef unsigned heap_ptr; 44 45#define HEAP_INVALID_PTR ((heap_ptr)-1) 46 47struct heap_element { 48 const void *data; 49 heap_ptr *ptr; 50}; 51 52typedef struct heap_element heap_element; 53 54typedef struct heap Heap; 55 56Heap *heap_new (unsigned sz, heap_cmp_fn cmp); 57 58int 59heap_insert (Heap *h, const void *data, heap_ptr *ptr); 60 61const void * 62heap_head (Heap *h); 63 64void 65heap_remove_head (Heap *h); 66 67int 68heap_remove (Heap *h, heap_ptr ptr); 69 70void 71heap_delete (Heap *h); 72 73int 74heap_verify (Heap *h); 75 76#endif /* _HEIM_HEAP_H */ 77