/src/nghttp2/lib/nghttp2_map.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * nghttp2 - HTTP/2 C Library |
3 | | * |
4 | | * Copyright (c) 2012 Tatsuhiro Tsujikawa |
5 | | * |
6 | | * Permission is hereby granted, free of charge, to any person obtaining |
7 | | * a copy of this software and associated documentation files (the |
8 | | * "Software"), to deal in the Software without restriction, including |
9 | | * without limitation the rights to use, copy, modify, merge, publish, |
10 | | * distribute, sublicense, and/or sell copies of the Software, and to |
11 | | * permit persons to whom the Software is furnished to do so, subject to |
12 | | * the following conditions: |
13 | | * |
14 | | * The above copyright notice and this permission notice shall be |
15 | | * included in all copies or substantial portions of the Software. |
16 | | * |
17 | | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
18 | | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
19 | | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
20 | | * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
21 | | * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
22 | | * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
23 | | * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
24 | | */ |
25 | | #include "nghttp2_map.h" |
26 | | |
27 | | #include <string.h> |
28 | | |
29 | 0 | #define INITIAL_TABLE_LENGTH 256 |
30 | | |
31 | 0 | int nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) { |
32 | 0 | map->mem = mem; |
33 | 0 | map->tablelen = INITIAL_TABLE_LENGTH; |
34 | 0 | map->table = |
35 | 0 | nghttp2_mem_calloc(mem, map->tablelen, sizeof(nghttp2_map_entry *)); |
36 | 0 | if (map->table == NULL) { |
37 | 0 | return NGHTTP2_ERR_NOMEM; |
38 | 0 | } |
39 | | |
40 | 0 | map->size = 0; |
41 | |
|
42 | 0 | return 0; |
43 | 0 | } |
44 | | |
45 | 0 | void nghttp2_map_free(nghttp2_map *map) { |
46 | 0 | nghttp2_mem_free(map->mem, map->table); |
47 | 0 | } |
48 | | |
49 | | void nghttp2_map_each_free(nghttp2_map *map, |
50 | | int (*func)(nghttp2_map_entry *entry, void *ptr), |
51 | 0 | void *ptr) { |
52 | 0 | uint32_t i; |
53 | 0 | for (i = 0; i < map->tablelen; ++i) { |
54 | 0 | nghttp2_map_entry *entry; |
55 | 0 | for (entry = map->table[i]; entry;) { |
56 | 0 | nghttp2_map_entry *next = entry->next; |
57 | 0 | func(entry, ptr); |
58 | 0 | entry = next; |
59 | 0 | } |
60 | 0 | map->table[i] = NULL; |
61 | 0 | } |
62 | 0 | } |
63 | | |
64 | | int nghttp2_map_each(nghttp2_map *map, |
65 | | int (*func)(nghttp2_map_entry *entry, void *ptr), |
66 | 0 | void *ptr) { |
67 | 0 | int rv; |
68 | 0 | uint32_t i; |
69 | 0 | for (i = 0; i < map->tablelen; ++i) { |
70 | 0 | nghttp2_map_entry *entry; |
71 | 0 | for (entry = map->table[i]; entry; entry = entry->next) { |
72 | 0 | rv = func(entry, ptr); |
73 | 0 | if (rv != 0) { |
74 | 0 | return rv; |
75 | 0 | } |
76 | 0 | } |
77 | 0 | } |
78 | 0 | return 0; |
79 | 0 | } |
80 | | |
81 | 0 | void nghttp2_map_entry_init(nghttp2_map_entry *entry, key_type key) { |
82 | 0 | entry->key = key; |
83 | 0 | entry->next = NULL; |
84 | 0 | } |
85 | | |
86 | | /* Same hash function in android HashMap source code. */ |
87 | | /* The |mod| must be power of 2 */ |
88 | 0 | static uint32_t hash(int32_t key, uint32_t mod) { |
89 | 0 | uint32_t h = (uint32_t)key; |
90 | 0 | h ^= (h >> 20) ^ (h >> 12); |
91 | 0 | h ^= (h >> 7) ^ (h >> 4); |
92 | 0 | return h & (mod - 1); |
93 | 0 | } |
94 | | |
95 | | static int insert(nghttp2_map_entry **table, uint32_t tablelen, |
96 | 0 | nghttp2_map_entry *entry) { |
97 | 0 | uint32_t h = hash(entry->key, tablelen); |
98 | 0 | if (table[h] == NULL) { |
99 | 0 | table[h] = entry; |
100 | 0 | } else { |
101 | 0 | nghttp2_map_entry *p; |
102 | | /* We won't allow duplicated key, so check it out. */ |
103 | 0 | for (p = table[h]; p; p = p->next) { |
104 | 0 | if (p->key == entry->key) { |
105 | 0 | return NGHTTP2_ERR_INVALID_ARGUMENT; |
106 | 0 | } |
107 | 0 | } |
108 | 0 | entry->next = table[h]; |
109 | 0 | table[h] = entry; |
110 | 0 | } |
111 | 0 | return 0; |
112 | 0 | } |
113 | | |
114 | | /* new_tablelen must be power of 2 */ |
115 | 0 | static int resize(nghttp2_map *map, uint32_t new_tablelen) { |
116 | 0 | uint32_t i; |
117 | 0 | nghttp2_map_entry **new_table; |
118 | |
|
119 | 0 | new_table = |
120 | 0 | nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_entry *)); |
121 | 0 | if (new_table == NULL) { |
122 | 0 | return NGHTTP2_ERR_NOMEM; |
123 | 0 | } |
124 | | |
125 | 0 | for (i = 0; i < map->tablelen; ++i) { |
126 | 0 | nghttp2_map_entry *entry; |
127 | 0 | for (entry = map->table[i]; entry;) { |
128 | 0 | nghttp2_map_entry *next = entry->next; |
129 | 0 | entry->next = NULL; |
130 | | /* This function must succeed */ |
131 | 0 | insert(new_table, new_tablelen, entry); |
132 | 0 | entry = next; |
133 | 0 | } |
134 | 0 | } |
135 | 0 | nghttp2_mem_free(map->mem, map->table); |
136 | 0 | map->tablelen = new_tablelen; |
137 | 0 | map->table = new_table; |
138 | |
|
139 | 0 | return 0; |
140 | 0 | } |
141 | | |
142 | 0 | int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_entry *new_entry) { |
143 | 0 | int rv; |
144 | | /* Load factor is 0.75 */ |
145 | 0 | if ((map->size + 1) * 4 > map->tablelen * 3) { |
146 | 0 | rv = resize(map, map->tablelen * 2); |
147 | 0 | if (rv != 0) { |
148 | 0 | return rv; |
149 | 0 | } |
150 | 0 | } |
151 | 0 | rv = insert(map->table, map->tablelen, new_entry); |
152 | 0 | if (rv != 0) { |
153 | 0 | return rv; |
154 | 0 | } |
155 | 0 | ++map->size; |
156 | 0 | return 0; |
157 | 0 | } |
158 | | |
159 | 0 | nghttp2_map_entry *nghttp2_map_find(nghttp2_map *map, key_type key) { |
160 | 0 | uint32_t h; |
161 | 0 | nghttp2_map_entry *entry; |
162 | 0 | h = hash(key, map->tablelen); |
163 | 0 | for (entry = map->table[h]; entry; entry = entry->next) { |
164 | 0 | if (entry->key == key) { |
165 | 0 | return entry; |
166 | 0 | } |
167 | 0 | } |
168 | 0 | return NULL; |
169 | 0 | } |
170 | | |
171 | 0 | int nghttp2_map_remove(nghttp2_map *map, key_type key) { |
172 | 0 | uint32_t h; |
173 | 0 | nghttp2_map_entry **dst; |
174 | |
|
175 | 0 | h = hash(key, map->tablelen); |
176 | |
|
177 | 0 | for (dst = &map->table[h]; *dst; dst = &(*dst)->next) { |
178 | 0 | if ((*dst)->key != key) { |
179 | 0 | continue; |
180 | 0 | } |
181 | | |
182 | 0 | *dst = (*dst)->next; |
183 | 0 | --map->size; |
184 | 0 | return 0; |
185 | 0 | } |
186 | 0 | return NGHTTP2_ERR_INVALID_ARGUMENT; |
187 | 0 | } |
188 | | |
189 | 0 | size_t nghttp2_map_size(nghttp2_map *map) { return map->size; } |