suitcase

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README

utstring.h (12229B)


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