include/heap.h

   1 /*
   2  * $Id$
   3  *
   4  * AUTHOR: John Dilley, Hewlett Packard
   5  *
   6  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   7  * ----------------------------------------------------------
   8  *
   9  *  Squid is the result of efforts by numerous individuals from
  10  *  the Internet community; see the CONTRIBUTORS file for full
  11  *  details.   Many organizations have provided support for Squid's
  12  *  development; see the SPONSORS file for full details.  Squid is
  13  *  Copyrighted (C) 2001 by the Regents of the University of
  14  *  California; see the COPYRIGHT file for full details.  Squid
  15  *  incorporates software developed and/or copyrighted by other
  16  *  sources; see the CREDITS file for full details.
  17  *
  18  *  This program is free software; you can redistribute it and/or modify
  19  *  it under the terms of the GNU General Public License as published by
  20  *  the Free Software Foundation; either version 2 of the License, or
  21  *  (at your option) any later version.
  22  *
  23  *  This program is distributed in the hope that it will be useful,
  24  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  26  *  GNU General Public License for more details.
  27  *
  28  *  You should have received a copy of the GNU General Public License
  29  *  along with this program; if not, write to the Free Software
  30  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  31  *
  32  */
  33
  34 /****************************************************************************
  35  * Copyright (C) 1999 by Hewlett Packard
  36  *
  37  * Heap data structure.  Used to store objects for cache replacement.  The
  38  * heap is implemented as a contiguous array in memory.  Heap sort and heap
  39  * update are done in-place.  The heap is ordered with the smallest value at
  40  * the top of the heap (as in the smallest object key value).  Child nodes
  41  * are larger than their parent.
  42  ****************************************************************************/
  43 #ifndef SQUID_HEAP_H
  44 #define SQUID_HEAP_H
  45
  46 /* Squid autoconf definitions */
  47 #include "config.h"
  48
  49 /*
  50  * Function for generating heap keys.  The first argument will typically be
  51  * a dws_md_p passed in as a void *.  Should find a way to get type safety
  52  * without having heap know all about metadata objects...  The second arg is
  53  * the current aging factor for the heap.
  54  */
  55 typedef unsigned long heap_mutex_t;
  56 typedef void * heap_t;
  57 typedef double heap_key;
  58 typedef heap_key heap_key_func(heap_t, heap_key);
  59
  60
  61 /*
  62  * Heap node.  Has a key value generated by a key_func, id (array index) so
  63  * it can be quickly found in its heap, and a pointer to a data object that
  64  * key_func can generate a key from.
  65  */
  66 typedef struct _heap_node {
  67     heap_key key;
  68     unsigned long id;
  69     heap_t data;
  70 } heap_node;
  71
  72
  73 /*
  74  * Heap object.  Holds an array of heap_node objects along with a heap size
  75  * (array length), the index of the last heap element, and a key generation
  76  * function.  Also stores aging factor for this heap.
  77  */
  78 typedef struct _heap {
  79     heap_mutex_t lock;
  80     unsigned long size;
  81     unsigned long last;
  82     heap_key_func *gen_key;     /* key generator for heap */
  83     heap_key age;               /* aging factor for heap */
  84     heap_node **nodes;
  85 } heap;
  86
  87 /****************************************************************************
  88  * Public functions
  89  ****************************************************************************/
  90
  91 /*
  92  * Create and initialize a new heap.
  93  */
  94 SQUIDCEXTERN heap *new_heap(int init_size, heap_key_func gen_key);
  95
  96 /*
  97  * Delete a heap and clean up its memory.  Does not delete what the heap
  98  * nodes are pointing to!
  99  */
 100 SQUIDCEXTERN void delete_heap(heap *);
 101
 102 /*
 103  * Insert a new node into a heap, returning a pointer to it.  The heap_node
 104  * object returned is used to update or delete a heap object.  Nothing else
 105  * should be done with this data structure (especially modifying it!)  The
 106  * heap does not assume ownership of the data passed to it.
 107  */
 108 SQUIDCEXTERN heap_node *heap_insert(heap *hp, heap_t dat);
 109
 110 /*
 111  * Delete a node out of a heap.  Returns the heap data from the deleted
 112  * node.  The caller is responsible for freeing this data.
 113  */
 114 SQUIDCEXTERN heap_t heap_delete(heap *, heap_node * elm);
 115
 116 /*
 117  * The semantics of this routine is the same as the followings:
 118  *        heap_delete(hp, elm);
 119  *        heap_insert(hp, dat);
 120  * Returns the old data object from elm (the one being replaced).  The
 121  * caller must free this as necessary.
 122  */
 123 SQUIDCEXTERN heap_t heap_update(heap *, heap_node * elm, heap_t dat);
 124
 125 /*
 126  * Generate a heap key for a given data object.  Alternative macro form:
 127  */
 128 #ifdef  MACRO_DEBUG
 129 SQUIDCEXTERN heap_key heap_gen_key(heap * hp, heap_t dat);
 130 #else
 131 #define heap_gen_key(hp,md)     ((hp)->gen_key((md),(hp)->age))
 132 #endif /* MACRO_DEBUG */
 133
 134
 135 /*
 136  * Extract the minimum (root) element and maintain the heap property.
 137  * Returns the data pointed to by the root node, which the caller must
 138  * free as necessary.
 139  */
 140 SQUIDCEXTERN heap_t heap_extractmin(heap *);
 141
 142 /*
 143  * Extract the last leaf node (does not change the heap property).
 144  * Returns the data that had been in the heap which the caller must free if
 145  * necessary.  Note that the last node is guaranteed to be less than its
 146  * parent, but may not be less than any of the other (leaf or parent) notes
 147  * in the tree.  This operation is fast but imprecise.
 148  */
 149 SQUIDCEXTERN heap_t heap_extractlast(heap * hp);
 150
 151 /*
 152  * Get the root key, the nth key, the root (smallest) element, or the nth
 153  * element.  None of these operations modify the heap.
 154  */
 155 SQUIDCEXTERN heap_key heap_peepminkey(heap *);
 156 SQUIDCEXTERN heap_key heap_peepkey(heap *, int n);
 157
 158 SQUIDCEXTERN heap_t heap_peepmin(heap *);
 159 SQUIDCEXTERN heap_t heap_peep(heap *, int n);
 160
 161 /*
 162  * Is the heap empty?  How many nodes (data objects) are in it?
 163  */
 164 #ifdef  MACRO_DEBUG
 165 SQUIDCEXTERN int heap_empty(heap *);
 166 SQUIDCEXTERN int heap_nodes(heap *);
 167 #else /* MACRO_DEBUG */
 168 #define heap_nodes(heap)        ((heap)->last)
 169 #define heap_empty(heap)        (((heap)->last <= 0) ? 1 : 0)
 170 #endif /* MACRO_DEBUG */
 171
 172 /*
 173  * Print the heap or a node in the heap.
 174  */
 175 SQUIDCEXTERN void heap_print(heap *);
 176 SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm);
 177
 178 SQUIDCEXTERN int verify_heap_property(heap *);
 179
 180 #endif /* SQUID_HEAP_H */