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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
#ifndef _MAP_H_ /* -*- linux-c -*- */
#define _MAP_H_
/** @file map.h
* @brief Header file for maps and lists
*/
/** @addtogroup maps
* @todo Needs a spinlock variable to help when locks are required on the map.
* @{
*/
/* This sets the size of the hash table. */
#ifndef HASH_TABLE_BITS
#define HASH_TABLE_BITS 8
/* This sets the size of the hash table. */
#define HASH_TABLE_SIZE (1<<HASH_TABLE_BITS)
#endif
/* The maximum number of keys allowed. Reducing this can save a small
amount of memory. Do not increase above 5. */
#ifndef MAX_KEY_ARITY
#define MAX_KEY_ARITY 5
#endif
/** Maximum length of strings in maps. This sets the amount of space reserved
for each string. */
#ifndef MAP_STRING_LENGTH
#define MAP_STRING_LENGTH 256
#endif
/** @cond DONT_INCLUDE */
#define INT64 0
#define STRING 1
#define STAT 2
#define END 3
/** @endcond */
#include "stat.h"
/* Histogram is log 2 */
#define HSTAT_LOG (STAT | (HIST_LOG << 8))
/* Histogram is linear */
#define HSTAT_LINEAR (STAT | (HIST_LINEAR << 8))
/* Keys are either int64 or strings */
typedef union {
int64_t val;
char *strp;
} key_data;
/* basic map element */
struct map_node {
/* list of other nodes in the map */
struct list_head lnode;
/* list of nodes with the same hash value */
struct hlist_node hnode;
/* pointer back to the map struct */
struct map_root *map;
};
/* This structure contains all information about a map.
* It is allocated once when _stp_map_new() is called.
*/
struct map_root {
/* type of the value stored in the array */
int type;
/* maximum number of elements allowed in the array. */
int maxnum;
/* current number of used elements */
int num;
/* when more than maxnum elements, wrap or discard? */
int no_wrap;
/* linked list of current entries */
struct list_head head;
/* pool of unused entries. */
struct list_head pool;
/* saved key entry for lookups */
struct map_node *key;
/* This is information about the structure of the map_nodes used */
/* for this map. It is stored here instead of the map_node to save */
/* space. */
void (*copy_keys)(struct map_root *, struct map_node *);
key_data (*get_key)(struct map_node *mn, int n, int *type);
int data_offset;
/* this is the creation data saved between the key functions and the
set/get functions */
u_int8_t create;
key_data c_key[MAX_KEY_ARITY];
struct hlist_head *c_keyhead;
/* the hash table for this array */
struct hlist_head hashes[HASH_TABLE_SIZE];
/* pointer to allocated memory space. Used for freeing memory. */
void *membuf;
/* used if this map's nodes contain stats */
enum histtype hist_type;
int hist_start;
int hist_stop;
int hist_int;
int hist_buckets;
};
/** All maps are of this type. */
typedef struct map_root *MAP;
/** Extracts string from key1 union */
#define key1str(ptr) (_stp_key_get_str(ptr,1))
/** Extracts string from key2 union */
#define key2str(ptr) (_stp_key_get_str(ptr,2))
/** Extracts int from key1 union */
#define key1int(ptr) (_stp_key_get_int64(ptr,1))
/** Extracts int from key2 union */
#define key2int(ptr) (_stp_key_get_int64(ptr,2))
/** Macro to call the proper _stp_map_key functions based on the
* types of the arguments.
*/
#define _stp_map_key2(map, key1, key2) \
({ \
if (__builtin_types_compatible_p (typeof (key1), char[])) \
if (__builtin_types_compatible_p (typeof (key2), char[])) \
_stp_map_key_str_str (map, (char *)(key1), (char *)(key2)); \
else \
_stp_map_key_str_int64 (map, (char *)(key1), (int64_t)(key2)); \
else \
if (__builtin_types_compatible_p (typeof (key2), char[])) \
_stp_map_key_int64_str (map, (int64_t)(key1), (char *)(key2)); \
else \
_stp_map_key_int64_int64 (map, (int64_t)(key1), (int64_t)(key2)); \
})
/** Macro to call the proper _stp_map_key function based on the
* type of the argument.
*/
#define _stp_map_key(map, key) \
({ \
if (__builtin_types_compatible_p (typeof (key), char[])) \
_stp_map_key_str (map, (char *)(key)); \
else \
_stp_map_key_int64 (map, (int64_t)(key)); \
})
/** Macro to call the proper _stp_map_set function based on the
* type of the argument.
* @ingroup map_set
*/
#define _stp_map_set(map, val) \
({ \
if (__builtin_types_compatible_p (typeof (val), char[])) \
_stp_map_set_str (map, (char *)(val)); \
else if (__builtin_types_compatible_p (typeof (val), String)) \
_stp_map_set_string (map, (String)(val)); \
else \
_stp_map_set_int64 (map, (int64_t)(val)); \
})
/** Loop through all elements of a map or list.
* @param map
* @param ptr pointer to a map_node_stat, map_node_int64 or map_node_str
*
* @b Example:
* @include foreach.c
*/
#define foreach(map, ptr) \
for (ptr = _stp_map_start(map); ptr; ptr = _stp_map_iter (map, ptr))
/** @} */
/** @ingroup lists
* @brief Macro to call the proper _stp_list_add function based on the
* types of the argument.
*
* @note May cause compiler warning on some GCCs
*/
#define _stp_list_add(map, val) \
({ \
if (__builtin_types_compatible_p (typeof (val), char[])) \
_stp_list_add_str (map, (char *)(val)); \
else if (__builtin_types_compatible_p (typeof (val), String)) \
_stp_list_add_string (map, (String)(val)); \
else \
_stp_list_add_int64 (map, (int64_t)(val)); \
})
/** @cond DONT_INCLUDE */
/************* prototypes for map.c ****************/
int int64_eq_p(int64_t key1, int64_t key2);
void int64_copy(void *dest, int64_t val);
void int64_add(void *dest, int64_t val);
int64_t int64_get(void *ptr);
void stat_copy(void *dest, stat *src);
void stat_add(void *dest, stat *src);
stat * stat_get(void *ptr);
int64_t _stp_key_get_int64(struct map_node *mn, int n);
char * _stp_key_get_str(struct map_node *mn, int n);
unsigned int int64_hash(const int64_t v);
char * str_get(void *ptr);
void str_copy(char *dest, char *src);
void str_add(void *dest, char *val);
int str_eq_p(char *key1, char *key2);
int64_t _stp_get_int64(struct map_node *m);
char * _stp_get_str(struct map_node *m);
stat * _stp_get_stat(struct map_node *m);
unsigned int str_hash(const char *key1);
static MAP _stp_map_new(unsigned max_entries, int type, int key_size, int data_size);
#ifdef NEED_STAT_VALS
static int msb64(int64_t x);
static MAP _stp_map_new_hstat_log(unsigned max_entries, int key_size, int buckets);
static MAP _stp_map_new_hstat_linear(unsigned max_entries, int ksize, int start, int stop, int interval);
static void _stp_map_print_histogram(MAP map, stat *s);
#endif
void _stp_map_key_del(MAP map);
struct map_node * _stp_map_start(MAP map);
struct map_node * _stp_map_iter(MAP map, struct map_node *m);
void _stp_map_del(MAP map);
void _stp_map_print(MAP map, const char *fmt);
static struct map_node * __stp_map_create(MAP map);
/* these prototypes suppress warnings from macros */
void _stp_map_key_str(MAP, char *);
void _stp_map_set_str(MAP, char *);
void _stp_map_set_string(MAP, String);
void _stp_list_add_str(MAP, char*);
void _stp_list_add_string(MAP, String);
void _stp_map_key_int64(MAP, int64_t);
void _stp_map_set_int64(MAP, int64_t);
int64_t _stp_map_get_int64(MAP);
/** @endcond */
#endif /* _MAP_H_ */
|
