1 | /*␊ |
2 | Copyright (c) 2008-2013, Troy D. Hanson http://uthash.sourceforge.net␊ |
3 | All rights reserved.␊ |
4 | ␊ |
5 | Redistribution and use in source and binary forms, with or without␊ |
6 | modification, are permitted provided that the following conditions are met:␊ |
7 | ␊ |
8 | * Redistributions of source code must retain the above copyright␊ |
9 | notice, this list of conditions and the following disclaimer.␊ |
10 | ␊ |
11 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS␊ |
12 | IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED␊ |
13 | TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A␊ |
14 | PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER␊ |
15 | OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,␊ |
16 | EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,␊ |
17 | PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR␊ |
18 | PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF␊ |
19 | LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING␊ |
20 | NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS␊ |
21 | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.␊ |
22 | */␊ |
23 | ␊ |
24 | /* a dynamic string implementation using macros ␊ |
25 | * see http://uthash.sourceforge.net/utstring␊ |
26 | */␊ |
27 | #ifndef UTSTRING_H␊ |
28 | #define UTSTRING_H␊ |
29 | ␊ |
30 | #define UTSTRING_VERSION 1.9.7␊ |
31 | ␊ |
32 | #ifdef __GNUC__␊ |
33 | #define _UNUSED_ __attribute__ ((__unused__)) ␊ |
34 | #else␊ |
35 | #define _UNUSED_ ␊ |
36 | #endif␊ |
37 | ␊ |
38 | #include <stdlib.h>␊ |
39 | #include <string.h>␊ |
40 | #include <stdarg.h>␊ |
41 | #define oom() exit(-1)␊ |
42 | ␊ |
43 | typedef struct {␊ |
44 | char *d;␊ |
45 | size_t n; /* allocd size */␊ |
46 | size_t i; /* index of first unused byte */␊ |
47 | } UT_string;␊ |
48 | ␊ |
49 | #define utstring_reserve(s,amt) \␊ |
50 | do { \␊ |
51 | if (((s)->n - (s)->i) < (size_t)(amt)) { \␊ |
52 | (s)->d = (char*)realloc((s)->d, (s)->n + amt); \␊ |
53 | if ((s)->d == NULL) oom(); \␊ |
54 | (s)->n += amt; \␊ |
55 | } \␊ |
56 | } while(0)␊ |
57 | ␊ |
58 | #define utstring_init(s) \␊ |
59 | do { \␊ |
60 | (s)->n = 0; (s)->i = 0; (s)->d = NULL; \␊ |
61 | utstring_reserve(s,100); \␊ |
62 | (s)->d[0] = '\0'; \␊ |
63 | } while(0)␊ |
64 | ␊ |
65 | #define utstring_done(s) \␊ |
66 | do { \␊ |
67 | if ((s)->d != NULL) free((s)->d); \␊ |
68 | (s)->n = 0; \␊ |
69 | } while(0)␊ |
70 | ␊ |
71 | #define utstring_free(s) \␊ |
72 | do { \␊ |
73 | utstring_done(s); \␊ |
74 | free(s); \␊ |
75 | } while(0)␊ |
76 | ␊ |
77 | #define utstring_new(s) \␊ |
78 | do { \␊ |
79 | s = (UT_string*)calloc(sizeof(UT_string),1); \␊ |
80 | if (!s) oom(); \␊ |
81 | utstring_init(s); \␊ |
82 | } while(0)␊ |
83 | ␊ |
84 | #define utstring_renew(s) \␊ |
85 | do { \␊ |
86 | if (s) { \␊ |
87 | utstring_clear(s); \␊ |
88 | } else { \␊ |
89 | utstring_new(s); \␊ |
90 | } \␊ |
91 | } while(0)␊ |
92 | ␊ |
93 | #define utstring_clear(s) \␊ |
94 | do { \␊ |
95 | (s)->i = 0; \␊ |
96 | (s)->d[0] = '\0'; \␊ |
97 | } while(0)␊ |
98 | ␊ |
99 | #define utstring_bincpy(s,b,l) \␊ |
100 | do { \␊ |
101 | utstring_reserve((s),(l)+1); \␊ |
102 | if (l) memcpy(&(s)->d[(s)->i], b, l); \␊ |
103 | (s)->i += l; \␊ |
104 | (s)->d[(s)->i]='\0'; \␊ |
105 | } while(0)␊ |
106 | ␊ |
107 | #define utstring_concat(dst,src) \␊ |
108 | do { \␊ |
109 | utstring_reserve((dst),((src)->i)+1); \␊ |
110 | if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \␊ |
111 | (dst)->i += (src)->i; \␊ |
112 | (dst)->d[(dst)->i]='\0'; \␊ |
113 | } while(0)␊ |
114 | ␊ |
115 | #define utstring_len(s) ((unsigned)((s)->i))␊ |
116 | ␊ |
117 | #define utstring_body(s) ((s)->d)␊ |
118 | ␊ |
119 | _UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {␊ |
120 | int n;␊ |
121 | va_list cp;␊ |
122 | while (1) {␊ |
123 | #ifdef _WIN32␊ |
124 | cp = ap;␊ |
125 | #else␊ |
126 | va_copy(cp, ap);␊ |
127 | #endif␊ |
128 | n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);␊ |
129 | va_end(cp);␊ |
130 | ␊ |
131 | if ((n > -1) && (n < (int)(s->n-s->i))) {␊ |
132 | s->i += n;␊ |
133 | return;␊ |
134 | }␊ |
135 | ␊ |
136 | /* Else try again with more space. */␊ |
137 | if (n > -1) utstring_reserve(s,n+1); /* exact */␊ |
138 | else utstring_reserve(s,(s->n)*2); /* 2x */␊ |
139 | }␊ |
140 | }␊ |
141 | #ifdef __GNUC__␊ |
142 | /* support printf format checking (2=the format string, 3=start of varargs) */␊ |
143 | static void utstring_printf(UT_string *s, const char *fmt, ...)␊ |
144 | __attribute__ (( format( printf, 2, 3) ));␊ |
145 | #endif␊ |
146 | _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) {␊ |
147 | va_list ap;␊ |
148 | va_start(ap,fmt);␊ |
149 | utstring_printf_va(s,fmt,ap);␊ |
150 | va_end(ap);␊ |
151 | }␊ |
152 | ␊ |
153 | /*******************************************************************************␊ |
154 | * begin substring search functions *␊ |
155 | ******************************************************************************/␊ |
156 | /* Build KMP table from left to right. */␊ |
157 | _UNUSED_ static void _utstring_BuildTable(␊ |
158 | const char *P_Needle, ␊ |
159 | unsigned int P_NeedleLen, ␊ |
160 | long *P_KMP_Table)␊ |
161 | {␊ |
162 | long i, j;␊ |
163 | ␊ |
164 | i = 0;␊ |
165 | j = i - 1;␊ |
166 | P_KMP_Table[i] = j;␊ |
167 | while (i < (long)P_NeedleLen)␊ |
168 | {␊ |
169 | while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )␊ |
170 | {␊ |
171 | j = P_KMP_Table[j];␊ |
172 | }␊ |
173 | i++;␊ |
174 | j++;␊ |
175 | if (i < (long)P_NeedleLen)␊ |
176 | {␊ |
177 | if (P_Needle[i] == P_Needle[j])␊ |
178 | {␊ |
179 | P_KMP_Table[i] = P_KMP_Table[j];␊ |
180 | }␊ |
181 | else␊ |
182 | {␊ |
183 | P_KMP_Table[i] = j;␊ |
184 | }␊ |
185 | }␊ |
186 | else␊ |
187 | {␊ |
188 | P_KMP_Table[i] = j;␊ |
189 | }␊ |
190 | }␊ |
191 | ␊ |
192 | return;␊ |
193 | }␊ |
194 | ␊ |
195 | ␊ |
196 | /* Build KMP table from right to left. */␊ |
197 | _UNUSED_ static void _utstring_BuildTableR(␊ |
198 | const char *P_Needle, ␊ |
199 | unsigned int P_NeedleLen, ␊ |
200 | long *P_KMP_Table)␊ |
201 | {␊ |
202 | long i, j;␊ |
203 | ␊ |
204 | i = P_NeedleLen - 1;␊ |
205 | j = i + 1;␊ |
206 | P_KMP_Table[i + 1] = j;␊ |
207 | while (i >= 0)␊ |
208 | {␊ |
209 | while ( (j < (long)P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )␊ |
210 | {␊ |
211 | j = P_KMP_Table[j + 1];␊ |
212 | }␊ |
213 | i--;␊ |
214 | j--;␊ |
215 | if (i >= 0)␊ |
216 | {␊ |
217 | if (P_Needle[i] == P_Needle[j])␊ |
218 | {␊ |
219 | P_KMP_Table[i + 1] = P_KMP_Table[j + 1];␊ |
220 | }␊ |
221 | else␊ |
222 | {␊ |
223 | P_KMP_Table[i + 1] = j;␊ |
224 | }␊ |
225 | }␊ |
226 | else␊ |
227 | {␊ |
228 | P_KMP_Table[i + 1] = j;␊ |
229 | }␊ |
230 | }␊ |
231 | ␊ |
232 | return;␊ |
233 | }␊ |
234 | ␊ |
235 | ␊ |
236 | /* Search data from left to right. ( Multiple search mode. ) */␊ |
237 | _UNUSED_ static long _utstring_find(␊ |
238 | const char *P_Haystack, ␊ |
239 | size_t P_HaystackLen, ␊ |
240 | const char *P_Needle, ␊ |
241 | size_t P_NeedleLen, ␊ |
242 | long *P_KMP_Table)␊ |
243 | {␊ |
244 | int i, j;␊ |
245 | long V_FindPosition = -1;␊ |
246 | ␊ |
247 | /* Search from left to right. */␊ |
248 | i = j = 0;␊ |
249 | while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )␊ |
250 | {␊ |
251 | while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )␊ |
252 | {␊ |
253 | i = P_KMP_Table[i];␊ |
254 | }␊ |
255 | i++;␊ |
256 | j++;␊ |
257 | if (i >= (int)P_NeedleLen)␊ |
258 | {␊ |
259 | /* Found. */␊ |
260 | V_FindPosition = j - i;␊ |
261 | break;␊ |
262 | }␊ |
263 | }␊ |
264 | ␊ |
265 | return V_FindPosition;␊ |
266 | }␊ |
267 | ␊ |
268 | ␊ |
269 | /* Search data from right to left. ( Multiple search mode. ) */␊ |
270 | _UNUSED_ static long _utstring_findR(␊ |
271 | const char *P_Haystack, ␊ |
272 | size_t P_HaystackLen, ␊ |
273 | const char *P_Needle, ␊ |
274 | size_t P_NeedleLen, ␊ |
275 | long *P_KMP_Table)␊ |
276 | {␊ |
277 | int i, j;␊ |
278 | long V_FindPosition = -1;␊ |
279 | ␊ |
280 | /* Search from right to left. */␊ |
281 | j = (P_HaystackLen - 1);␊ |
282 | i = (P_NeedleLen - 1);␊ |
283 | while ( (j >= 0) && (j >= i) )␊ |
284 | {␊ |
285 | while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )␊ |
286 | {␊ |
287 | i = P_KMP_Table[i + 1];␊ |
288 | }␊ |
289 | i--;␊ |
290 | j--;␊ |
291 | if (i < 0)␊ |
292 | {␊ |
293 | /* Found. */␊ |
294 | V_FindPosition = j + 1;␊ |
295 | break;␊ |
296 | }␊ |
297 | }␊ |
298 | ␊ |
299 | return V_FindPosition;␊ |
300 | }␊ |
301 | ␊ |
302 | ␊ |
303 | /* Search data from left to right. ( One time search mode. ) */␊ |
304 | _UNUSED_ static long utstring_find(␊ |
305 | UT_string *s, ␊ |
306 | long P_StartPosition, /* Start from 0. -1 means last position. */␊ |
307 | const char *P_Needle, ␊ |
308 | size_t P_NeedleLen)␊ |
309 | {␊ |
310 | long V_StartPosition;␊ |
311 | long V_HaystackLen;␊ |
312 | long *V_KMP_Table;␊ |
313 | long V_FindPosition = -1;␊ |
314 | ␊ |
315 | if (P_StartPosition < 0)␊ |
316 | {␊ |
317 | V_StartPosition = s->i + P_StartPosition;␊ |
318 | }␊ |
319 | else␊ |
320 | {␊ |
321 | V_StartPosition = P_StartPosition;␊ |
322 | }␊ |
323 | V_HaystackLen = s->i - V_StartPosition;␊ |
324 | if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )␊ |
325 | {␊ |
326 | V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));␊ |
327 | if (V_KMP_Table != NULL)␊ |
328 | {␊ |
329 | _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);␊ |
330 | ␊ |
331 | V_FindPosition = _utstring_find(s->d + V_StartPosition, ␊ |
332 | V_HaystackLen, ␊ |
333 | P_Needle, ␊ |
334 | P_NeedleLen, ␊ |
335 | V_KMP_Table);␊ |
336 | if (V_FindPosition >= 0)␊ |
337 | {␊ |
338 | V_FindPosition += V_StartPosition;␊ |
339 | }␊ |
340 | ␊ |
341 | free(V_KMP_Table);␊ |
342 | }␊ |
343 | }␊ |
344 | ␊ |
345 | return V_FindPosition;␊ |
346 | }␊ |
347 | ␊ |
348 | ␊ |
349 | /* Search data from right to left. ( One time search mode. ) */␊ |
350 | _UNUSED_ static long utstring_findR(␊ |
351 | UT_string *s, ␊ |
352 | long P_StartPosition, /* Start from 0. -1 means last position. */␊ |
353 | const char *P_Needle, ␊ |
354 | size_t P_NeedleLen)␊ |
355 | {␊ |
356 | long V_StartPosition;␊ |
357 | long V_HaystackLen;␊ |
358 | long *V_KMP_Table;␊ |
359 | long V_FindPosition = -1;␊ |
360 | ␊ |
361 | if (P_StartPosition < 0)␊ |
362 | {␊ |
363 | V_StartPosition = s->i + P_StartPosition;␊ |
364 | }␊ |
365 | else␊ |
366 | {␊ |
367 | V_StartPosition = P_StartPosition;␊ |
368 | }␊ |
369 | V_HaystackLen = V_StartPosition + 1;␊ |
370 | if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )␊ |
371 | {␊ |
372 | V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));␊ |
373 | if (V_KMP_Table != NULL)␊ |
374 | {␊ |
375 | _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);␊ |
376 | ␊ |
377 | V_FindPosition = _utstring_findR(s->d, ␊ |
378 | V_HaystackLen, ␊ |
379 | P_Needle, ␊ |
380 | P_NeedleLen, ␊ |
381 | V_KMP_Table);␊ |
382 | ␊ |
383 | free(V_KMP_Table);␊ |
384 | }␊ |
385 | }␊ |
386 | ␊ |
387 | return V_FindPosition;␊ |
388 | }␊ |
389 | /*******************************************************************************␊ |
390 | * end substring search functions *␊ |
391 | ******************************************************************************/␊ |
392 | ␊ |
393 | #endif /* UTSTRING_H */␊ |
394 | |