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
|
/*
* upb - a minimalist implementation of protocol buffers.
*
* Copyright (c) 2009 Joshua Haberman. See LICENSE for details.
*
* This file defines very fast int->struct (inttable) and string->struct
* (strtable) hash tables. The struct can be of any size, and it is stored
* in the table itself, for cache-friendly performance.
*
* The table uses internal chaining with Brent's variation (inspired by the
* Lua implementation of hash tables). The hash function for strings is
* Austin Appleby's "MurmurHash."
*/
#ifndef UPB_TABLE_H_
#define UPB_TABLE_H_
#include <assert.h>
#include "upb.h"
#include "upb_string.h"
#ifdef __cplusplus
extern "C" {
#endif
/* Note: the key cannot be zero! Zero is used by the implementation. */
typedef uint32_t upb_inttable_key_t;
#define UPB_END_OF_CHAIN (uint32_t)0
#define UPB_EMPTY_ENTRY (uint32_t)0
struct upb_inttable_entry {
upb_inttable_key_t key;
uint32_t next; /* Internal chaining. */
};
/* TODO: consider storing the hash in the entry. This would avoid the need to
* rehash on table resizes, but more importantly could possibly improve lookup
* performance by letting us compare hashes before comparing lengths or the
* strings themselves. */
struct upb_strtable_entry {
struct upb_string key;
uint32_t next; /* Internal chaining. */
};
struct upb_table {
void *entries;
uint32_t count; /* How many elements are currently in the table? */
uint16_t entry_size; /* How big is each entry? */
uint8_t size_lg2; /* The table is 2^size_lg2 in size. */
uint32_t mask;
};
struct upb_strtable {
struct upb_table t;
};
struct upb_inttable {
struct upb_table t;
};
/* Initialize and free a table, respectively. Specify the initial size
* with 'size' (the size will be increased as necessary). Entry size
* specifies how many bytes each entry in the table is. */
void upb_inttable_init(struct upb_inttable *table,
uint32_t size, uint16_t entry_size);
void upb_inttable_free(struct upb_inttable *table);
void upb_strtable_init(struct upb_strtable *table,
uint32_t size, uint16_t entry_size);
void upb_strtable_free(struct upb_strtable *table);
INLINE uint32_t upb_table_size(struct upb_table *t) { return 1 << t->size_lg2; }
INLINE uint32_t upb_inttable_size(struct upb_inttable *t) {
return upb_table_size(&t->t);
}
INLINE uint32_t upb_strtable_size(struct upb_strtable *t) {
return upb_table_size(&t->t);
}
/* Inserts the given key into the hashtable with the given value. The key must
* not already exist in the hash table. The data will be copied from e into
* the hashtable (the amount of data copied comes from entry_size when the
* table was constructed). Therefore the data at val may be freed once the
* call returns. */
void upb_inttable_insert(struct upb_inttable *t, struct upb_inttable_entry *e);
void upb_strtable_insert(struct upb_strtable *t, struct upb_strtable_entry *e);
INLINE uint32_t upb_inttable_bucket(struct upb_inttable *t, upb_inttable_key_t k) {
return (k & t->t.mask) + 1; /* Identity hash for ints. */
}
/* Looks up key in this table. Inlined because this is in the critical path
* of parsing. We have the caller specify the entry_size because fixing
* this as a literal (instead of reading table->entry_size) gives the
* compiler more ability to optimize. */
INLINE void *upb_inttable_lookup(struct upb_inttable *t,
uint32_t key, uint32_t entry_size) {
assert(key != 0);
uint32_t bucket = upb_inttable_bucket(t, key);
struct upb_inttable_entry *e;
do {
e = (struct upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size);
if(e->key == key) return e;
} while((bucket = e->next) != UPB_END_OF_CHAIN);
return NULL; /* Not found. */
}
void *upb_strtable_lookup(struct upb_strtable *t, struct upb_string *key);
/* Provides iteration over the table. The order in which the entries are
* returned is undefined. Insertions invalidate iterators. The _next
* functions return NULL when the end has been reached. */
void *upb_inttable_begin(struct upb_inttable *t);
void *upb_inttable_next(struct upb_inttable *t, struct upb_inttable_entry *cur);
void *upb_strtable_begin(struct upb_strtable *t);
void *upb_strtable_next(struct upb_strtable *t, struct upb_strtable_entry *cur);
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif /* UPB_TABLE_H_ */
|
