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