LibDocument

image-alt

Document and Trie Processing.


trie.h

Version: 0.1.1

Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015-2016 CODAMONO, Ontario, Canada
3  *
4  * This Source Code Form is subject to the terms of the Mozilla Public
5  * License, v. 2.0. If a copy of the MPL was not distributed with this
6  * file, You can obtain one at: http://mozilla.org/MPL/2.0/
7  */
8 
15 #ifndef __ldoc__trie__
16 #define __ldoc__trie__
17 
18 #include <stdbool.h>
19 #include <stdint.h>
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <string.h>
23 #include <sys/queue.h>
24 #include <unistd.h>
25 
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29 
35 #define LDOC_TRIE_NDS_ARR_INIT 64
36 
41 #define LDOC_TRIE_NDS_ARR_INC 16
42 
46 #define LDOC_TRIE_RES_CHR '^'
47 
55 typedef enum
56 {
83 
93 typedef enum
94 {
108 
112 typedef struct ldoc_trie_anno_t
113 {
119  uint16_t cat;
123  void* pld;
125 
130 
135 
139 typedef union
140 {
144  void* c0;
148  char* c8;
152  uint16_t* c16;
156  uint32_t* c32;
158 
162 typedef struct ldoc_trie_nde_t
163 {
172  uint16_t size;
192 
200 typedef struct ldoc_trie_nde_arr_t
201 {
205  size_t wptr;
209  size_t max;
215 
219 typedef struct ldoc_trie_t
220 {
225  uint16_t min;
229  uint16_t max;
234 } ldoc_trie_t;
235 
236 #pragma mark - Trie Allocation/Deallocation
237 
244 
253 void ldoc_trie_free(ldoc_trie_t* trie);
254 
255 #pragma mark - Trie-Node Array CRUD
256 
265 
274 
285 
286 #pragma mark - Trie Updates/Modifications
287 
296 void ldoc_trie_add(ldoc_trie_t* trie, const char* str, ldoc_trie_ptr_t tpe, ldoc_trie_anno_t anno);
297 
305 ldoc_trie_nde_t* ldoc_trie_remove(ldoc_trie_t* trie, const char* str);
306 
307 #pragma mark - Trie Search
308 
317 ldoc_trie_nde_t* ldoc_trie_lookup(ldoc_trie_t* trie, const char* string, bool prefixes);
318 
319 #pragma mark - Summarization
320 
328 char* ldoc_trie_collect(ldoc_trie_t* trie, const char* sep);
329 
330 #pragma mark - Debugging
331 
337 void ldoc_trie_dmp(ldoc_trie_t* trie);
338 
339 #ifdef __cplusplus
340 } /* extern "C" */
341 #endif
342 
343 #endif /* defined(__ldoc__trie__) */
344 
void ldoc_trie_dmp(ldoc_trie_t *trie)
Produce debugging output of a trie on STDOUT.
ldoc_trie_alloc_t alloc
Definition: trie.h:186
size_t wptr
Definition: trie.h:205
void ldoc_trie_add(ldoc_trie_t *trie, const char *str, ldoc_trie_ptr_t tpe, ldoc_trie_anno_t anno)
Adds a string to a trie.
Trie node.
Definition: trie.h:162
void ldoc_trie_nde_arr_free(ldoc_trie_nde_arr_t *arr)
Frees a trie-node array.
ldoc_trie_nde_t * ldoc_trie_lookup(ldoc_trie_t *trie, const char *string, bool prefixes)
Lookup a string in a trie.
uint16_t max
Definition: trie.h:229
ldoc_trie_ptr_t
Type of pointer used to access descendant trie nodes.
Definition: trie.h:55
uint16_t * c16
Definition: trie.h:152
char * ldoc_trie_collect(ldoc_trie_t *trie, const char *sep)
Create a list of all strings in a trie.
uint16_t cat
Definition: trie.h:119
Definition: trie.h:65
ldoc_trie_nde_t ** nds
Definition: trie.h:213
void * pld
Definition: trie.h:123
ldoc_trie_alloc_t
Trie-node type.
Definition: trie.h:93
ldoc_trie_nde_t * ldoc_trie_remove(ldoc_trie_t *trie, const char *str)
Remove a string (prefix) from a trie.
uint16_t min
Definition: trie.h:225
uint32_t * c32
Definition: trie.h:156
ldoc_trie_anno_t LDOC_TRIE_ANNO_NULL
Null pointer for trie annotations.
Definition: trie.h:69
struct ldoc_trie_anno_t ldoc_trie_anno_t
Trie node annotation.
ldoc_trie_nde_t * root
Definition: trie.h:233
char * c8
Definition: trie.h:148
Trie-node array.
Definition: trie.h:200
uint16_t size
Definition: trie.h:172
void * c0
Definition: trie.h:144
Definition: trie.h:102
Definition: trie.h:106
struct ldoc_trie_t ldoc_trie_t
A trie (prefix tree).
struct ldoc_trie_nde_t ** dscs
Definition: trie.h:182
ldoc_trie_anno_t LDOC_TRIE_NDE_NULL
Null pointer for trie nodes.
ldoc_trie_anno_t anno
Definition: trie.h:190
A trie (prefix tree).
Definition: trie.h:219
Character pointer types.
Definition: trie.h:139
Definition: trie.h:60
struct ldoc_trie_nde_arr_t ldoc_trie_nde_arr_t
Trie-node array.
Trie node annotation.
Definition: trie.h:112
void ldoc_trie_free(ldoc_trie_t *trie)
Frees the memory of a trie object.
ldoc_trie_ptr_t tpe
Definition: trie.h:168
Definition: trie.h:81
Definition: trie.h:98
void ldoc_trie_nde_arr_appnd(ldoc_trie_nde_arr_t *arr, ldoc_trie_nde_t *nde)
Appends a node at the end of a trie-node array.
ldoc_trie_t * ldoc_trie_new()
Creates a new trie object (including trie root node).
size_t max
Definition: trie.h:209
ldoc_trie_char_t chr
Definition: trie.h:181
struct ldoc_trie_nde_t ldoc_trie_nde_t
Trie node.
ldoc_trie_nde_arr_t * ldoc_trie_nde_arr_new()
Creates a new trie-node array.
Definition: trie.h:75