heap.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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;
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 {
43  unsigned long id;
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 {
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 */
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  */
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  */
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  */
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  */
98 
99 /*
100  * Generate a heap key for a given data object. Alternative macro form:
101  */
102 #ifdef MACRO_DEBUG
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  */
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  */
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  */
130 
133 
134 /*
135  * Is the heap empty? How many nodes (data objects) are in it?
136  */
137 #ifdef MACRO_DEBUG
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  */
149 SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm);
150 
152 
153 #endif /* SQUID_HEAP_H */
154 
SQUIDCEXTERN heap_t heap_extractlast(heap *hp)
Definition: heap.c:210
SQUIDCEXTERN heap_t heap_peep(heap *, int n)
Definition: heap.c:281
double heap_key
Definition: heap.h:33
heap_key age
Definition: heap.h:57
heap_node ** nodes
Definition: heap.h:58
#define SQUIDCEXTERN
Definition: squid.h:26
SQUIDCEXTERN heap_key heap_peepminkey(heap *)
Definition: heap.c:257
struct _heap heap
#define heap_nodes(heap)
Definition: heap.h:141
SQUIDCEXTERN void heap_print(heap *)
heap_key key
Definition: heap.h:42
SQUIDCEXTERN heap_t heap_update(heap *, heap_node *elm, heap_t dat)
Definition: heap.c:228
unsigned long size
Definition: heap.h:54
heap_mutex_t lock
Definition: heap.h:53
heap_t data
Definition: heap.h:44
SQUIDCEXTERN int verify_heap_property(heap *)
Definition: heap.c:455
SQUIDCEXTERN heap_t heap_extractmin(heap *)
Definition: heap.c:188
struct _heap_node heap_node
SQUIDCEXTERN void heap_printnode(char *msg, heap_node *elm)
#define heap_gen_key(hp, md)
Definition: heap.h:105
unsigned long id
Definition: heap.h:43
SQUIDCEXTERN heap * new_heap(int init_size, heap_key_func gen_key)
Definition: heap.c:72
heap_key heap_key_func(heap_t, heap_key)
Definition: heap.h:34
SQUIDCEXTERN heap_node * heap_insert(heap *hp, heap_t dat)
Definition: heap.c:117
#define heap_empty(heap)
Definition: heap.h:142
Definition: heap.h:52
SQUIDCEXTERN heap_key heap_peepkey(heap *, int n)
Definition: heap.c:268
SQUIDCEXTERN void delete_heap(heap *)
Definition: heap.c:95
heap_key_func * gen_key
Definition: heap.h:56
SQUIDCEXTERN heap_t heap_peepmin(heap *)
Definition: heap.c:247
unsigned long heap_mutex_t
Definition: heap.h:31
unsigned long last
Definition: heap.h:55
void * heap_t
Definition: heap.h:32
SQUIDCEXTERN heap_t heap_delete(heap *, heap_node *elm)
Definition: heap.c:142

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors