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