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 "libsaio.h"␊ |
39 | ␊ |
40 | typedef struct {␊ |
41 | char *d;␊ |
42 | size_t n; /* allocd size */␊ |
43 | size_t i; /* index of first unused byte */␊ |
44 | } UT_string;␊ |
45 | ␊ |
46 | #define utstring_reserve(s,amt) \␊ |
47 | do { \␊ |
48 | if (((s)->n - (s)->i) < (size_t)(amt)) { \␊ |
49 | (s)->d = (char*)realloc((s)->d, (s)->n + amt); \␊ |
50 | if ((s)->d == NULL) exit(-1); \␊ |
51 | (s)->n += amt; \␊ |
52 | } \␊ |
53 | } while(0)␊ |
54 | ␊ |
55 | #define utstring_init(s) \␊ |
56 | do { \␊ |
57 | (s)->n = 0; (s)->i = 0; (s)->d = NULL; \␊ |
58 | utstring_reserve(s,100); \␊ |
59 | (s)->d[0] = '\0'; \␊ |
60 | } while(0)␊ |
61 | ␊ |
62 | #define utstring_done(s) \␊ |
63 | do { \␊ |
64 | if ((s)->d != NULL) free((s)->d); \␊ |
65 | (s)->n = 0; \␊ |
66 | } while(0)␊ |
67 | ␊ |
68 | #define utstring_free(s) \␊ |
69 | do { \␊ |
70 | utstring_done(s); \␊ |
71 | free(s); \␊ |
72 | } while(0)␊ |
73 | ␊ |
74 | #define utstring_new(s) \␊ |
75 | do { \␊ |
76 | s = (UT_string*)calloc(1,sizeof(UT_string)); \␊ |
77 | if (!s) exit(-1); \␊ |
78 | utstring_init(s); \␊ |
79 | } while(0)␊ |
80 | ␊ |
81 | #define utstring_renew(s) \␊ |
82 | do { \␊ |
83 | if (s) { \␊ |
84 | utstring_clear(s); \␊ |
85 | } else { \␊ |
86 | utstring_new(s); \␊ |
87 | } \␊ |
88 | } while(0)␊ |
89 | ␊ |
90 | #define utstring_clear(s) \␊ |
91 | do { \␊ |
92 | (s)->i = 0; \␊ |
93 | (s)->d[0] = '\0'; \␊ |
94 | } while(0)␊ |
95 | ␊ |
96 | #define utstring_bincpy(s,b,l) \␊ |
97 | do { \␊ |
98 | utstring_reserve((s),(l)+1); \␊ |
99 | if (l) memcpy(&(s)->d[(s)->i], b, l); \␊ |
100 | (s)->i += l; \␊ |
101 | (s)->d[(s)->i]='\0'; \␊ |
102 | } while(0)␊ |
103 | ␊ |
104 | #define utstring_concat(dst,src) \␊ |
105 | do { \␊ |
106 | utstring_reserve((dst),((src)->i)+1); \␊ |
107 | if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \␊ |
108 | (dst)->i += (src)->i; \␊ |
109 | (dst)->d[(dst)->i]='\0'; \␊ |
110 | } while(0)␊ |
111 | ␊ |
112 | #define utstring_len(s) ((unsigned)((s)->i))␊ |
113 | ␊ |
114 | #define utstring_body(s) ((s)->d)␊ |
115 | ␊ |
116 | _UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {␊ |
117 | ␉int n;␊ |
118 | ␉va_list cp;␊ |
119 | ␉while (1) {␊ |
120 | #ifdef _WIN32␊ |
121 | ␉␉cp = ap;␊ |
122 | #else␊ |
123 | ␉␉va_copy(cp, ap);␊ |
124 | #endif␊ |
125 | ␉␉n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);␊ |
126 | ␉␉va_end(cp);␊ |
127 | ␉␉␊ |
128 | ␉␉if ((n > -1) && (n < (int)(s->n-s->i))) {␊ |
129 | ␉␉␉s->i += n;␊ |
130 | ␉␉␉return;␊ |
131 | ␉␉}␊ |
132 | ␉␉␊ |
133 | ␉␉/* Else try again with more space. */␊ |
134 | ␉␉if (n > -1) utstring_reserve(s,n+1); /* exact */␊ |
135 | ␉␉else utstring_reserve(s,(s->n)*2); /* 2x */␊ |
136 | ␉}␊ |
137 | }␊ |
138 | #ifdef __GNUC__␊ |
139 | /* support printf format checking (2=the format string, 3=start of varargs) */␊ |
140 | _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...)␊ |
141 | __attribute__ (( format( printf, 2, 3) ));␊ |
142 | #endif␊ |
143 | _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) {␊ |
144 | ␉va_list ap;␊ |
145 | ␉va_start(ap,fmt);␊ |
146 | ␉utstring_printf_va(s,fmt,ap);␊ |
147 | ␉va_end(ap);␊ |
148 | }␊ |
149 | ␊ |
150 | /*******************************************************************************␊ |
151 | * begin substring search functions *␊ |
152 | ******************************************************************************/␊ |
153 | /* Build KMP table from left to right. */␊ |
154 | _UNUSED_ static void _utstring_BuildTable(␊ |
155 | ␉␉␉␉␉␉␉␉␉␉ const char *P_Needle, ␊ |
156 | ␉␉␉␉␉␉␉␉␉␉ unsigned int P_NeedleLen, ␊ |
157 | ␉␉␉␉␉␉␉␉␉␉ long *P_KMP_Table)␊ |
158 | {␊ |
159 | long i, j;␊ |
160 | ␉␊ |
161 | i = 0;␊ |
162 | j = i - 1;␊ |
163 | P_KMP_Table[i] = j;␊ |
164 | while (i < (long)P_NeedleLen)␊ |
165 | {␊ |
166 | while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )␊ |
167 | {␊ |
168 | ␉␉␉j = P_KMP_Table[j];␊ |
169 | }␊ |
170 | i++;␊ |
171 | j++;␊ |
172 | if (i < (long)P_NeedleLen)␊ |
173 | {␊ |
174 | if (P_Needle[i] == P_Needle[j])␊ |
175 | {␊ |
176 | P_KMP_Table[i] = P_KMP_Table[j];␊ |
177 | }␊ |
178 | else␊ |
179 | {␊ |
180 | P_KMP_Table[i] = j;␊ |
181 | }␊ |
182 | }␊ |
183 | else␊ |
184 | {␊ |
185 | P_KMP_Table[i] = j;␊ |
186 | }␊ |
187 | }␊ |
188 | ␉␊ |
189 | return;␊ |
190 | }␊ |
191 | ␊ |
192 | ␊ |
193 | /* Build KMP table from right to left. */␊ |
194 | _UNUSED_ static void _utstring_BuildTableR(␊ |
195 | ␉␉␉␉␉␉␉␉␉␉ const char *P_Needle, ␊ |
196 | ␉␉␉␉␉␉␉␉␉␉ unsigned int P_NeedleLen, ␊ |
197 | ␉␉␉␉␉␉␉␉␉␉ long *P_KMP_Table)␊ |
198 | {␊ |
199 | long i, j;␊ |
200 | ␉␊ |
201 | i = P_NeedleLen - 1;␊ |
202 | j = i + 1;␊ |
203 | P_KMP_Table[i + 1] = j;␊ |
204 | while (i >= 0)␊ |
205 | {␊ |
206 | while ( (j < (long)P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )␊ |
207 | {␊ |
208 | ␉␉␉j = P_KMP_Table[j + 1];␊ |
209 | }␊ |
210 | i--;␊ |
211 | j--;␊ |
212 | if (i >= 0)␊ |
213 | {␊ |
214 | if (P_Needle[i] == P_Needle[j])␊ |
215 | {␊ |
216 | P_KMP_Table[i + 1] = P_KMP_Table[j + 1];␊ |
217 | }␊ |
218 | else␊ |
219 | {␊ |
220 | P_KMP_Table[i + 1] = j;␊ |
221 | }␊ |
222 | }␊ |
223 | else␊ |
224 | {␊ |
225 | P_KMP_Table[i + 1] = j;␊ |
226 | }␊ |
227 | }␊ |
228 | ␉␊ |
229 | return;␊ |
230 | }␊ |
231 | ␊ |
232 | ␊ |
233 | /* Search data from left to right. ( Multiple search mode. ) */␊ |
234 | _UNUSED_ static long _utstring_find(␊ |
235 | ␉␉␉␉␉␉␉␉␉const char *P_Haystack, ␊ |
236 | ␉␉␉␉␉␉␉␉␉size_t P_HaystackLen, ␊ |
237 | ␉␉␉␉␉␉␉␉␉const char *P_Needle, ␊ |
238 | ␉␉␉␉␉␉␉␉␉size_t P_NeedleLen, ␊ |
239 | ␉␉␉␉␉␉␉␉␉long *P_KMP_Table)␊ |
240 | {␊ |
241 | int i, j;␊ |
242 | long V_FindPosition = -1;␊ |
243 | ␉␊ |
244 | /* Search from left to right. */␊ |
245 | i = j = 0;␊ |
246 | while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )␊ |
247 | {␊ |
248 | while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )␊ |
249 | {␊ |
250 | i = P_KMP_Table[i];␊ |
251 | }␊ |
252 | i++;␊ |
253 | j++;␊ |
254 | if (i >= (int)P_NeedleLen)␊ |
255 | {␊ |
256 | /* Found. */␊ |
257 | V_FindPosition = j - i;␊ |
258 | break;␊ |
259 | }␊ |
260 | }␊ |
261 | ␉␊ |
262 | return V_FindPosition;␊ |
263 | }␊ |
264 | ␊ |
265 | ␊ |
266 | /* Search data from right to left. ( Multiple search mode. ) */␊ |
267 | _UNUSED_ static long _utstring_findR(␊ |
268 | ␉␉␉␉␉␉␉␉␉ const char *P_Haystack, ␊ |
269 | ␉␉␉␉␉␉␉␉␉ size_t P_HaystackLen, ␊ |
270 | ␉␉␉␉␉␉␉␉␉ const char *P_Needle, ␊ |
271 | ␉␉␉␉␉␉␉␉␉ size_t P_NeedleLen, ␊ |
272 | ␉␉␉␉␉␉␉␉␉ long *P_KMP_Table)␊ |
273 | {␊ |
274 | int i, j;␊ |
275 | long V_FindPosition = -1;␊ |
276 | ␉␊ |
277 | /* Search from right to left. */␊ |
278 | j = (P_HaystackLen - 1);␊ |
279 | i = (P_NeedleLen - 1);␊ |
280 | while ( (j >= 0) && (j >= i) )␊ |
281 | {␊ |
282 | while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )␊ |
283 | {␊ |
284 | i = P_KMP_Table[i + 1];␊ |
285 | }␊ |
286 | i--;␊ |
287 | j--;␊ |
288 | if (i < 0)␊ |
289 | {␊ |
290 | /* Found. */␊ |
291 | V_FindPosition = j + 1;␊ |
292 | break;␊ |
293 | }␊ |
294 | }␊ |
295 | ␉␊ |
296 | return V_FindPosition;␊ |
297 | }␊ |
298 | ␊ |
299 | ␊ |
300 | /* Search data from left to right. ( One time search mode. ) */␊ |
301 | _UNUSED_ static long utstring_find(␊ |
302 | ␉␉␉␉␉␉␉␉ UT_string *s, ␊ |
303 | ␉␉␉␉␉␉␉␉ long P_StartPosition, /* Start from 0. -1 means last position. */␊ |
304 | ␉␉␉␉␉␉␉␉ const char *P_Needle, ␊ |
305 | ␉␉␉␉␉␉␉␉ size_t P_NeedleLen)␊ |
306 | {␊ |
307 | long V_StartPosition;␊ |
308 | long V_HaystackLen;␊ |
309 | long *V_KMP_Table;␊ |
310 | long V_FindPosition = -1;␊ |
311 | ␉␊ |
312 | if (P_StartPosition < 0)␊ |
313 | {␊ |
314 | V_StartPosition = s->i + P_StartPosition;␊ |
315 | }␊ |
316 | else␊ |
317 | {␊ |
318 | V_StartPosition = P_StartPosition;␊ |
319 | }␊ |
320 | V_HaystackLen = s->i - V_StartPosition;␊ |
321 | if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )␊ |
322 | {␊ |
323 | V_KMP_Table = (long *)calloc((P_NeedleLen + 1), sizeof(long));␊ |
324 | if (V_KMP_Table != NULL)␊ |
325 | {␊ |
326 | _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);␊ |
327 | ␉␉␉␊ |
328 | V_FindPosition = _utstring_find(s->d + V_StartPosition, ␊ |
329 | V_HaystackLen, ␊ |
330 | P_Needle, ␊ |
331 | P_NeedleLen, ␊ |
332 | V_KMP_Table);␊ |
333 | if (V_FindPosition >= 0)␊ |
334 | {␊ |
335 | V_FindPosition += V_StartPosition;␊ |
336 | }␊ |
337 | ␉␉␉␊ |
338 | free(V_KMP_Table);␊ |
339 | }␊ |
340 | }␊ |
341 | ␉␊ |
342 | return V_FindPosition;␊ |
343 | }␊ |
344 | ␊ |
345 | ␊ |
346 | /* Search data from right to left. ( One time search mode. ) */␊ |
347 | _UNUSED_ static long utstring_findR(␊ |
348 | ␉␉␉␉␉␉␉␉␉UT_string *s, ␊ |
349 | ␉␉␉␉␉␉␉␉␉long P_StartPosition, /* Start from 0. -1 means last position. */␊ |
350 | ␉␉␉␉␉␉␉␉␉const char *P_Needle, ␊ |
351 | ␉␉␉␉␉␉␉␉␉size_t P_NeedleLen)␊ |
352 | {␊ |
353 | long V_StartPosition;␊ |
354 | long V_HaystackLen;␊ |
355 | long *V_KMP_Table;␊ |
356 | long V_FindPosition = -1;␊ |
357 | ␉␊ |
358 | if (P_StartPosition < 0)␊ |
359 | {␊ |
360 | V_StartPosition = s->i + P_StartPosition;␊ |
361 | }␊ |
362 | else␊ |
363 | {␊ |
364 | V_StartPosition = P_StartPosition;␊ |
365 | }␊ |
366 | V_HaystackLen = V_StartPosition + 1;␊ |
367 | if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )␊ |
368 | {␊ |
369 | V_KMP_Table = (long *)calloc((P_NeedleLen + 1), sizeof(long));␊ |
370 | if (V_KMP_Table != NULL)␊ |
371 | {␊ |
372 | _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);␊ |
373 | ␉␉␉␊ |
374 | V_FindPosition = _utstring_findR(s->d, ␊ |
375 | V_HaystackLen, ␊ |
376 | P_Needle, ␊ |
377 | P_NeedleLen, ␊ |
378 | V_KMP_Table);␊ |
379 | ␉␉␉␊ |
380 | free(V_KMP_Table);␊ |
381 | }␊ |
382 | }␊ |
383 | ␉␊ |
384 | return V_FindPosition;␊ |
385 | }␊ |
386 | /*******************************************************************************␊ |
387 | * end substring search functions *␊ |
388 | ******************************************************************************/␊ |
389 | ␊ |
390 | #endif /* UTSTRING_H */␊ |
391 | |