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
155
156
157
158
159
160
161
|
/* wmem_splay.h
* Definitions for the Wireshark Memory Manager Splay Tree
* Copyright 2014, Evan Huus <eapache@gmail.com>
*
* Wireshark - Network traffic analyzer
* By Gerald Combs <gerald@wireshark.org>
* Copyright 1998 Gerald Combs
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#ifndef __WMEM_SPLAY_H__
#define __WMEM_SPLAY_H__
#include "wmem_core.h"
#include "wmem_tree.h"
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
/** @addtogroup wmem
* @{
* @defgroup wmem-splay Splay Tree
*
* Binary trees are a well-known and popular device in computer science to
* handle storage of objects based on a search key or identity. The
* particular binary tree style implemented here is the splay tree, which
* has a large number of nice properties. It guarantees O(log(n)) amortized
* time per operation, and O(1) per operation for certain special access
* patterns. See https://en.wikipedia.org/wiki/Splay_tree
*
* The version implemented here is known as "independent semi-splaying",
* which is a variant with the same properties but slightly better practical
* performance.
*
* @{
*/
struct _wmem_splay_t;
typedef struct _wmem_splay_t wmem_splay_t;
/** A wmem_compare_func compares two keys in a tree, and must return:
* 0 if a==b
* >0 if a>b
* <0 if a<b
* It must be able to compare any two keys, and must form a total order on the
* space of keys (https://en.wikipedia.org/wiki/Total_order). For example, the
* builtin strcmp() function satisfies these requirements.
*/
typedef int (*wmem_compare_func)(const void *a, const void *b);
/** Creates a tree with the given allocator scope. When the scope is emptied,
* the tree is fully destroyed. The given comparison function is used to compare
* keys. It is permitted to pass NULL for the comparison function, in which case
* the key pointer values will be compared directly (cast to signed integers).
*/
WS_DLL_PUBLIC
wmem_splay_t *
wmem_splay_new(wmem_allocator_t *allocator, wmem_compare_func cmp)
G_GNUC_MALLOC;
/** Creates a tree with two allocator scopes. The base structure lives in the
* master scope, however the data lives in the slave scope. Every time free_all
* occurs in the slave scope the tree is transparently emptied without affecting
* the location of the master structure.
*
* WARNING: None of the tree (even the part in the master scope) can be used
* after the slave scope has been *destroyed*.
*
* The primary use for this function is to create trees that reset for each new
* capture file that is loaded. This can be done by specifying wmem_epan_scope()
* as the master and wmem_file_scope() as the slave.
*/
WS_DLL_PUBLIC
wmem_splay_t *
wmem_splay_new_autoreset(wmem_allocator_t *master, wmem_allocator_t *slave,
wmem_compare_func cmp)
G_GNUC_MALLOC;
/** Returns true if the tree is empty (has no nodes). */
WS_DLL_PUBLIC
gboolean
wmem_splay_is_empty(const wmem_splay_t *tree);
/** Look up a node in the tree indexed by the given key. If no node is found
* the function will return NULL.
*/
WS_DLL_PUBLIC
void *
wmem_splay_lookup(wmem_splay_t *tree, const void *key);
/** Look up a node in the tree indexed by the given key. Returns the node that
* has the largest key that is less than or equal to the search key, or NULL if
* no such node exists.
*/
WS_DLL_PUBLIC
void *
wmem_splay_lookup_le(wmem_splay_t *tree, const void *key);
/** Insert a node indexed by the given key.
*
* Value is a pointer to the structure you want to be able to retrieve by
* searching for the same key later.
*
* Unlike the old wmem_tree/emem_tree, inserting does *not* take a copy of
* whatever key is pointed to, it simply stores a pointer. As such, inserted
* keys cannot be on the stack and must instead last as long as the tree itself
* (keys used during lookups are not stored, and can be on the stack).
*
* NOTE: If you insert a node to a key that already exists in the tree this
* function will simply overwrite the old value. If the structures you are
* storing are allocated in a wmem pool this is not a problem as they will still
* be freed with the pool. If you are managing them manually however, you must
* either ensure each key is unique, or do a lookup before each insert.
*/
WS_DLL_PUBLIC
void
wmem_splay_insert(wmem_splay_t *tree, void *key, void *value);
/** Traverse the tree and call callback(value, userdata) for each value found.
* Returns TRUE if the traversal was ended prematurely by the callback.
*/
WS_DLL_PUBLIC
gboolean
wmem_splay_foreach(wmem_splay_t* tree, wmem_foreach_func callback,
void *user_data);
/** @}
* @} */
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* __WMEM_SPLAY_H__ */
/*
* Editor modelines - http://www.wireshark.org/tools/modelines.html
*
* Local variables:
* c-basic-offset: 4
* tab-width: 8
* indent-tabs-mode: nil
* End:
*
* vi: set shiftwidth=4 tabstop=8 expandtab:
* :indentSize=4:tabSize=8:noTabs=true:
*/
|
