include/heap.h

   1 /*
   2  * Copyright (C) 1996-2018 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 /*
  10  * AUTHOR: John Dilley, Hewlett Packard
  11  */
  12
  13 /****************************************************************************
  14  * Copyright (C) 1999 by Hewlett Packard
  15  *
  16  * Heap data structure.  Used to store objects for cache replacement.  The
  17  * heap is implemented as a contiguous array in memory.  Heap sort and heap
  18  * update are done in-place.  The heap is ordered with the smallest value at
  19  * the top of the heap (as in the smallest object key value).  Child nodes
  20  * are larger than their parent.
  21  ****************************************************************************/
  22 #ifndef SQUID_HEAP_H
  23 #define SQUID_HEAP_H
  24
  25 /*
  26  * Function for generating heap keys.  The first argument will typically be
  27  * a dws_md_p passed in as a void *.  Should find a way to get type safety
  28  * without having heap know all about metadata objects...  The second arg is
  29  * the current aging factor for the heap.
  30  */
  31 typedef unsigned long heap_mutex_t;
  32 typedef void * heap_t;
  33 typedef double heap_key;
  34 typedef heap_key heap_key_func(heap_t, heap_key);
  35
  36 /*
  37  * Heap node.  Has a key value generated by a key_func, id (array index) so
  38  * it can be quickly found in its heap, and a pointer to a data object that
  39  * key_func can generate a key from.
  40  */
  41 typedef struct _heap_node {
  42     heap_key key;
  43     unsigned long id;
  44     heap_t data;
  45 } heap_node;
  46
  47 /*
  48  * Heap object.  Holds an array of heap_node objects along with a heap size
  49  * (array length), the index of the last heap element, and a key generation
  50  * function.  Also stores aging factor for this heap.
  51  */
  52 typedef struct _heap {
  53     heap_mutex_t lock;
  54     unsigned long size;
  55     unsigned long last;
  56     heap_key_func *gen_key; /* key generator for heap */
  57     heap_key age;       /* aging factor for heap */
  58     heap_node **nodes;
  59 } heap;
  60
  61 /****************************************************************************
  62  * Public functions
  63  ****************************************************************************/
  64
  65 /*
  66  * Create and initialize a new heap.
  67  */
  68 SQUIDCEXTERN heap *new_heap(int init_size, heap_key_func gen_key);
  69
  70 /*
  71  * Delete a heap and clean up its memory.  Does not delete what the heap
  72  * nodes are pointing to!
  73  */
  74 SQUIDCEXTERN void delete_heap(heap *);
  75
  76 /*
  77  * Insert a new node into a heap, returning a pointer to it.  The heap_node
  78  * object returned is used to update or delete a heap object.  Nothing else
  79  * should be done with this data structure (especially modifying it!)  The
  80  * heap does not assume ownership of the data passed to it.
  81  */
  82 SQUIDCEXTERN heap_node *heap_insert(heap *hp, heap_t dat);
  83
  84 /*
  85  * Delete a node out of a heap.  Returns the heap data from the deleted
  86  * node.  The caller is responsible for freeing this data.
  87  */
  88 SQUIDCEXTERN heap_t heap_delete(heap *, heap_node * elm);
  89
  90 /*
  91  * The semantics of this routine is the same as the followings:
  92  *        heap_delete(hp, elm);
  93  *        heap_insert(hp, dat);
  94  * Returns the old data object from elm (the one being replaced).  The
  95  * caller must free this as necessary.
  96  */
  97 SQUIDCEXTERN heap_t heap_update(heap *, heap_node * elm, heap_t dat);
  98
  99 /*
 100  * Generate a heap key for a given data object.  Alternative macro form:
 101  */
 102 #ifdef  MACRO_DEBUG
 103 SQUIDCEXTERN heap_key heap_gen_key(heap * hp, heap_t dat);
 104 #else
 105 #define heap_gen_key(hp,md) ((hp)->gen_key((md),(hp)->age))
 106 #endif /* MACRO_DEBUG */
 107
 108 /*
 109  * Extract the minimum (root) element and maintain the heap property.
 110  * Returns the data pointed to by the root node, which the caller must
 111  * free as necessary.
 112  */
 113 SQUIDCEXTERN heap_t heap_extractmin(heap *);
 114
 115 /*
 116  * Extract the last leaf node (does not change the heap property).
 117  * Returns the data that had been in the heap which the caller must free if
 118  * necessary.  Note that the last node is guaranteed to be less than its
 119  * parent, but may not be less than any of the other (leaf or parent) notes
 120  * in the tree.  This operation is fast but imprecise.
 121  */
 122 SQUIDCEXTERN heap_t heap_extractlast(heap * hp);
 123
 124 /*
 125  * Get the root key, the nth key, the root (smallest) element, or the nth
 126  * element.  None of these operations modify the heap.
 127  */
 128 SQUIDCEXTERN heap_key heap_peepminkey(heap *);
 129 SQUIDCEXTERN heap_key heap_peepkey(heap *, int n);
 130
 131 SQUIDCEXTERN heap_t heap_peepmin(heap *);
 132 SQUIDCEXTERN heap_t heap_peep(heap *, int n);
 133
 134 /*
 135  * Is the heap empty?  How many nodes (data objects) are in it?
 136  */
 137 #ifdef  MACRO_DEBUG
 138 SQUIDCEXTERN int heap_empty(heap *);
 139 SQUIDCEXTERN int heap_nodes(heap *);
 140 #else /* MACRO_DEBUG */
 141 #define heap_nodes(heap)    ((heap)->last)
 142 #define heap_empty(heap)    ((heap)->last <= 0 ? 1 : 0)
 143 #endif /* MACRO_DEBUG */
 144
 145 /*
 146  * Print the heap or a node in the heap.
 147  */
 148 SQUIDCEXTERN void heap_print(heap *);
 149 SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm);
 150
 151 SQUIDCEXTERN int verify_heap_property(heap *);
 152
 153 #endif /* SQUID_HEAP_H */
 154