BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file NCDStringIndex.c
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 #include <string.h>
31 #include <stdlib.h>
32  
33 #include <misc/hashfun.h>
34 #include <misc/strdup.h>
35 #include <misc/array_length.h>
36 #include <base/BLog.h>
37  
38 #include "NCDStringIndex.h"
39  
40 #include "NCDStringIndex_hash.h"
41 #include <structure/CHash_impl.h>
42  
43 #define GROWARRAY_NAME Array
44 #define GROWARRAY_OBJECT_TYPE NCDStringIndex
45 #define GROWARRAY_ARRAY_MEMBER entries
46 #define GROWARRAY_CAPACITY_MEMBER entries_capacity
47 #define GROWARRAY_MAX_CAPACITY NCD_STRING_ID_MAX
48 #include <misc/grow_array.h>
49  
50 #include <generated/blog_channel_ncd.h>
51  
52 // NOTE: keep synchronized with static_strings.h
53 static const char *static_strings[] = {
54 "",
55 "_args",
56 "_arg0",
57 "_arg1",
58 "_arg2",
59 "_arg3",
60 "_arg4",
61 "_arg5",
62 "_arg6",
63 "_arg7",
64 "_arg8",
65 "_arg9",
66 "_arg10",
67 "_arg11",
68 "_arg12",
69 "_arg13",
70 "_arg14",
71 "_arg15",
72 "_arg16",
73 "_arg17",
74 "_arg18",
75 "_arg19",
76 "true",
77 "false",
78 "<none>",
79 "_caller",
80 "succeeded",
81 "is_error",
82 "not_eof",
83 "length",
84 "type",
85 "exit_status",
86 "size",
87 "eof",
88 "_scope",
89 };
90  
91 static NCD_string_id_t do_get (NCDStringIndex *o, const char *str, size_t str_len)
92 {
93 ASSERT(str)
94  
95 NCDStringIndex_hash_key key = {str, str_len};
96 NCDStringIndex__HashRef ref = NCDStringIndex__Hash_Lookup(&o->hash, o->entries, key);
97 ASSERT(ref.link == -1 || ref.link >= 0)
98 ASSERT(ref.link == -1 || ref.link < o->entries_size)
99 ASSERT(ref.link == -1 || (ref.ptr->str_len == str_len && !memcmp(ref.ptr->str, str, str_len)))
100  
101 if (ref.link != -1) {
102 return ref.link;
103 }
104  
105 if (o->entries_size == o->entries_capacity) {
106 if (!Array_DoubleUp(o)) {
107 BLog(BLOG_ERROR, "Array_DoubleUp failed");
108 return -1;
109 }
110  
111 if (!NCDStringIndex__Hash_MultiplyBuckets(&o->hash, o->entries, 1)) {
112 BLog(BLOG_ERROR, "NCDStringIndex__Hash_MultiplyBuckets failed");
113 return -1;
114 }
115 }
116  
117 ASSERT(o->entries_size < o->entries_capacity)
118  
119 struct NCDStringIndex__entry *entry = &o->entries[o->entries_size];
120  
121 if (!(entry->str = b_strdup_bin(str, str_len))) {
122 BLog(BLOG_ERROR, "b_strdup_bin failed");
123 return -1;
124 }
125 entry->str_len = str_len;
126 entry->has_nulls = !!memchr(str, '\0', str_len);
127  
128 NCDStringIndex__HashRef newref = {entry, o->entries_size};
129 int res = NCDStringIndex__Hash_Insert(&o->hash, o->entries, newref, NULL);
130 ASSERT_EXECUTE(res)
131  
132 return o->entries_size++;
133 }
134  
135 int NCDStringIndex_Init (NCDStringIndex *o)
136 {
137 o->entries_size = 0;
138  
139 if (!Array_Init(o, NCDSTRINGINDEX_INITIAL_CAPACITY)) {
140 BLog(BLOG_ERROR, "Array_Init failed");
141 goto fail0;
142 }
143  
144 if (!NCDStringIndex__Hash_Init(&o->hash, NCDSTRINGINDEX_INITIAL_HASH_BUCKETS)) {
145 BLog(BLOG_ERROR, "NCDStringIndex__Hash_Init failed");
146 goto fail1;
147 }
148  
149 for (size_t i = 0; i < B_ARRAY_LENGTH(static_strings); i++) {
150 if (do_get(o, static_strings[i], strlen(static_strings[i])) < 0) {
151 goto fail2;
152 }
153 }
154  
155 DebugObject_Init(&o->d_obj);
156 return 1;
157  
158 fail2:
159 for (NCD_string_id_t i = 0; i < o->entries_size; i++) {
160 free(o->entries[i].str);
161 }
162 NCDStringIndex__Hash_Free(&o->hash);
163 fail1:
164 Array_Free(o);
165 fail0:
166 return 0;
167 }
168  
169 void NCDStringIndex_Free (NCDStringIndex *o)
170 {
171 DebugObject_Free(&o->d_obj);
172  
173 for (NCD_string_id_t i = 0; i < o->entries_size; i++) {
174 free(o->entries[i].str);
175 }
176  
177 NCDStringIndex__Hash_Free(&o->hash);
178 Array_Free(o);
179 }
180  
181 NCD_string_id_t NCDStringIndex_Lookup (NCDStringIndex *o, const char *str)
182 {
183 DebugObject_Access(&o->d_obj);
184 ASSERT(str)
185  
186 return NCDStringIndex_LookupBin(o, str, strlen(str));
187 }
188  
189 NCD_string_id_t NCDStringIndex_LookupBin (NCDStringIndex *o, const char *str, size_t str_len)
190 {
191 DebugObject_Access(&o->d_obj);
192 ASSERT(str)
193  
194 NCDStringIndex_hash_key key = {str, str_len};
195 NCDStringIndex__HashRef ref = NCDStringIndex__Hash_Lookup(&o->hash, o->entries, key);
196 ASSERT(ref.link == -1 || ref.link >= 0)
197 ASSERT(ref.link == -1 || ref.link < o->entries_size)
198 ASSERT(ref.link == -1 || (ref.ptr->str_len == str_len && !memcmp(ref.ptr->str, str, str_len)))
199  
200 return ref.link;
201 }
202  
203 NCD_string_id_t NCDStringIndex_Get (NCDStringIndex *o, const char *str)
204 {
205 DebugObject_Access(&o->d_obj);
206 ASSERT(str)
207  
208 return NCDStringIndex_GetBin(o, str, strlen(str));
209 }
210  
211 NCD_string_id_t NCDStringIndex_GetBin (NCDStringIndex *o, const char *str, size_t str_len)
212 {
213 DebugObject_Access(&o->d_obj);
214 ASSERT(str)
215  
216 return do_get(o, str, str_len);
217 }
218  
219 NCD_string_id_t NCDStringIndex_GetBinMr (NCDStringIndex *o, MemRef str)
220 {
221 return NCDStringIndex_GetBin(o, str.ptr, str.len);
222 }
223  
224 MemRef NCDStringIndex_Value (NCDStringIndex *o, NCD_string_id_t id)
225 {
226 DebugObject_Access(&o->d_obj);
227 ASSERT(id >= 0)
228 ASSERT(id < o->entries_size)
229 ASSERT(o->entries[id].str)
230  
231 return MemRef_Make(o->entries[id].str, o->entries[id].str_len);
232 }
233  
234 int NCDStringIndex_HasNulls (NCDStringIndex *o, NCD_string_id_t id)
235 {
236 DebugObject_Access(&o->d_obj);
237 ASSERT(id >= 0)
238 ASSERT(id < o->entries_size)
239 ASSERT(o->entries[id].str)
240  
241 return o->entries[id].has_nulls;
242 }
243  
244 int NCDStringIndex_GetRequests (NCDStringIndex *o, struct NCD_string_request *requests)
245 {
246 DebugObject_Access(&o->d_obj);
247 ASSERT(requests)
248  
249 while (requests->str) {
250 NCD_string_id_t id = NCDStringIndex_Get(o, requests->str);
251 if (id < 0) {
252 return 0;
253 }
254 requests->id = id;
255 requests++;
256 }
257  
258 return 1;
259 }