contrib/libucl/uthash/utstring.h

   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
 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
 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. */
 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. */
 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. ) */
 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. ) */
 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. ) */
 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. ) */
 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 */