Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
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 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /** \file
29 : * Inplace trie.
30 : *
31 : * This trie is a inplace implementation not needing any external allocation.
32 : *
33 : * Elements are not stored in order, like ::tommy_trie, because some elements
34 : * should be used to represent the inner nodes in the trie.
35 : *
36 : * You can control the number of branches of each node using the ::TOMMY_TRIE_INPLACE_TREE_MAX define.
37 : * More branches imply more speed, but a bigger memory occupation.
38 : *
39 : * Compared to ::tommy_trie you should use a lower number of branches to limit the unused memory
40 : * occupation of the leaf nodes. This imply a lower speed, but without the need of an external allocator.
41 : *
42 : * To initialize the trie you have to call tommy_trie_inplace_init().
43 : *
44 : * \code
45 : * tommy_trie_inplace trie_inplace;
46 : *
47 : * tommy_trie_inplace_init(&trie_inplace);
48 : * \endcode
49 : *
50 : * To insert elements in the trie you have to call tommy_trie_inplace_insert() for
51 : * each element.
52 : * In the insertion call you have to specify the address of the node, the
53 : * address of the object, and the key value to use.
54 : * The address of the object is used to initialize the tommy_node::data field
55 : * of the node, and the key to initialize the tommy_node::key field.
56 : *
57 : * \code
58 : * struct object {
59 : * int value;
60 : * // other fields
61 : * tommy_node node;
62 : * };
63 : *
64 : * struct object* obj = malloc(sizeof(struct object)); // creates the object
65 : *
66 : * obj->value = ...; // initializes the object
67 : *
68 : * tommy_trie_inplace_insert(&trie_inplace, &obj->node, obj, obj->value); // inserts the object
69 : * \endcode
70 : *
71 : * To find and element in the trie you have to call tommy_trie_inplace_search() providing
72 : * the key to search.
73 : *
74 : * \code
75 : * int value_to_find = 1;
76 : * struct object* obj = tommy_trie_inplace_search(&trie_inplace, value_to_find);
77 : * if (!obj) {
78 : * // not found
79 : * } else {
80 : * // found
81 : * }
82 : * \endcode
83 : *
84 : * To iterate over all the elements in the trie with the same key, you have to
85 : * use tommy_trie_inplace_bucket() and follow the tommy_node::next pointer until NULL.
86 : *
87 : * \code
88 : * int value_to_find = 1;
89 : * tommy_node* i = tommy_trie_inplace_bucket(&trie_inplace, value_to_find);
90 : * while (i) {
91 : * struct object* obj = i->data; // gets the object pointer
92 : *
93 : * printf("%d\n", obj->value); // process the object
94 : *
95 : * i = i->next; // goes to the next element
96 : * }
97 : * \endcode
98 : *
99 : * To remove an element from the trie you have to call tommy_trie_inplace_remove()
100 : * providing the key to search and remove.
101 : *
102 : * \code
103 : * struct object* obj = tommy_trie_inplace_remove(&trie_inplace, value_to_remove);
104 : * if (obj) {
105 : * free(obj); // frees the object allocated memory
106 : * }
107 : * \endcode
108 : *
109 : * To destroy the trie you have only to remove all the elements, as the trie is
110 : * completely inplace and it doesn't allocate memory.
111 : *
112 : * Note that you cannot iterate over all the elements in the trie using the
113 : * trie itself. You have to insert all the elements also in a ::tommy_list,
114 : * and use the list to iterate. See the \ref multiindex example for more detail.
115 : */
116 :
117 : #ifndef __TOMMYTRIEINP_H
118 : #define __TOMMYTRIEINP_H
119 :
120 : #include "tommytypes.h"
121 :
122 : /******************************************************************************/
123 : /* trie_inplace */
124 :
125 : /**
126 : * Number of bits of the elements to store in the trie.
127 : *
128 : * If you need to store integers bigger than 32 bits you can
129 : * increse this value.
130 : *
131 : * Keeping this value small improves the performance of the trie.
132 : */
133 : #define TOMMY_TRIE_INPLACE_BIT 32
134 :
135 : /**
136 : * Number of branches on each node. It must be a power of 2.
137 : * Suggested values are 2, 4 and 8.
138 : * Any node, including leafs, contains a pointer to each branch.
139 : */
140 : #define TOMMY_TRIE_INPLACE_TREE_MAX 4
141 :
142 : /** \internal
143 : * Number of bits for each branch.
144 : */
145 : #define TOMMY_TRIE_INPLACE_TREE_BIT TOMMY_ILOG2(TOMMY_TRIE_INPLACE_TREE_MAX)
146 :
147 : /** \internal
148 : * Number of bits of the first level.
149 : */
150 : #define TOMMY_TRIE_INPLACE_BUCKET_BIT ((TOMMY_TRIE_INPLACE_BIT % TOMMY_TRIE_INPLACE_TREE_BIT) + 3 * TOMMY_TRIE_INPLACE_TREE_BIT)
151 :
152 : /** \internal
153 : * Number of branches of the first level.
154 : * It's like a inner branch, but bigger to get any remainder bits.
155 : */
156 : #define TOMMY_TRIE_INPLACE_BUCKET_MAX (1 << TOMMY_TRIE_INPLACE_BUCKET_BIT)
157 :
158 : /**
159 : * Trie node.
160 : * This is the node that you have to include inside your objects.
161 : */
162 : typedef struct tommy_trie_inplace_node_struct {
163 : struct tommy_trie_inplace_node_struct* next; /**< Next element. 0 if it's the last. */
164 : struct tommy_trie_inplace_node_struct* prev; /**< Circular previous element. */
165 : void* data; /**< Pointer to the data. */
166 : struct tommy_trie_inplace_node_struct* map[TOMMY_TRIE_INPLACE_TREE_MAX]; /** Branches of the node. */
167 : tommy_key_t key; /**< Used to store the key or the hash. */
168 : } tommy_trie_inplace_node;
169 :
170 : /**
171 : * Trie container type.
172 : * \note Don't use internal fields directly, but access the container only using functions.
173 : */
174 : typedef struct tommy_trie_inplace_struct {
175 : tommy_trie_inplace_node* bucket[TOMMY_TRIE_INPLACE_BUCKET_MAX]; /**< First tree level. */
176 : tommy_size_t count; /**< Number of elements. */
177 : } tommy_trie_inplace;
178 :
179 : /**
180 : * Initializes the trie.
181 : *
182 : * The tries is completely inplace, and it doesn't need to be deinitialized.
183 : */
184 : void tommy_trie_inplace_init(tommy_trie_inplace* trie_inplace);
185 :
186 : /**
187 : * Inserts an element in the trie.
188 : */
189 : void tommy_trie_inplace_insert(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node, void* data, tommy_key_t key);
190 :
191 : /**
192 : * Searches and removes the first element with the specified key.
193 : * If the element is not found, 0 is returned.
194 : * If more equal elements are present, the first one is removed.
195 : * This operation is faster than calling tommy_trie_inplace_bucket() and tommy_trie_inplace_remove_existing() separately.
196 : * \param key Key of the element to find and remove.
197 : * \return The removed element, or 0 if not found.
198 : */
199 : void* tommy_trie_inplace_remove(tommy_trie_inplace* trie_inplace, tommy_key_t key);
200 :
201 : /**
202 : * Gets the bucket of the specified key.
203 : * The bucket is guaranteed to contain ALL and ONLY the elements with the specified key.
204 : * You can access elements in the bucket following the ::next pointer until 0.
205 : * \param key Key of the element to find.
206 : * \return The head of the bucket, or 0 if empty.
207 : */
208 : tommy_trie_inplace_node* tommy_trie_inplace_bucket(tommy_trie_inplace* trie_inplace, tommy_key_t key);
209 :
210 : /**
211 : * Searches an element in the trie.
212 : * You have to provide the key of the element you want to find.
213 : * If more elements with the same key are present, the first one is returned.
214 : * \param key Key of the element to find.
215 : * \return The first element found, or 0 if none.
216 : */
217 4000000 : tommy_inline void* tommy_trie_inplace_search(tommy_trie_inplace* trie_inplace, tommy_key_t key)
218 : {
219 4000000 : tommy_trie_inplace_node* i = tommy_trie_inplace_bucket(trie_inplace, key);
220 :
221 4000000 : if (!i)
222 2000000 : return 0;
223 :
224 2000000 : return i->data;
225 : }
226 :
227 : /**
228 : * Removes an element from the trie.
229 : * You must already have the address of the element to remove.
230 : * \return The tommy_node::data field of the node removed.
231 : */
232 : void* tommy_trie_inplace_remove_existing(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node);
233 :
234 : /**
235 : * Gets the number of elements.
236 : */
237 2 : tommy_inline tommy_size_t tommy_trie_inplace_count(tommy_trie_inplace* trie_inplace)
238 : {
239 2 : return trie_inplace->count;
240 : }
241 :
242 : /**
243 : * Gets the size of allocated memory.
244 : * It includes the size of the ::tommy_inplace_node of the stored elements.
245 : */
246 : tommy_size_t tommy_trie_inplace_memory_usage(tommy_trie_inplace* trie_inplace);
247 :
248 : #endif
249 :
|
