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
|
/*
* upb - a minimalist implementation of protocol buffers.
*
* Copyright (c) 2009 Joshua Haberman. See LICENSE for details.
*/
#ifndef UPB_TABLE_H_
#define UPB_TABLE_H_
#include "upb.h"
#ifdef __cplusplus
extern "C" {
#endif
typedef int32_t upb_inttable_key_t;
#define UPB_END_OF_CHAIN (upb_inttable_key_t)-1
struct upb_inttable_entry {
upb_inttable_key_t key;
int32_t next;
};
struct upb_inttable {
uint32_t size; /* Is a power of two. */
void *entries;
};
/* Builds an int32_t -> <entry> table, optimized for very fast lookup by
* number. table is a pointer to a previously allocated upb_inttable.
* entries points to an array of the desired entries themselves, each of size
* entry_size. The table is allocated in dynamic memory, and does not reference
* the data in entries. Entries may be modified by the function.
*
* The table must be freed with upb_inttable_free. */
void upb_inttable_init(struct upb_inttable *table, void *entries,
int num_entries, int entry_size);
inline int32_t upb_inttable_hash(struct upb_inttable * table,
upb_inttable_key_t key) {
return key & (table->size-1);
}
/* Frees any data that was allocated by upb_inttable_init. */
void upb_inttable_free(struct upb_inttable *table);
inline struct upb_inttable_entry *upb_inttable_entry_get(
void *entries, int32_t pos, int entry_size) {
return (struct upb_inttable_entry*)((char*)entries) + pos*entry_size;
}
inline struct upb_inttable_entry *upb_inttable_get(
struct upb_inttable *table, int32_t pos, int entry_size) {
return upb_inttable_entry_get(table->entries, pos, entry_size);
}
/* Lookups up key in this table. Inlined because this is in the critical path
* of parsing. */
inline void *upb_inttable_lookup(struct upb_inttable *table, int32_t key,
int entry_size) {
int32_t pos = upb_inttable_hash(table, key);
do {
struct upb_inttable_entry *e = upb_inttable_get(table, pos, entry_size);
if (key == e->key) return e;
pos = e->next;
} while (pos != UPB_END_OF_CHAIN);
return NULL; /* Not found. */
}
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif /* UPB_TABLE_H_ */
|
