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
|
/* wmem_interval_tree.h
* Definitions for the Wireshark Memory Manager Red-Black Tree
* Based on the red-black tree implementation in epan/emem.*
* Copyright 2015, Matthieu coudron <matthieu.coudron@lip6.fr>
*
* 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_INTERVAL_TREE_H__
#define __WMEM_INTERVAL_TREE_H__
#include "wmem_core.h"
#include "wmem_tree.h"
#include "wmem_list.h"
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
/** @addtogroup wmem
* @{
* @defgroup wmem-interval-tree Interval Tree
*
* http://www.geeksforgeeks.org/interval-tree/
* The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc ...
* to maintain a set of intervals so that all operations can be done in O(Logn) time.
* @{
* Following wikipedia's convention this is an augmented tree rather then an interval tree
* http://www.wikiwand.com/en/Interval_tree
*/
struct _wmem_tree_t;
typedef struct _wmem_tree_t wmem_itree_t;
struct _wmem_range_t {
guint64 low; /* low is used as the key in the binary tree */
guint64 high; /* Max value of the range */
guint64 max_edge; /* max value among subtrees */
};
/**
* Callback to provide the data for an interval. The original data that is
* replaced by the new data are passed as "oldData1" and "oldData2". If there
* was no previous interval, then these will be NULL. It is the responsibility
* of this callback to deallocate resources associated with the old data.
*/
typedef void *(*wmem_itree_data_callback)(void *oldData1, void *oldData2);
WS_DLL_PUBLIC
wmem_itree_t *
wmem_itree_new(wmem_allocator_t *allocator)
G_GNUC_MALLOC;
/** Returns true if the tree is empty (has no nodes). */
WS_DLL_PUBLIC
gboolean
wmem_itree_is_empty(wmem_itree_t *tree);
/** Inserts a range low-high indexed by "low" in O(log(n)).
* As in wmem_tree, if a key "low" already exists, it will be overwritten with the new data
*
*/
WS_DLL_PUBLIC
void
wmem_itree_insert(wmem_itree_t *tree, const guint64 low, const guint64 high, void *data);
/** Inserts a point indexed by "pos" in O(log(n)).
*
* Pre-condition: there must not be overlapping or directly adjacent intervals
* (guaranteed by using only wmem_itree_insert_point).
* If the point already exists, nothing is done. Otherwise an interval is
* created or updated, invoking the callback to obtain the new data.
*/
WS_DLL_PUBLIC
void
wmem_itree_insert_point(wmem_itree_t *tree, const guint64 pos, wmem_itree_data_callback callback);
/*
* Save results in a wmem_list with the scope passed as a parameter.
* wmem_list_t is always allocated even if there is no result
*/
WS_DLL_PUBLIC
wmem_list_t *
wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, guint64 low, guint64 high);
/**
* Print ranges along the tree
*/
void
wmem_print_itree(wmem_itree_t *tree);
/** @}
* @} */
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* __WMEM_INTERVAL_TREE_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:
*/
|
