tommytrieinp.h
Go to the documentation of this file.
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 
117 #ifndef __TOMMYTRIEINP_H
118 #define __TOMMYTRIEINP_H
119 
120 #include "tommytypes.h"
121 
122 /******************************************************************************/
123 /* trie_inplace */
124 
130 #define TOMMY_TRIE_INPLACE_TREE_MAX 4
131 
135 #define TOMMY_TRIE_INPLACE_TREE_BIT TOMMY_ILOG2(TOMMY_TRIE_INPLACE_TREE_MAX)
136 
140 #define TOMMY_TRIE_INPLACE_BUCKET_BIT ((TOMMY_KEY_BIT % TOMMY_TRIE_INPLACE_TREE_BIT) + 3 * TOMMY_TRIE_INPLACE_TREE_BIT)
141 
146 #define TOMMY_TRIE_INPLACE_BUCKET_MAX (1 << TOMMY_TRIE_INPLACE_BUCKET_BIT)
147 
155  void* data;
159 
165  tommy_trie_inplace_node* bucket[TOMMY_TRIE_INPLACE_BUCKET_MAX];
168 
174 void tommy_trie_inplace_init(tommy_trie_inplace* trie_inplace);
175 
179 void tommy_trie_inplace_insert(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node, void* data, tommy_key_t key);
180 
190 
199 
207 tommy_inline void* tommy_trie_inplace_search(tommy_trie_inplace* trie_inplace, tommy_key_t key)
208 {
209  tommy_trie_inplace_node* i = tommy_trie_inplace_bucket(trie_inplace, key);
210 
211  if (!i)
212  return 0;
213 
214  return i->data;
215 }
216 
223 
228 {
229  return trie_inplace->count;
230 }
231 
237 
238 #endif
239 
struct tommy_trie_inplace_struct tommy_trie_inplace
Trie container type.
tommy_count_t tommy_trie_inplace_count(tommy_trie_inplace *trie_inplace)
Gets the number of elements.
Definition: tommytrieinp.h:227
tommy_uint32_t tommy_count_t
Generic unsigned integer for counting objects.
Definition: tommytypes.h:67
tommy_uint32_t tommy_key_t
Key type used in indexed data structures to store the key or the hash value.
Definition: tommytypes.h:160
void * tommy_trie_inplace_search(tommy_trie_inplace *trie_inplace, tommy_key_t key)
Searches an element in the trie.
Definition: tommytrieinp.h:207
struct tommy_trie_inplace_node_struct * prev
Circular previous element.
Definition: tommytrieinp.h:154
Trie node.
Definition: tommytrieinp.h:152
#define TOMMY_TRIE_INPLACE_TREE_MAX
Number of branches on each node.
Definition: tommytrieinp.h:130
struct tommy_trie_inplace_node_struct * next
Next element.
Definition: tommytrieinp.h:153
tommy_count_t count
Number of elements.
Definition: tommytrieinp.h:166
void * tommy_trie_inplace_remove_existing(tommy_trie_inplace *trie_inplace, tommy_trie_inplace_node *node)
Removes an element from the trie.
void * data
Pointer to the data.
Definition: tommytrieinp.h:155
void tommy_trie_inplace_init(tommy_trie_inplace *trie_inplace)
Initializes the trie.
void tommy_trie_inplace_insert(tommy_trie_inplace *trie_inplace, tommy_trie_inplace_node *node, void *data, tommy_key_t key)
Inserts an element in the trie.
size_t tommy_size_t
Generic size_t type.
Definition: tommytypes.h:50
void * tommy_trie_inplace_remove(tommy_trie_inplace *trie_inplace, tommy_key_t key)
Searches and removes the first element with the specified key.
Generic types.
tommy_trie_inplace_node * bucket[TOMMY_TRIE_INPLACE_BUCKET_MAX]
First tree level.
Definition: tommytrieinp.h:165
tommy_size_t tommy_trie_inplace_memory_usage(tommy_trie_inplace *trie_inplace)
Gets the size of allocated memory.
Trie container type.
Definition: tommytrieinp.h:164
struct tommy_trie_inplace_node_struct tommy_trie_inplace_node
Trie node.
tommy_key_t key
Branches of the node.
Definition: tommytrieinp.h:157
tommy_trie_inplace_node * tommy_trie_inplace_bucket(tommy_trie_inplace *trie_inplace, tommy_key_t key)
Gets the bucket of the specified key.