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
|
/* Level-Compressed Tree Bitmap (LC-TBM) Trie implementation
*
* Contributed by Geoffrey T. Dairiki <dairiki@dairiki.org>
*
* This file is released under a "Three-clause BSD License".
*
* Copyright (c) 2013, Geoffrey T. Dairiki
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* * Neither the name of Geoffrey T. Dairiki nor the names of other
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GEOFFREY
* T. DAIRIKI BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
* USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*/
#ifndef _BTRIE_H_INCLUDED
#define _BTRIE_H_INCLUDED
#include "config.h"
#include <stdint.h>
typedef uint8_t btrie_oct_t;
/* maximum length of bit string btrie_walk() can handle
*
* note: this limit is necessitated by the use of fixed length buffers
* in btrie_walk() --- btrie_add_prefix() and btrie_lookup() impose no
* limit on the length of bitstrings
*/
#define BTRIE_MAX_PREFIX 128
struct btrie;
struct memory_pool_s;
struct btrie * btrie_init(struct memory_pool_s *mp);
enum btrie_result
{
BTRIE_OKAY = 0,
BTRIE_ALLOC_FAILED = -1,
BTRIE_DUPLICATE_PREFIX = 1
};
enum btrie_result btrie_add_prefix(struct btrie *btrie,
const btrie_oct_t *prefix, unsigned len, const void *data);
const void *btrie_lookup(const struct btrie *btrie, const btrie_oct_t *pfx,
unsigned len);
const char *btrie_stats(const struct btrie *btrie, guint duplicates);
#ifndef NO_MASTER_DUMP
typedef void btrie_walk_cb_t(const btrie_oct_t *prefix, unsigned len,
const void *data, int post, void *user_data);
void btrie_walk(const struct btrie *btrie, btrie_walk_cb_t *callback,
void *user_data);
#endif /* not NO_MASTER_DUMP */
#endif /* _BTRIE_H_INCLUDED */
|
