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