VLib/TVTrie [ Modules ]

[ Top ] [ Modules ]

NAME

TVTrie -- a trie data structure.

HISTORY


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

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

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

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

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

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

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

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

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

RESULT

None.

SOURCE

167 void v_trie_store(int fd, struct TVTriePage *root);

TVTrie/v_trie_user_t [ Types ]

[ Top ] [ TVTrie ] [ 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;