1/*
2Copyright (c) 2008-2013, Troy D. Hanson   http://troydhanson.github.com/uthash/
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, 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
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21SOFTWARE, 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
45typedef 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)                            \
53do {                                                       \
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)                                   \
63do {                                                       \
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)                                   \
70do {                                                       \
71  if ((s)->d != NULL) free((s)->d);                        \
72  (s)->n = 0;                                              \
73} while(0)
74
75#define utstring_free(s)                                   \
76do {                                                       \
77  utstring_done(s);                                        \
78  free(s);                                                 \
79} while(0)
80
81#define utstring_new(s)                                    \
82do {                                                       \
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)                                  \
89do {                                                       \
90   if (s) {                                                \
91     utstring_clear(s);                                    \
92   } else {                                                \
93     utstring_new(s);                                      \
94   }                                                       \
95} while(0)
96
97#define utstring_clear(s)                                  \
98do {                                                       \
99  (s)->i = 0;                                              \
100  (s)->d[0] = '\0';                                        \
101} while(0)
102
103#define utstring_bincpy(s,b,l)                             \
104do {                                                       \
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)                                 \
112do {                                                             \
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_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) */
147static void utstring_printf(UT_string *s, const char *fmt, ...)
148  __attribute__ (( format( printf, 2, 3) ));
149#endif
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)                                    \
158do {                                                                           \
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)                                             \
166do {                                                                           \
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. */
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. */
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. ) */
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. ) */
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. ) */
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. ) */
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