Code Coverage: vinyl-cache/include/vbh.h
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
0
/*-
1
 * Copyright (c) 2006 Verdens Gang AS
2
 * Copyright (c) 2006-2009 Varnish Software AS
3
 * All rights reserved.
4
 *
5
 * Author: Poul-Henning Kamp <phk@phk.freebsd.dk>
6
 *
7
 * SPDX-License-Identifier: BSD-2-Clause
8
 *
9
 * Redistribution and use in source and binary forms, with or without
10
 * modification, are permitted provided that the following conditions
11
 * are met:
12
 * 1. Redistributions of source code must retain the above copyright
13
 *    notice, this list of conditions and the following disclaimer.
14
 * 2. Redistributions in binary form must reproduce the above copyright
15
 *    notice, this list of conditions and the following disclaimer in the
16
 *    documentation and/or other materials provided with the distribution.
17
 *
18
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
22
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28
 * SUCH DAMAGE.
29
 *
30
 * Binary Heap API (see: http://en.wikipedia.org/wiki/Binary_heap)
31
 *
32
 * XXX: doesn't scale back the array of pointers when items are deleted.
33
 */
34
35
/* Public Interface --------------------------------------------------*/
36
37
struct vbh;
38
39
typedef int vbh_cmp_t(void *priv, const void *a, const void *b);
40
        /*
41
         * Comparison function.
42
         * Should return true if item 'a' should be closer to the root
43
         * than item 'b'
44
         */
45
46
typedef void vbh_update_t(void *priv, void *a, unsigned newidx);
47
        /*
48
         * Update function (optional)
49
         * When items move in the tree, this function gets called to
50
         * notify the item of its new index.
51
         * Only needed if deleting non-root items.
52
         */
53
54
struct vbh *VBH_new(void *priv, vbh_cmp_t, vbh_update_t);
55
        /*
56
         * Create Binary tree
57
         * 'priv' is passed to cmp and update functions.
58
         */
59
60
void VBH_destroy(struct vbh **);
61
        /*
62
         * Destroy an empty Binary tree
63
         */
64
65
void VBH_insert(struct vbh *, void *);
66
        /*
67
         * Insert an item
68
         */
69
70
void VBH_reorder(const struct vbh *, unsigned idx);
71
        /*
72
         * Move an order after changing its key value.
73
         */
74
75
void VBH_delete(struct vbh *, unsigned idx);
76
        /*
77
         * Delete an item
78
         * The root item has 'idx' zero
79
         */
80
81
void *VBH_root(const struct vbh *);
82
        /*
83
         * Return the root item
84
         */
85
86 1737121
#define VBH_NOIDX       0