VLib/TVTrie [ Modules ]
NAME
TVTrie -- a trie data structure.
HISTORY
- Documented on 2008-08-09.
- Moved to library style on 2008-08-10.
TVTrie/struct TVTriePage [ Structures ]
[ Top ] [ TVTrie ] [ Structures ]
NAME
struct TVTriePage -- a description of the tree page
FUNCTION
The structure desctibes a page of the tree. The root of the tree would be this type. The structure is used to holt the pointer to data of the page and its size. The advantage is that the data may be relocated to other address while growing but the page structure stays on original address.
ATTRIBUTES
- size -- the allocated size in bytes of the page itself.
- data -- data of the page; the limit is expressed by size field.
DESCRIPTION
The data blob is structured as a sequence of non-homogenous structures. Each structure begins with C like string key (i.e. zero-terminated sequence of bytes). If the key is non-empty string, it is followed by an instance of the struct TVTriePage. If the key is an empty string, it marks the end of the sequence.
Since the page-key is just a part of the searched word (trie), each word present in the trie has to have its part in the page (in b-tree it does not hold).
The following example shows the structure. Ptrs stands for struct TVTriePagePtrs.
+---------------------+---------------------+-----+---------------------+----+ | k0-letters\0 | Ptrs | k1-letters\0 | Ptrs | ... | kn-letters\0 | Ptrs | \0 | +---------------------+---------------------+-----+---------------------+----+ k0 < k1 < ... < kn
SOURCE
78 struct TVTriePage { 79 uint32_t size; 80 char *data; 81 };
TVTrie/struct TVTriePagePtrs [ Structures ]
[ Top ] [ TVTrie ] [ Structures ]
NAME
struct TVTriePagePtrs -- a structure of the tree page
FUNCTION
The structure desctibes a part of a page of the tree. The root of the tree would be this type.
ATTRIBUTES
- dtr -- pointer to a daughter or NULL if the containing page is a list.
- user_data -- user's data. It is also used to recognize whether the page-key finishes a word. If so, the value shall not be equal to V_TRIE_NO_USER_DATA. If it is equal, the key is considered to finish a whole word.
SOURCE
98 struct TVTriePagePtrs { 99 struct TVTriePage *dtr; 100 v_trie_user_t user_data; 101 };
TVTrie/v_trie_free [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_free -- frees an alocated page.
FUNCTION
The function frees an alocated page.
INPUTS
- pg -- a pointer to the page to free.
RESULT
None.
SOURCE
129 void v_trie_free(struct TVTriePage *pg);
TVTrie/v_trie_insert [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_insert -- inserts a word into the tree.
SYNOPSIS
136 *v_trie_insert(root, "world") = 56;
FUNCTION
The function inserts a key into the tree. If the key is already present, it just returns data associated with it.
INPUTS
- pg -- the root page of the tree.
- string -- a word to insert.
RESULT
The result is a pointer to user's data associated with the inserted word.
EXAMPLE
146 v_trie_user_t *color = v_trie_insert(root, "apple"); 147 old_color = *color; 148 *color = new_color;
SOURCE
151 v_trie_user_t *v_trie_insert(struct TVTriePage *pg, const char *string);
TVTrie/v_trie_load [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_load -- creates a tree from the fd.
FUNCTION
The function loads the tree from a filedescriptor.
INPUTS
- fd -- a filedescriptor to write the tree to.
RESULT
The result is a pointer to a root page of the loaded tree.
SOURCE
181 struct TVTriePage *v_trie_load(int fd);
TVTrie/v_trie_lookup [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_lookup -- an abstract function to lookup a key
SYNOPSIS
222 v_trie_user_t *val = v_trie_lookup(root, "key");
INPUTS
- root -- a root page of the tree
- word -- a searched word.
RESULT
Returns pointer to data associated with the key or NULL if the key is not present. NOTE No such function is implemented. It only shows how to lookup the tree.
SOURCE
231 v_trie_user_t *v_trie_lookup(struct TVTriePage *root, const char *word) { 232 char *d = root->data; 233 (* find the first letter of the key in the page *) 234 while ( *d != '\0' && *d < *word) { 235 d = v_trie_skip(d); 236 } 237 238 (* check whether prefixes match *) 239 if ( *d == *word) { 240 const char *k = d+1; word++; 241 while ( *k != '\0' && *k == *word) { k++; word++; } 242 if ( *k == '\0') { (* match *) 243 const struct TVTriePagePtrs *ptrs = 244 (const struct TVTriePagePtrs *) (k + 1); 245 if ( *word == '\0' && ptrs->user_data != V_TRIE_NO_USER_DATA) { 246 (* the word has been whole matched and is present *) 247 return &ptrs->user_data; 248 } 249 if (ptrs->dtr != NULL && *word != '\0') { 250 (* the end of the word remains to be matched *) 251 v_trie_lookup(ptrs->dtr, word); 252 } 253 } 254 } 255 return NULL; 256 }
TVTrie/v_trie_new_page [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_new_page -- alocates a new tree page.
FUNCTION
The function alocates and initializas a new tree page.
INPUTS
- size -- page capacity.
RESULT
A pointer to the new page.
SOURCE
115 struct TVTriePage *v_trie_new_page(size_t size);
TVTrie/V_TRIE_NEW_PAGE_SIZE [ Definitions ]
[ Top ] [ TVTrie ] [ Definitions ]
NAME
V_TRIE_NEW_PAGE_SIZE -- minimal size of a new allocated page
SOURCE
31 #define V_TRIE_NEW_PAGE_SIZE 64
TVTrie/V_TRIE_NO_USER_DATA [ Definitions ]
[ Top ] [ TVTrie ] [ Definitions ]
NAME
V_TRIE_NO_USER_DATA -- a value of v_trie_user_t type that marks that the page-key does not finish a word.
SOURCE
40 #define V_TRIE_NO_USER_DATA (v_trie_user_t) -1
TVTrie/v_trie_skip [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_skip -- skips a key-ptrs couple.
SYNOPSIS
188 d = v_trie_skip(d);
FUNCTION
The function skips one key-ptrs record.
INPUTS
- d -- a pointer to the current position in a page.
RESULT
The result is a pointer to the next position in a page.
EXAMPLE
196 (* look for a first letter of a string *) 197 char *d = pg->data; 198 while ( *d != '\0' (* list stop mark *) && *d < *string) { 199 d = v_trie_skip(d); (* try next *) 200 } 201 if ( *d == *string) { 202 (* do something *) 203 }
NOTES
If called at the end-of-page, the unchanged input pointer is returned;
SOURCE
208 static inline char *v_trie_skip(char *d);
TVTrie/v_trie_store [ Functions ]
[ Top ] [ TVTrie ] [ Functions ]
NAME
v_trie_store -- serializes a tree to the fd.
FUNCTION
The function stores the tree into a filedescriptor.
INPUTS
- fd -- a filedescriptor to write the tree to.
- root -- the root page of the tree.
RESULT
None.
SOURCE
167 void v_trie_store(int fd, struct TVTriePage *root);
TVTrie/v_trie_user_t [ Types ]
NAME
v_trie_user_t -- a type of the user's data
FUNCTION
The type defines a type of the user's data that could be stored in the page with a key. It is up to the user to mark whether the page-key finishes a word or is merely a beginning or a middle part of it.
SOURCE
23 typedef uint32_t v_trie_user_t;