1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
/*
* This file is part of hat-trie
*
* Copyright (c) 2011 by Daniel C. Jones <dcjones@cs.washington.edu>
*
*
* This is an implementation of the HAT-trie data structure described in,
*
* Askitis, N., & Sinha, R. (2007). HAT-trie: a cache-conscious trie-based data
* structure for strings. Proceedings of the thirtieth Australasian conference on
* Computer science-Volume 62 (pp. 97–105). Australian Computer Society, Inc.
*
* The HAT-trie is in essence a hybrid data structure, combining tries and hash
* tables in a clever way to try to get the best of both worlds.
*
*/
#ifndef HATTRIE_HATTRIE_H
#define HATTRIE_HATTRIE_H
#ifdef __cplusplus
extern "C" {
#endif
#include <stdlib.h>
#include <stdbool.h>
#include "libknot/common.h"
#include "common/mempattern.h"
#include "common/hhash.h"
/* Hat-trie defines. */
#define TRIE_ZEROBUCKETS 0 /* Do not use hash buckets (pure trie). */
#define TRIE_BUCKET_SIZE 765 /* Exactly 3x4K pages for 1 hhash. */
#define TRIE_MAXCHAR 0xff /* Use 7-bit ASCII alphabet. */
#define TRIE_EOK KNOT_EOK
typedef struct hattrie_t_ hattrie_t;
hattrie_t* hattrie_create (void); //< Create an empty hat-trie.
void hattrie_free (hattrie_t*); //< Free all memory used by a trie.
void hattrie_clear (hattrie_t*); //< Remove all entries.
size_t hattrie_weight (hattrie_t*); //< Number of entries
/** Create new trie with custom bucket size and memory management.
*/
hattrie_t* hattrie_create_n (unsigned, const mm_ctx_t *);
/** Duplicate an existing trie.
*/
hattrie_t* hattrie_dup (const hattrie_t*, value_t (*nval)(value_t));
/** Build order index on all ahtable nodes in trie.
*/
void hattrie_build_index (hattrie_t*);
int hattrie_apply_rev (hattrie_t*, int (*f)(value_t*,void*), void* d);
int hattrie_apply_rev_ahtable(hattrie_t* T, int (*f)(void*,void*), void* d);
/** Find the given key in the trie, inserting it if it does not exist, and
* returning a pointer to it's key.
*
* This pointer is not guaranteed to be valid after additional calls to
* hattrie_get, hattrie_del, hattrie_clear, or other functions that modifies the
* trie.
*/
value_t* hattrie_get (hattrie_t*, const char* key, size_t len);
/** Find a given key in the table, returning a NULL pointer if it does not
* exist. */
value_t* hattrie_tryget (hattrie_t*, const char* key, size_t len);
/** Find a given key in the table, returning a NULL pointer if it does not
* exist. Also set prev to point to previous node. */
int hattrie_find_leq (hattrie_t*, const char* key, size_t len, value_t** dst);
/** Find a longest prefix match. */
int hattrie_find_lpr (hattrie_t*, const char* key, size_t len, value_t** dst);
/** Delete a given key from trie. Returns 0 if successful or -1 if not found.
*/
int hattrie_del(hattrie_t* T, const char* key, size_t len);
typedef struct hattrie_iter_t_ hattrie_iter_t;
hattrie_iter_t* hattrie_iter_begin (const hattrie_t*, bool sorted);
void hattrie_iter_next (hattrie_iter_t*);
bool hattrie_iter_finished (hattrie_iter_t*);
void hattrie_iter_free (hattrie_iter_t*);
const char* hattrie_iter_key (hattrie_iter_t*, size_t* len);
value_t* hattrie_iter_val (hattrie_iter_t*);
#ifdef __cplusplus
}
#endif
#endif
|
