2 Copyright (c) 2008-2013, Troy D. Hanson http://troydhanson.github.com/uthash/
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
8 * Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
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.
24 /* a dynamic string implementation using macros
29 #define UTSTRING_VERSION 1.9.8
32 #define _UNUSED_ __attribute__ ((__unused__))
48 size_t n; /* allocd size */
49 size_t i; /* index of first unused byte */
52 #define utstring_reserve(s,amt) \
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;} \
62 #define utstring_init(s) \
64 (s)->n = 0; (s)->i = 0; (s)->d = NULL; \
65 utstring_reserve(s,128); \
69 #define utstring_done(s) \
71 if ((s)->d != NULL) free((s)->d); \
75 #define utstring_free(s) \
81 #define utstring_new(s) \
83 s = (UT_string*)calloc(1, sizeof(UT_string)); \
85 else utstring_init(s); \
88 #define utstring_renew(s) \
97 #define utstring_clear(s) \
103 #define utstring_bincpy(s,b,l) \
105 utstring_reserve((s),(l)+1); \
106 if (l) memcpy(&(s)->d[(s)->i], b, l); \
108 (s)->d[(s)->i]='\0'; \
111 #define utstring_concat(dst,src) \
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'; \
119 #define utstring_len(s) ((unsigned)((s)->i))
121 #define utstring_body(s) ((s)->d)
123 _UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
132 n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
135 if ((n > -1) && (n < (int)(s->n-s->i))) {
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 */
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) ));
150 _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) {
153 utstring_printf_va(s,fmt,ap);
157 #define utstring_append_len(dst, src, len) \
159 while ((dst)->n-(dst)->i <= (len)) utstring_reserve((dst),((dst)->n)*2); \
160 memcpy(&(dst)->d[(dst)->i], (src), (len)); \
162 (dst)->d[(dst)->i]='\0'; \
165 #define utstring_append_c(dst, c) \
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'; \
172 /*******************************************************************************
173 * begin substring search functions *
174 ******************************************************************************/
175 /* Build KMP table from left to right. */
176 _UNUSED_ static void _utstring_BuildTable(
177 const char *P_Needle,
186 while (i < P_NeedleLen)
188 while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )
196 if (P_Needle[i] == P_Needle[j])
198 P_KMP_Table[i] = P_KMP_Table[j];
215 /* Build KMP table from right to left. */
216 _UNUSED_ static void _utstring_BuildTableR(
217 const char *P_Needle,
225 P_KMP_Table[i + 1] = j;
228 while ( (j < P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )
230 j = P_KMP_Table[j + 1];
236 if (P_Needle[i] == P_Needle[j])
238 P_KMP_Table[i + 1] = P_KMP_Table[j + 1];
242 P_KMP_Table[i + 1] = j;
247 P_KMP_Table[i + 1] = j;
255 /* Search data from left to right. ( Multiple search mode. ) */
256 _UNUSED_ static long _utstring_find(
257 const char *P_Haystack,
258 size_t P_HaystackLen,
259 const char *P_Needle,
264 long V_FindPosition = -1;
266 /* Search from left to right. */
268 while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )
270 while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )
276 if (i >= (int)P_NeedleLen)
279 V_FindPosition = j - i;
284 return V_FindPosition;
288 /* Search data from right to left. ( Multiple search mode. ) */
289 _UNUSED_ static long _utstring_findR(
290 const char *P_Haystack,
291 size_t P_HaystackLen,
292 const char *P_Needle,
297 long V_FindPosition = -1;
299 /* Search from right to left. */
300 j = (P_HaystackLen - 1);
301 i = (P_NeedleLen - 1);
302 while ( (j >= 0) && (j >= i) )
304 while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )
306 i = P_KMP_Table[i + 1];
313 V_FindPosition = j + 1;
318 return V_FindPosition;
322 /* Search data from left to right. ( One time search mode. ) */
323 _UNUSED_ static long utstring_find(
325 long P_StartPosition, /* Start from 0. -1 means last position. */
326 const char *P_Needle,
329 long V_StartPosition;
332 long V_FindPosition = -1;
334 if (P_StartPosition < 0)
336 V_StartPosition = s->i + P_StartPosition;
340 V_StartPosition = P_StartPosition;
342 V_HaystackLen = s->i - V_StartPosition;
343 if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )
345 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
346 if (V_KMP_Table != NULL)
348 _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);
350 V_FindPosition = _utstring_find(s->d + V_StartPosition,
355 if (V_FindPosition >= 0)
357 V_FindPosition += V_StartPosition;
364 return V_FindPosition;
368 /* Search data from right to left. ( One time search mode. ) */
369 _UNUSED_ static long utstring_findR(
371 long P_StartPosition, /* Start from 0. -1 means last position. */
372 const char *P_Needle,
375 long V_StartPosition;
378 long V_FindPosition = -1;
380 if (P_StartPosition < 0)
382 V_StartPosition = s->i + P_StartPosition;
386 V_StartPosition = P_StartPosition;
388 V_HaystackLen = V_StartPosition + 1;
389 if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) )
391 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
392 if (V_KMP_Table != NULL)
394 _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);
396 V_FindPosition = _utstring_findR(s->d,
406 return V_FindPosition;
408 /*******************************************************************************
409 * end substring search functions *
410 ******************************************************************************/
412 #endif /* UTSTRING_H */