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