]>
Commit | Line | Data |
---|---|---|
ad19eafb | 1 | /* |
262a0e14 | 2 | * $Id$ |
ad19eafb | 3 | * |
4 | * AUTHOR: John Dilley, Hewlett Packard | |
5 | * | |
2b6662ba | 6 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
7 | * ---------------------------------------------------------- | |
ad19eafb | 8 | * |
2b6662ba | 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. | |
ad19eafb | 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. | |
c5dd4956 | 22 | * |
ad19eafb | 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. | |
c5dd4956 | 27 | * |
ad19eafb | 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. | |
c5dd4956 | 31 | * |
ad19eafb | 32 | */ |
33 | ||
34 | /**************************************************************************** | |
9bc73deb | 35 | * Copyright (C) 1999 by Hewlett Packard |
36 | * | |
ad19eafb | 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 | ****************************************************************************/ | |
b5638623 | 43 | #ifndef SQUID_HEAP_H |
44 | #define SQUID_HEAP_H | |
ad19eafb | 45 | |
e1f7507e AJ |
46 | /* Squid autoconf definitions */ |
47 | #include "config.h" | |
48 | ||
ad19eafb | 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 | ||
c5dd4956 | 91 | /* |
ad19eafb | 92 | * Create and initialize a new heap. |
93 | */ | |
e6ccf245 | 94 | SQUIDCEXTERN heap *new_heap(int init_size, heap_key_func gen_key); |
ad19eafb | 95 | |
c5dd4956 | 96 | /* |
ad19eafb | 97 | * Delete a heap and clean up its memory. Does not delete what the heap |
98 | * nodes are pointing to! | |
99 | */ | |
e6ccf245 | 100 | SQUIDCEXTERN void delete_heap(heap *); |
ad19eafb | 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 | */ | |
e6ccf245 | 108 | SQUIDCEXTERN heap_node *heap_insert(heap *, heap_t dat); |
ad19eafb | 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 | */ | |
e6ccf245 | 114 | SQUIDCEXTERN heap_t heap_delete(heap *, heap_node * elm); |
ad19eafb | 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 | */ | |
e6ccf245 | 123 | SQUIDCEXTERN heap_t heap_update(heap *, heap_node * elm, heap_t dat); |
ad19eafb | 124 | |
c5dd4956 | 125 | /* |
ad19eafb | 126 | * Generate a heap key for a given data object. Alternative macro form: |
127 | */ | |
128 | #ifdef MACRO_DEBUG | |
e6ccf245 | 129 | SQUIDCEXTERN heap_key heap_gen_key(heap * hp, heap_t dat); |
ad19eafb | 130 | #else |
131 | #define heap_gen_key(hp,md) ((hp)->gen_key((md),(hp)->age)) | |
132 | #endif /* MACRO_DEBUG */ | |
133 | ||
134 | ||
c5dd4956 | 135 | /* |
ad19eafb | 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 | */ | |
e6ccf245 | 140 | SQUIDCEXTERN heap_t heap_extractmin(heap *); |
ad19eafb | 141 | |
c5dd4956 | 142 | /* |
ad19eafb | 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 | */ | |
e6ccf245 | 149 | SQUIDCEXTERN heap_t heap_extractlast(heap * hp); |
ad19eafb | 150 | |
c5dd4956 | 151 | /* |
ad19eafb | 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 | */ | |
e6ccf245 | 155 | SQUIDCEXTERN heap_key heap_peepminkey(heap *); |
156 | SQUIDCEXTERN heap_key heap_peepkey(heap *, int n); | |
ad19eafb | 157 | |
e6ccf245 | 158 | SQUIDCEXTERN heap_t heap_peepmin(heap *); |
159 | SQUIDCEXTERN heap_t heap_peep(heap *, int n); | |
ad19eafb | 160 | |
c5dd4956 AJ |
161 | /* |
162 | * Is the heap empty? How many nodes (data objects) are in it? | |
ad19eafb | 163 | */ |
164 | #ifdef MACRO_DEBUG | |
e6ccf245 | 165 | SQUIDCEXTERN int heap_empty(heap *); |
166 | SQUIDCEXTERN int heap_nodes(heap *); | |
ad19eafb | 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 | ||
c5dd4956 | 172 | /* |
ad19eafb | 173 | * Print the heap or a node in the heap. |
174 | */ | |
e6ccf245 | 175 | SQUIDCEXTERN void heap_print(heap *); |
176 | SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm); | |
ad19eafb | 177 | |
e6ccf245 | 178 | SQUIDCEXTERN int verify_heap_property(heap *); |
ad19eafb | 179 | |
b5638623 | 180 | #endif /* SQUID_HEAP_H */ |