-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpoptrie.h
146 lines (117 loc) · 3.32 KB
/
poptrie.h
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*_
* Copyright (c) 2014-2017 Hirochika Asai <[email protected]>
* All rights reserved.
*/
#ifndef _POPTRIE_H
#define _POPTRIE_H
#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
/* The bit length used for direct pointing. The most significant POPTRIE_S bits
of keys will be tested at the first stage of the trie search in O(1). */
#define POPTRIE_S 18
/* The initial size of forwarding information base (FIB). In the current
version of this software, new entries exceeding this size will result in an
error. This parameter must be less than 65535. */
#define POPTRIE_INIT_FIB_SIZE 4096
/* 64-bit popcnt intrinsic. To use popcnt instruction in x86-64, the "-mpopcnt"
option must be specified in CFLAGS. */
#define popcnt(v) __builtin_popcountll(v)
/* Internal node; 24-byte data structure */
typedef struct poptrie_node {
/* Leafvec */
u64 leafvec;
/* Vector */
u64 vector;
/* Base for leaf nodes */
u32 base0;
/* Base for descendant internal nodes */
u32 base1;
} poptrie_node_t;
/* Leaf node; 16-bit value */
typedef u16 poptrie_leaf_t;
/* FIB index */
typedef u16 poptrie_fib_index_t;
/*
* Radix tree node
*/
struct radix_node {
int valid;
struct radix_node *left;
struct radix_node *right;
/* Next hop */
int len;
poptrie_leaf_t nexthop;
/* Propagated route for invalid intermediate nodes from a valid parent */
struct radix_node *ext;
/* Mark for update */
int mark;
};
/*
* FIB mapping table
*/
struct poptrie_fib_entry {
void *entry;
int refs;
};
struct poptrie_fib {
struct poptrie_fib_entry *entries;
int sz;
};
/*
* Poptrie management data structure
*/
struct poptrie {
/* Root */
u32 root;
/* FIB */
struct poptrie_fib fib;
/* Memory management data structure for buddy system */
poptrie_node_t *nodes;
poptrie_leaf_t *leaves;
void *cnodes;
void *cleaves;
/* Allocated sizes for internal nodes and leaves */
int nodesz;
int leafsz;
/* Array for direct pointing */
u32 *dir;
u32 *altdir;
/* RIB */
struct radix_node *radix;
/* Control */
int _allocated;
};
#ifdef __cplusplus
extern "C" {
#endif
/* in poptrie.c */
struct poptrie * poptrie_init(struct poptrie *, int, int);
void poptrie_release(struct poptrie *);
int poptrie_route_add(struct poptrie *, u32, int, void *);
int poptrie_route_change(struct poptrie *, u32, int, void *);
int poptrie_route_update(struct poptrie *, u32, int, void *);
int poptrie_route_del(struct poptrie *, u32, int);
void * poptrie_lookup(struct poptrie *, u32);
void * poptrie_rib_lookup(struct poptrie *, u32);
/* in poptrie6.c */
int poptrie6_route_add(struct poptrie *, __uint128_t, int, void *);
int poptrie6_route_change(struct poptrie *, __uint128_t, int, void *);
int poptrie6_route_update(struct poptrie *, __uint128_t, int, void *);
int poptrie6_route_del(struct poptrie *, __uint128_t, int);
void * poptrie6_lookup(struct poptrie *, __uint128_t);
void * poptrie6_rib_lookup(struct poptrie *, __uint128_t);
#ifdef __cplusplus
}
#endif
#endif /* _POPTRIE_H */
/*
* Local variables:
* tab-width: 4
* c-basic-offset: 4
* End:
* vim600: sw=4 ts=4 fdm=marker
* vim<600: sw=4 ts=4
*/