heap.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 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 */
31typedef unsigned long heap_mutex_t;
32typedef void * heap_t;
33typedef 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 */
41typedef struct _heap_node {
43 unsigned long id;
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 */
52typedef 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 */
60
61/****************************************************************************
62 * Public functions
63 ****************************************************************************/
64
65/*
66 * Create and initialize a new heap.
67 */
68SQUIDCEXTERN 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 */
149SQUIDCEXTERN void heap_printnode(char *msg, heap_node * elm);
150
152
153#endif /* SQUID_HEAP_H */
154
SQUIDCEXTERN heap_t heap_peep(heap *, int n)
Definition: heap.c:281
#define heap_gen_key(hp, md)
Definition: heap.h:105
SQUIDCEXTERN heap_t heap_update(heap *, heap_node *elm, heap_t dat)
Definition: heap.c:228
SQUIDCEXTERN int verify_heap_property(heap *)
Definition: heap.c:436
SQUIDCEXTERN heap_key heap_peepkey(heap *, int n)
Definition: heap.c:268
SQUIDCEXTERN heap_t heap_peepmin(heap *)
Definition: heap.c:247
double heap_key
Definition: heap.h:33
SQUIDCEXTERN heap_t heap_delete(heap *, heap_node *elm)
Definition: heap.c:142
unsigned long heap_mutex_t
Definition: heap.h:31
SQUIDCEXTERN heap_key heap_peepminkey(heap *)
Definition: heap.c:257
SQUIDCEXTERN void heap_printnode(char *msg, heap_node *elm)
SQUIDCEXTERN heap_t heap_extractlast(heap *hp)
Definition: heap.c:210
#define heap_empty(heap)
Definition: heap.h:142
SQUIDCEXTERN void delete_heap(heap *)
Definition: heap.c:95
void * heap_t
Definition: heap.h:32
SQUIDCEXTERN heap_node * heap_insert(heap *hp, heap_t dat)
Definition: heap.c:117
SQUIDCEXTERN void heap_print(heap *)
#define heap_nodes(heap)
Definition: heap.h:141
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
struct _heap heap
struct _heap_node heap_node
SQUIDCEXTERN heap_t heap_extractmin(heap *)
Definition: heap.c:188
#define SQUIDCEXTERN
Definition: squid.h:21
unsigned long id
Definition: heap.h:43
heap_t data
Definition: heap.h:44
heap_key key
Definition: heap.h:42
Definition: heap.h:52
heap_node ** nodes
Definition: heap.h:58
heap_key_func * gen_key
Definition: heap.h:56
unsigned long last
Definition: heap.h:55
heap_mutex_t lock
Definition: heap.h:53
unsigned long size
Definition: heap.h:54
heap_key age
Definition: heap.h:57

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors