BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file CAvl_header.h
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 // Preprocessor inputs:
31 // CAVL_PARAM_NAME - name of this data structure
32 // CAVL_PARAM_FEATURE_COUNTS - whether to keep count information (0 or 1)
33 // CAVL_PARAM_FEATURE_KEYS_ARE_INDICES - (0 or 1) whether to assume the keys are entry indices
34 // (number of entries lesser than given entry). If yes, CAVL_PARAM_TYPE_KEY is unused.
35 // Requires CAVL_PARAM_FEATURE_COUNTS.
36 // CAVL_PARAM_FEATURE_NOKEYS - define to 1 if there is no need for a lookup operation
37 // CAVL_PARAM_FEATURE_ASSOC - define to 1 for computation of an associative operation on subtrees.
38 // If enabled, the following macros must be defined: CAVL_PARAM_TYPE_ASSOC,
39 // CAVL_PARAM_VALUE_ASSOC_ZERO, CAVL_PARAM_FUN_ASSOC_VALUE,
40 // CAVL_PARAM_FUN_ASSOC_OPER, CAVL_PARAM_MEMBER_ASSOC.
41 // CAVL_PARAM_TYPE_ENTRY - type of entry
42 // CAVL_PARAM_TYPE_LINK - type of entry link (usually pointer or index)
43 // CAVL_PARAM_TYPE_KEY - type of key (only if not CAVL_PARAM_FEATURE_KEYS_ARE_INDICES and
44 // not CAVL_PARAM_FEATURE_NOKEYS)
45 // CAVL_PARAM_TYPE_ARG - type of argument pass through to callbacks
46 // CAVL_PARAM_TYPE_COUNT - type of count (only if CAVL_PARAM_FEATURE_COUNTS)
47 // CAVL_PARAM_TYPE_ASSOC - type of associative operation result
48 // CAVL_PARAM_VALUE_COUNT_MAX - maximum value of count (type is CAVL_PARAM_TYPE_COUNT)
49 // CAVL_PARAM_VALUE_NULL - value of invalid link (type is CAVL_PARAM_TYPE_LINK)
50 // CAVL_PARAM_VALUE_ASSOC_ZERO - zero value for associative operation (type is CAVL_PARAM_TYPE_ASSOC).
51 // This must be both a left- and right-identity for the associative operation.
52 // CAVL_PARAM_FUN_DEREF(arg, link) - dereference a non-null link; returns pointer to CAVL_PARAM_TYPE_LINK
53 // CAVL_PARAM_FUN_COMPARE_ENTRIES(arg, entry1, entry2) - compare to entries; returns -1/0/1
54 // CAVL_PARAM_FUN_COMPARE_KEY_ENTRY(arg, key1, entry2) - compare key and entry; returns -1/0/1
55 // CAVL_PARAM_FUN_ASSOC_VALUE(arg, entry) - get value of a node for associative operation.
56 // The result will be cast to CAVL_PARAM_TYPE_ASSOC.
57 // CAVL_PARAM_FUN_ASSOC_OPER(arg, value1, value2) - compute the associative operation on two values.
58 // The type of the two values is CAVL_PARAM_TYPE_ASSOC, and the result will be cast to
59 // CAVL_PARAM_TYPE_ASSOC.
60 // CAVL_PARAM_MEMBER_CHILD - name of the child member in entry (type is CAVL_PARAM_TYPE_LINK[2])
61 // CAVL_PARAM_MEMBER_BALANCE - name of the balance member in entry (type is any signed integer)
62 // CAVL_PARAM_MEMBER_PARENT - name of the parent member in entry (type is CAVL_PARAM_TYPE_LINK)
63 // CAVL_PARAM_MEMBER_COUNT - name of the count member in entry (type is CAVL_PARAM_TYPE_COUNT)
64 // (only if CAVL_PARAM_FEATURE_COUNTS)
65 // CAVL_PARAM_MEMBER_ASSOC - name of assoc member in entry (type is CAVL_PARAM_TYPE_ASSOC)
66  
67 #ifndef BADVPN_CAVL_H
68 #error CAvl.h has not been included
69 #endif
70  
71 #if CAVL_PARAM_FEATURE_KEYS_ARE_INDICES && !CAVL_PARAM_FEATURE_COUNTS
72 #error CAVL_PARAM_FEATURE_KEYS_ARE_INDICES requires CAVL_PARAM_FEATURE_COUNTS
73 #endif
74  
75 #if CAVL_PARAM_FEATURE_KEYS_ARE_INDICES && CAVL_PARAM_FEATURE_NOKEYS
76 #error CAVL_PARAM_FEATURE_KEYS_ARE_INDICES and CAVL_PARAM_FEATURE_NOKEYS cannot be used together
77 #endif
78  
79 // types
80 #define CAvl CAVL_PARAM_NAME
81 #define CAvlEntry CAVL_PARAM_TYPE_ENTRY
82 #define CAvlLink CAVL_PARAM_TYPE_LINK
83 #define CAvlRef MERGE(CAVL_PARAM_NAME, Ref)
84 #define CAvlArg CAVL_PARAM_TYPE_ARG
85 #define CAvlKey CAVL_PARAM_TYPE_KEY
86 #define CAvlCount CAVL_PARAM_TYPE_COUNT
87 #define CAvlAssoc CAVL_PARAM_TYPE_ASSOC
88  
89 // non-object public functions
90 #define CAvlIsNullRef MERGE(CAvl, IsNullRef)
91 #define CAvlIsValidRef MERGE(CAvl, IsValidRef)
92 #define CAvlDeref MERGE(CAvl, Deref)
93  
94 // public functions
95 #define CAvl_Init MERGE(CAvl, _Init)
96 #define CAvl_Insert MERGE(CAvl, _Insert)
97 #define CAvl_InsertAt MERGE(CAvl, _InsertAt)
98 #define CAvl_Remove MERGE(CAvl, _Remove)
99 #define CAvl_Lookup MERGE(CAvl, _Lookup)
100 #define CAvl_LookupExact MERGE(CAvl, _LookupExact)
101 #define CAvl_GetFirstGreater MERGE(CAvl, _GetFirstGreater)
102 #define CAvl_GetLastLesser MERGE(CAvl, _GetLastLesser)
103 #define CAvl_GetFirstGreaterEqual MERGE(CAvl, _GetFirstGreaterEqual)
104 #define CAvl_GetLastLesserEqual MERGE(CAvl, _GetLastLesserEqual)
105 #define CAvl_GetFirst MERGE(CAvl, _GetFirst)
106 #define CAvl_GetLast MERGE(CAvl, _GetLast)
107 #define CAvl_GetNext MERGE(CAvl, _GetNext)
108 #define CAvl_GetPrev MERGE(CAvl, _GetPrev)
109 #define CAvl_IsEmpty MERGE(CAvl, _IsEmpty)
110 #define CAvl_Verify MERGE(CAvl, _Verify)
111 #define CAvl_Count MERGE(CAvl, _Count)
112 #define CAvl_IndexOf MERGE(CAvl, _IndexOf)
113 #define CAvl_GetAt MERGE(CAvl, _GetAt)
114 #define CAvl_AssocSum MERGE(CAvl, _AssocSum)
115 #define CAvl_ExclusiveAssocPrefixSum MERGE(CAvl, _ExclusiveAssocPrefixSum)
116 #define CAvl_FindLastExclusiveAssocPrefixSumLesserEqual MERGE(CAvl, _FindLastExclusiveAssocPrefixSumLesserEqual)
117  
118 // private stuff
119 #define CAvl_link(entry) ((entry).ptr->CAVL_PARAM_MEMBER_CHILD)
120 #define CAvl_balance(entry) ((entry).ptr->CAVL_PARAM_MEMBER_BALANCE)
121 #define CAvl_parent(entry) ((entry).ptr->CAVL_PARAM_MEMBER_PARENT)
122 #define CAvl_count(entry) ((entry).ptr->CAVL_PARAM_MEMBER_COUNT)
123 #define CAvl_assoc(entry) ((entry).ptr->CAVL_PARAM_MEMBER_ASSOC)
124 #define CAvl_nulllink MERGE(CAvl, __nulllink)
125 #define CAvl_nullref MERGE(CAvl, __nullref)
126 #define CAvl_compare_entries MERGE(CAVL_PARAM_NAME, _compare_entries)
127 #define CAvl_compare_key_entry MERGE(CAVL_PARAM_NAME, _compare_key_entry)
128 #define CAvl_compute_node_assoc MERGE(CAVL_PARAM_NAME, _compute_node_assoc)
129 #define CAvl_check_parent MERGE(CAVL_PARAM_NAME, _check_parent)
130 #define CAvl_verify_recurser MERGE(CAVL_PARAM_NAME, _verify_recurser)
131 #define CAvl_assert_tree MERGE(CAVL_PARAM_NAME, _assert_tree)
132 #define CAvl_update_count_from_children MERGE(CAVL_PARAM_NAME, _update_count_from_children)
133 #define CAvl_rotate MERGE(CAVL_PARAM_NAME, _rotate)
134 #define CAvl_subtree_min MERGE(CAVL_PARAM_NAME, _subtree_min)
135 #define CAvl_subtree_max MERGE(CAVL_PARAM_NAME, _subtree_max)
136 #define CAvl_replace_subtree_fix_assoc MERGE(CAVL_PARAM_NAME, _replace_subtree_fix_counts)
137 #define CAvl_swap_for_remove MERGE(CAVL_PARAM_NAME, _swap_entries)
138 #define CAvl_rebalance MERGE(CAVL_PARAM_NAME, _rebalance)
139 #define CAvl_child_count MERGE(CAvl, __child_count)
140 #define CAvl_MAX(_a, _b) ((_a) > (_b) ? (_a) : (_b))
141 #define CAvl_OPTNEG(_a, _neg) ((_neg) ? -(_a) : (_a))