]>
Commit | Line | Data |
---|---|---|
ad19eafb | 1 | /* |
b8ae064d | 2 | * Copyright (C) 1996-2023 The Squid Software Foundation and contributors |
c5dd4956 | 3 | * |
5c193dec AJ |
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 | |
ad19eafb | 11 | */ |
12 | ||
13 | /**************************************************************************** | |
9bc73deb | 14 | * Copyright (C) 1999 by Hewlett Packard |
15 | * | |
ad19eafb | 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 | ****************************************************************************/ | |
ff9d9458 FC |
22 | #ifndef SQUID_INCLUDE_HEAP_H |
23 | #define SQUID_INCLUDE_HEAP_H | |
ad19eafb | 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; | |
641ac151 | 32 | typedef void * heap_t; |
ad19eafb | 33 | typedef double heap_key; |
34 | typedef heap_key heap_key_func(heap_t, heap_key); | |
35 | ||
ad19eafb | 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 | ||
ad19eafb | 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; | |
f53969cc SM |
56 | heap_key_func *gen_key; /* key generator for heap */ |
57 | heap_key age; /* aging factor for heap */ | |
ad19eafb | 58 | heap_node **nodes; |
59 | } heap; | |
60 | ||
61 | /**************************************************************************** | |
62 | * Public functions | |
63 | ****************************************************************************/ | |
64 | ||
c5dd4956 | 65 | /* |
ad19eafb | 66 | * Create and initialize a new heap. |
67 | */ | |
e6ccf245 | 68 | SQUIDCEXTERN heap *new_heap(int init_size, heap_key_func gen_key); |
ad19eafb | 69 | |
c5dd4956 | 70 | /* |
ad19eafb | 71 | * Delete a heap and clean up its memory. Does not delete what the heap |
72 | * nodes are pointing to! | |
73 | */ | |
e6ccf245 | 74 | SQUIDCEXTERN void delete_heap(heap *); |
ad19eafb | 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 | */ | |
641ac151 | 82 | SQUIDCEXTERN heap_node *heap_insert(heap *hp, heap_t dat); |
ad19eafb | 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 | */ | |
e6ccf245 | 88 | SQUIDCEXTERN heap_t heap_delete(heap *, heap_node * elm); |
ad19eafb | 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 | */ | |
e6ccf245 | 97 | SQUIDCEXTERN heap_t heap_update(heap *, heap_node * elm, heap_t dat); |
ad19eafb | 98 | |
c5dd4956 | 99 | /* |
ad19eafb | 100 | * Generate a heap key for a given data object. Alternative macro form: |
101 | */ | |
f53969cc | 102 | #ifdef MACRO_DEBUG |
e6ccf245 | 103 | SQUIDCEXTERN heap_key heap_gen_key(heap * hp, heap_t dat); |
ad19eafb | 104 | #else |
f53969cc | 105 | #define heap_gen_key(hp,md) ((hp)->gen_key((md),(hp)->age)) |
ad19eafb | 106 | #endif /* MACRO_DEBUG */ |
107 | ||
c5dd4956 | 108 | /* |
ad19eafb | 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 | */ | |
e6ccf245 | 113 | SQUIDCEXTERN heap_t heap_extractmin(heap *); |
ad19eafb | 114 | |
c5dd4956 | 115 | /* |
ad19eafb | 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 | */ | |
e6ccf245 | 122 | SQUIDCEXTERN heap_t heap_extractlast(heap * hp); |
ad19eafb | 123 | |
c5dd4956 | 124 | /* |
ad19eafb | 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 | */ | |
e6ccf245 | 128 | SQUIDCEXTERN heap_key heap_peepminkey(heap *); |
129 | SQUIDCEXTERN heap_key heap_peepkey(heap *, int n); | |
ad19eafb | 130 | |
e6ccf245 | 131 | SQUIDCEXTERN heap_t heap_peepmin(heap *); |
132 | SQUIDCEXTERN heap_t heap_peep(heap *, int n); | |
ad19eafb | 133 | |
c5dd4956 AJ |
134 | /* |
135 | * Is the heap empty? How many nodes (data objects) are in it? | |
ad19eafb | 136 | */ |
f53969cc | 137 | #ifdef MACRO_DEBUG |
e6ccf245 | 138 | SQUIDCEXTERN int heap_empty(heap *); |
139 | SQUIDCEXTERN int heap_nodes(heap *); | |
ad19eafb | 140 | #else /* MACRO_DEBUG */ |
f53969cc SM |
141 | #define heap_nodes(heap) ((heap)->last) |
142 | #define heap_empty(heap) ((heap)->last <= 0 ? 1 : 0) | |
ad19eafb | 143 | #endif /* MACRO_DEBUG */ |
144 | ||
c5dd4956 | 145 | /* |
ad19eafb | 146 | * Print the heap or a node in the heap. |
147 | */ | |
e6ccf245 | 148 | SQUIDCEXTERN void heap_print(heap *); |
149 | SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm); | |
ad19eafb | 150 | |
e6ccf245 | 151 | SQUIDCEXTERN int verify_heap_property(heap *); |
ad19eafb | 152 | |
ff9d9458 | 153 | #endif /* SQUID_INCLUDE_HEAP_H */ |
f53969cc | 154 |