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
162
163
164
165
166
167
|
/*--------------------------------------------------------------------*/
/*--- OSet: a fast data structure with no dups. pub_tool_oset.h ---*/
/*--------------------------------------------------------------------*/
/*
This file is part of Valgrind, a dynamic binary instrumentation
framework.
Copyright (C) 2000-2005 Julian Seward
jseward@acm.org
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., 59 Temple Place, Suite 330, Boston, MA
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
*/
#ifndef __PUB_TOOL_OSET_H
#define __PUB_TOOL_OSET_H
// This module implements an ordered set, a data structure with fast
// (eg. amortised log(n) or better) insertion, lookup and deletion of
// elements. It does not allow duplicates, and will assert if you insert a
// duplicate to an OSet.
//
// The structure is totally generic. The user provides the allocation and
// deallocation functions. Also, each element has a key, which the lookup
// is done with. The key may be the whole element (eg. in an OSet of
// integers, each integer serves both as an element and a key), or it may be
// only part of it (eg. if the key is a single field in a struct). The user
// can provide a function that compares an element with a key; this is very
// flexible, and with the right comparison function even a (non-overlapping)
// interval list can be created. But the cost of calling a function for
// every comparison can be high during lookup. If no comparison function is
// provided, we assume that keys are (signed or unsigned) words, and that
// the key is the first word in each element. This fast comparison is
// suitable for an OSet of Ints, or an OSet containing structs where the
// first element is an Addr, for example.
//
// Each OSet also has an iterator, which makes it simple to traverse all the
// nodes in order. Note that the iterator maintains state and so is
// non-reentrant.
//
// Note that once you insert an element into an OSet, if you modify any part
// of it looked at by your cmp() function, this may cause incorrect
// behaviour as the sorted order maintained will be wrong.
/*--------------------------------------------------------------------*/
/*--- Types ---*/
/*--------------------------------------------------------------------*/
typedef struct _OSet OSet;
typedef struct _OSetNode OSetNode;
typedef Int (*OSetCmp_t) ( void* key, void* elem );
typedef void* (*OSetAlloc_t) ( SizeT szB );
typedef void (*OSetFree_t) ( void* p );
/*--------------------------------------------------------------------*/
/*--- Creating and destroying OSets and OSet members ---*/
/*--------------------------------------------------------------------*/
// * Create: allocates and initialises the OSet. Arguments:
// - keyOff The offset of the key within the element.
// - cmp The comparison function between keys and elements, or NULL
// if the OSet should use fast comparisons.
// - alloc The allocation function used for allocating the OSet itself;
// it's also called for each invocation of VG_(OSet_AllocNode)().
// - free The deallocation function used by VG_(OSet_FreeNode)() and
// VG_(OSet_Destroy)().
//
// If cmp is NULL, keyOff must be zero. This is checked.
//
// * Destroy: frees all nodes in the table, plus the memory used by
// the table itself.
//
// * AllocNode: Allocate and zero memory for a node to go into the OSet.
// Uses the alloc function given to VG_(OSet_Create)() to allocated a node
// which is big enough for both an element and the OSet metadata.
// Not all elements in one OSet have to be the same size.
//
// Note that the element allocated will be at most word-aligned, which may
// be less aligned than the element type would normally be.
//
// * FreeNode: Deallocate a node allocated with OSet_AllocNode(). Using
// a deallocation function (such as VG_(free)()) directly will likely
// lead to assertions in Valgrind's allocator.
extern OSet* VG_(OSet_Create) ( OffT keyOff, OSetCmp_t cmp,
OSetAlloc_t alloc, OSetFree_t free );
extern void VG_(OSet_Destroy) ( OSet* os );
extern void* VG_(OSet_AllocNode) ( OSet* os, SizeT elemSize );
extern void VG_(OSet_FreeNode) ( OSet* os, void* elem );
/*--------------------------------------------------------------------*/
/*--- Operations on OSets ---*/
/*--------------------------------------------------------------------*/
// In everything that follows, the parameter 'key' is always the *address*
// of the key, and 'elem' is *address* of the elem, as are the return values
// of the functions that return elems.
//
// * Size: The number of elements in the set.
//
// * Contains: Determines if any element in the OSet matches the key.
//
// * Lookup: Returns a pointer to the element matching the key, if there is
// one, otherwise returns NULL.
//
// * LookupWithCmp: Like Lookup, but you specify the comparison function,
// which overrides the OSet's normal one.
//
// * Insert: Inserts a new element into the list. Note that 'elem' must
// have been allocated using VG_(OSet_AllocNode)(), otherwise you will get
// assertion failures about "bad magic". Duplicates are forbidden, and
// will also cause assertion failures.
//
// * Remove: Removes the element matching the key, if there is one. Returns
// NULL if no element matches the key.
//
// * ResetIter: Each OSet has an iterator. This resets it to point to the
// first element in the OSet.
//
// * Next: Returns a pointer to the element pointed to by the OSet's
// iterator, and advances the iterator by one; the elements are visited
// in order. Or, returns NULL if the iterator has reached the OSet's end.
//
// You can thus iterate in order through an OSet like this:
//
// VG_(OSet_ResetIter)(oset);
// while ( (elem = VG_(OSet_Next)(oset)) ) {
// ... do stuff with 'elem' ...
// }
//
// Note that iterators are cleared any time an element is inserted or
// removed from the OSet, to avoid possible mayhem caused by the iterator
// getting out of sync with the OSet's contents. "Cleared" means that
// they will return NULL if VG_(OSet_Next)() is called without an
// intervening call to VG_(OSet_ResetIter)().
extern Int VG_(OSet_Size) ( OSet* os );
extern void VG_(OSet_Insert) ( OSet* os, void* elem );
extern Bool VG_(OSet_Contains) ( OSet* os, void* key );
extern void* VG_(OSet_Lookup) ( OSet* os, void* key );
extern void* VG_(OSet_LookupWithCmp)( OSet* os, void* key, OSetCmp_t cmp );
extern void* VG_(OSet_Remove) ( OSet* os, void* key );
extern void VG_(OSet_ResetIter) ( OSet* os );
extern void* VG_(OSet_Next) ( OSet* os );
#endif // __PUB_TOOL_OSET_H
/*--------------------------------------------------------------------*/
/*--- end ---*/
/*--------------------------------------------------------------------*/
|
