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 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 (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 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
123 #ifdef __GNUC__
124 __attribute__((format(printf, 2, 0)))
125 #endif
utstring_printf_va(UT_string * s,const char * fmt,va_list ap)126 _UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
127 int n;
128 va_list cp;
129 while (1) {
130 #ifdef _WIN32
131 cp = ap;
132 #else
133 va_copy(cp, ap);
134 #endif
135 n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
136 va_end(cp);
137
138 if ((n > -1) && (n < (int)(s->n-s->i))) {
139 s->i += n;
140 return;
141 }
142
143 /* Else try again with more space. */
144 if (n > -1) utstring_reserve(s,n+1); /* exact */
145 else utstring_reserve(s,(s->n)*2); /* 2x */
146 }
147 }
148 #ifdef __GNUC__
149 /* support printf format checking (2=the format string, 3=start of varargs) */
150 static void utstring_printf(UT_string *s, const char *fmt, ...)
151 __attribute__ (( format( printf, 2, 3) ));
152 #endif
utstring_printf(UT_string * s,const char * fmt,...)153 _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) {
154 va_list ap;
155 va_start(ap,fmt);
156 utstring_printf_va(s,fmt,ap);
157 va_end(ap);
158 }
159
160 #define utstring_append_len(dst, src, len) \
161 do { \
162 while ((dst)->n-(dst)->i <= (len)) utstring_reserve((dst),((dst)->n)*2); \
163 memcpy(&(dst)->d[(dst)->i], (src), (len)); \
164 (dst)->i+=(len); \
165 (dst)->d[(dst)->i]='\0'; \
166 } while(0)
167
168 #define utstring_append_c(dst, c) \
169 do { \
170 if ((dst)->n-(dst)->i < 2) utstring_reserve((dst),((dst)->n)*2); \
171 (dst)->d[(dst)->i++] = (c); \
172 (dst)->d[(dst)->i]='\0'; \
173 } while(0)
174
175 /*******************************************************************************
176 * begin substring search functions *
177 ******************************************************************************/
178 /* Build KMP table from left to right. */
_utstring_BuildTable(const char * P_Needle,ssize_t P_NeedleLen,long * P_KMP_Table)179 _UNUSED_ static void _utstring_BuildTable(
180 const char *P_Needle,
181 ssize_t P_NeedleLen,
182 long *P_KMP_Table)
183 {
184 long i, j;
185
186 i = 0;
187 j = i - 1;
188 P_KMP_Table[i] = j;
189 while (i < P_NeedleLen)
190 {
191 while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )
192 {
193 j = P_KMP_Table[j];
194 }
195 i++;
196 j++;
197 if (i < P_NeedleLen)
198 {
199 if (P_Needle[i] == P_Needle[j])
200 {
201 P_KMP_Table[i] = P_KMP_Table[j];
202 }
203 else
204 {
205 P_KMP_Table[i] = j;
206 }
207 }
208 else
209 {
210 P_KMP_Table[i] = j;
211 }
212 }
213
214 return;
215 }
216
217
218 /* Build KMP table from right to left. */
_utstring_BuildTableR(const char * P_Needle,ssize_t P_NeedleLen,long * P_KMP_Table)219 _UNUSED_ static void _utstring_BuildTableR(
220 const char *P_Needle,
221 ssize_t P_NeedleLen,
222 long *P_KMP_Table)
223 {
224 long i, j;
225
226 i = P_NeedleLen - 1;
227 j = i + 1;
228 P_KMP_Table[i + 1] = j;
229 while (i >= 0)
230 {
231 while ( (j < P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )
232 {
233 j = P_KMP_Table[j + 1];
234 }
235 i--;
236 j--;
237 if (i >= 0)
238 {
239 if (P_Needle[i] == P_Needle[j])
240 {
241 P_KMP_Table[i + 1] = P_KMP_Table[j + 1];
242 }
243 else
244 {
245 P_KMP_Table[i + 1] = j;
246 }
247 }
248 else
249 {
250 P_KMP_Table[i + 1] = j;
251 }
252 }
253
254 return;
255 }
256
257
258 /* 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)259 _UNUSED_ static long _utstring_find(
260 const char *P_Haystack,
261 size_t P_HaystackLen,
262 const char *P_Needle,
263 size_t P_NeedleLen,
264 long *P_KMP_Table)
265 {
266 long i, j;
267 long V_FindPosition = -1;
268
269 /* Search from left to right. */
270 i = j = 0;
271 while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )
272 {
273 while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )
274 {
275 i = P_KMP_Table[i];
276 }
277 i++;
278 j++;
279 if (i >= (int)P_NeedleLen)
280 {
281 /* Found. */
282 V_FindPosition = j - i;
283 break;
284 }
285 }
286
287 return V_FindPosition;
288 }
289
290
291 /* 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)292 _UNUSED_ static long _utstring_findR(
293 const char *P_Haystack,
294 size_t P_HaystackLen,
295 const char *P_Needle,
296 size_t P_NeedleLen,
297 long *P_KMP_Table)
298 {
299 long i, j;
300 long V_FindPosition = -1;
301
302 /* Search from right to left. */
303 j = (P_HaystackLen - 1);
304 i = (P_NeedleLen - 1);
305 while ( (j >= 0) && (j >= i) )
306 {
307 while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )
308 {
309 i = P_KMP_Table[i + 1];
310 }
311 i--;
312 j--;
313 if (i < 0)
314 {
315 /* Found. */
316 V_FindPosition = j + 1;
317 break;
318 }
319 }
320
321 return V_FindPosition;
322 }
323
324
325 /* 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)326 _UNUSED_ static long utstring_find(
327 UT_string *s,
328 long P_StartPosition, /* Start from 0. -1 means last position. */
329 const char *P_Needle,
330 ssize_t P_NeedleLen)
331 {
332 long V_StartPosition;
333 long V_HaystackLen;
334 long *V_KMP_Table;
335 long V_FindPosition = -1;
336
337 if (P_StartPosition < 0)
338 {
339 V_StartPosition = s->i + P_StartPosition;
340 }
341 else
342 {
343 V_StartPosition = P_StartPosition;
344 }
345 V_HaystackLen = s->i - V_StartPosition;
346 if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )
347 {
348 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
349 if (V_KMP_Table != NULL)
350 {
351 _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);
352
353 V_FindPosition = _utstring_find(s->d + V_StartPosition,
354 V_HaystackLen,
355 P_Needle,
356 P_NeedleLen,
357 V_KMP_Table);
358 if (V_FindPosition >= 0)
359 {
360 V_FindPosition += V_StartPosition;
361 }
362
363 free(V_KMP_Table);
364 }
365 }
366
367 return V_FindPosition;
368 }
369
370
371 /* 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)372 _UNUSED_ static long utstring_findR(
373 UT_string *s,
374 long P_StartPosition, /* Start from 0. -1 means last position. */
375 const char *P_Needle,
376 ssize_t P_NeedleLen)
377 {
378 long V_StartPosition;
379 long V_HaystackLen;
380 long *V_KMP_Table;
381 long V_FindPosition = -1;
382
383 if (P_StartPosition < 0)
384 {
385 V_StartPosition = s->i + P_StartPosition;
386 }
387 else
388 {
389 V_StartPosition = P_StartPosition;
390 }
391 V_HaystackLen = V_StartPosition + 1;
392 if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )
393 {
394 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
395 if (V_KMP_Table != NULL)
396 {
397 _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);
398
399 V_FindPosition = _utstring_findR(s->d,
400 V_HaystackLen,
401 P_Needle,
402 P_NeedleLen,
403 V_KMP_Table);
404
405 free(V_KMP_Table);
406 }
407 }
408
409 return V_FindPosition;
410 }
411 /*******************************************************************************
412 * end substring search functions *
413 ******************************************************************************/
414
415 #endif /* UTSTRING_H */
416