ucx: ucx/string.c@b7d1317b138e

     1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

     3  *

     4  * Copyright 2017 Olaf Wintermann. All rights reserved.

     5  *

     6  * Redistribution and use in source and binary forms, with or without

     7  * modification, are permitted provided that the following conditions are met:

     8  *

     9  *   1. Redistributions of source code must retain the above copyright

    10  *      notice, this list of conditions and the following disclaimer.

    11  *

    12  *   2. Redistributions in binary form must reproduce the above copyright

    13  *      notice, this list of conditions and the following disclaimer in the

    14  *      documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE

    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

    26  * POSSIBILITY OF SUCH DAMAGE.

    27  */

    29 #include <stdlib.h>

    30 #include <string.h>

    31 #include <stdarg.h>

    32 #include <stdint.h>

    33 #include <ctype.h>

    35 #include "string.h"

    36 #include "allocator.h"

    38 sstr_t sstr(char *cstring) {

    39     sstr_t string;

    40     string.ptr = cstring;

    41     string.length = strlen(cstring);

    42     return string;

    43 }

    45 sstr_t sstrn(char *cstring, size_t length) {

    46     sstr_t string;

    47     string.ptr = cstring;

    48     string.length = length;

    49     return string;

    50 }

    52 size_t sstrnlen(size_t n, sstr_t s, ...) {

    53     va_list ap;

    54     size_t size = s.length;

    55     va_start(ap, s);

    57     for (size_t i = 1 ; i < n ; i++) {

    58         sstr_t str = va_arg(ap, sstr_t);

    59         size += str.length;

    60     }

    61     va_end(ap);

    63     return size;

    64 }

    66 static sstr_t sstrvcat_a(

    67         UcxAllocator *a,

    68         size_t count,

    69         sstr_t s1,

    70         sstr_t s2,

    71         va_list ap) {

    72     sstr_t str;

    73     str.ptr = NULL;

    74     str.length = 0;

    75     if(count < 2) {

    76         return str;

    77     }

    79     sstr_t *strings = (sstr_t*) calloc(count, sizeof(sstr_t));

    80     if(!strings) {

    81         return str;

    82     }

    84     // get all args and overall length

    85     strings[0] = s1;

    86     strings[1] = s2;

    87     size_t strlen = s1.length + s2.length;

    88     for (size_t i=2;i<count;i++) {

    89         sstr_t s = va_arg (ap, sstr_t);

    90         strings[i] = s;

    91         strlen += s.length;

    92     }

    94     // create new string

    95     str.ptr = (char*) almalloc(a, strlen + 1);

    96     str.length = strlen;

    97     if(!str.ptr) {

    98         free(strings);

    99         str.length = 0;

   100         return str;

   101     }

   103     // concatenate strings

   104     size_t pos = 0;

   105     for (size_t i=0;i<count;i++) {

   106         sstr_t s = strings[i];

   107         memcpy(str.ptr + pos, s.ptr, s.length);

   108         pos += s.length;

   109     }

   111     str.ptr[str.length] = '\0';

   113     free(strings);

   115     return str;

   116 }

   118 sstr_t sstrcat(size_t count, sstr_t s1, sstr_t s2, ...) {

   119     va_list ap;

   120     va_start(ap, s2);

   121     sstr_t s = sstrvcat_a(ucx_default_allocator(), count, s1, s2, ap);

   122     va_end(ap);

   123     return s;

   124 }

   126 sstr_t sstrcat_a(UcxAllocator *a, size_t count, sstr_t s1, sstr_t s2, ...) {

   127     va_list ap;

   128     va_start(ap, s2);

   129     sstr_t s = sstrvcat_a(a, count, s1, s2, ap);

   130     va_end(ap);

   131     return s;

   132 }

   134 sstr_t sstrsubs(sstr_t s, size_t start) {

   135     return sstrsubsl (s, start, s.length-start);

   136 }

   138 sstr_t sstrsubsl(sstr_t s, size_t start, size_t length) {

   139     sstr_t new_sstr;

   140     if (start >= s.length) {

   141         new_sstr.ptr = NULL;

   142         new_sstr.length = 0;

   143     } else {

   144         if (length > s.length-start) {

   145             length = s.length-start;

   146         }

   147         new_sstr.ptr = &s.ptr[start];

   148         new_sstr.length = length;

   149     }

   150     return new_sstr;

   151 }

   153 sstr_t sstrchr(sstr_t s, int c) {

   154     for(size_t i=0;i<s.length;i++) {

   155         if(s.ptr[i] == c) {

   156             return sstrsubs(s, i);

   157         }

   158     }

   159     sstr_t n;

   160     n.ptr = NULL;

   161     n.length = 0;

   162     return n;

   163 }

   165 sstr_t sstrrchr(sstr_t s, int c) {

   166     if (s.length > 0) {

   167         for(size_t i=s.length;i>0;i--) {

   168             if(s.ptr[i-1] == c) {

   169                 return sstrsubs(s, i-1);

   170             }

   171         }

   172     }

   173     sstr_t n;

   174     n.ptr = NULL;

   175     n.length = 0;

   176     return n;

   177 }

   179 #define ptable_r(dest, useheap, ptable, index) (dest = useheap ? \

   180     ((size_t*)ptable)[index] : (size_t) ((uint8_t*)ptable)[index])

   182 #define ptable_w(useheap, ptable, index, src) do {\

   183     if (!useheap) ((uint8_t*)ptable)[index] = (uint8_t) src;\

   184     else ((size_t*)ptable)[index] = src;\

   185     } while (0);

   187 sstr_t sstrstr(sstr_t string, sstr_t match) {

   188     if (match.length == 0) {

   189         return string;

   190     }

   192     /* prepare default return value in case of no match */

   193     sstr_t result = sstrn(NULL, 0);

   195     /*

   196      * IMPORTANT:

   197      * our prefix table contains the prefix length PLUS ONE

   198      * this is our decision, because we want to use the full range of size_t

   199      * the original algorithm needs a (-1) at one single place

   200      * and we want to avoid that

   201      */

   203     /* static prefix table */

   204     static uint8_t s_prefix_table[256];

   206     /* check pattern length and use appropriate prefix table */

   207     /* if the pattern exceeds static prefix table, allocate on the heap */

   208     register int useheap = match.length > 255;

   209     register void* ptable = useheap ?

   210         calloc(match.length+1, sizeof(size_t)): s_prefix_table;

   212     /* keep counter in registers */

   213     register size_t i, j;

   215     /* fill prefix table */

   216     i = 0; j = 0;

   217     ptable_w(useheap, ptable, i, j);

   218     while (i < match.length) {

   219         while (j >= 1 && match.ptr[j-1] != match.ptr[i]) {

   220             ptable_r(j, useheap, ptable, j-1);

   221         }

   222         i++; j++;

   223         ptable_w(useheap, ptable, i, j);

   224     }

   226     /* search */

   227     i = 0; j = 1;

   228     while (i < string.length) {

   229         while (j >= 1 && string.ptr[i] != match.ptr[j-1]) {

   230             ptable_r(j, useheap, ptable, j-1);

   231         }

   232         i++; j++;

   233         if (j-1 == match.length) {

   234             size_t start = i - match.length;

   235             result.ptr = string.ptr + start;

   236             result.length = string.length - start;

   237             break;

   238         }

   239     }

   241     /* if prefix table was allocated on the heap, free it */

   242     if (ptable != s_prefix_table) {

   243         free(ptable);

   244     }

   246     return result;

   247 }

   249 #undef ptable_r

   250 #undef ptable_w

   252 sstr_t* sstrsplit(sstr_t s, sstr_t d, ssize_t *n) {

   253     return sstrsplit_a(ucx_default_allocator(), s, d, n);

   254 }

   256 sstr_t* sstrsplit_a(UcxAllocator *allocator, sstr_t s, sstr_t d, ssize_t *n) {

   257     if (s.length == 0 || d.length == 0) {

   258         *n = -1;

   259         return NULL;

   260     }

   262     /* special cases: delimiter is at least as large as the string */

   263     if (d.length >= s.length) {

   264         /* exact match */

   265         if (sstrcmp(s, d) == 0) {

   266             *n = 0;

   267             return NULL;

   268         } else /* no match possible */ {

   269             *n = 1;

   270             sstr_t *result = (sstr_t*) almalloc(allocator, sizeof(sstr_t));

   271             *result = sstrdup_a(allocator, s);

   272             return result;

   273         }

   274     }

   276     ssize_t nmax = *n;

   277     size_t arrlen = 16;

   278     sstr_t* result = (sstr_t*) almalloc(allocator, arrlen*sizeof(sstr_t));

   280     if (result) {

   281         sstr_t curpos = s;

   282         ssize_t j = 1;

   283         while (1) {

   284             sstr_t match;

   285             /* optimize for one byte delimiters */

   286             if (d.length == 1) {

   287                 match = curpos;

   288                 for (size_t i = 0 ; i < curpos.length ; i++) {

   289                     if (curpos.ptr[i] == *(d.ptr)) {

   290                         match.ptr = curpos.ptr + i;

   291                         break;

   292                     }

   293                     match.length--;

   294                 }

   295             } else {

   296                 match = sstrstr(curpos, d);

   297             }

   298             if (match.length > 0) {

   299                 /* is this our last try? */

   300                 if (nmax == 0 || j < nmax) {

   301                     /* copy the current string to the array */

   302                     sstr_t item = sstrn(curpos.ptr, match.ptr - curpos.ptr);

   303                     result[j-1] = sstrdup_a(allocator, item);

   304                     size_t processed = item.length + d.length;

   305                     curpos.ptr += processed;

   306                     curpos.length -= processed;

   308                     /* allocate memory for the next string */

   309                     j++;

   310                     if (j > arrlen) {

   311                         arrlen *= 2;

   312                         sstr_t* reallocated = (sstr_t*) alrealloc(

   313                                 allocator, result, arrlen*sizeof(sstr_t));

   314                         if (reallocated) {

   315                             result = reallocated;

   316                         } else {

   317                             for (ssize_t i = 0 ; i < j-1 ; i++) {

   318                                 alfree(allocator, result[i].ptr);

   319                             }

   320                             alfree(allocator, result);

   321                             *n = -2;

   322                             return NULL;

   323                         }

   324                     }

   325                 } else {

   326                     /* nmax reached, copy the _full_ remaining string */

   327                     result[j-1] = sstrdup_a(allocator, curpos);

   328                     break;

   329                 }

   330             } else {

   331                 /* no more matches, copy last string */

   332                 result[j-1] = sstrdup_a(allocator, curpos);

   333                 break;

   334             }

   335         }

   336         *n = j;

   337     } else {

   338         *n = -2;

   339     }

   341     return result;

   342 }

   344 int sstrcmp(sstr_t s1, sstr_t s2) {

   345     if (s1.length == s2.length) {

   346         return memcmp(s1.ptr, s2.ptr, s1.length);

   347     } else if (s1.length > s2.length) {

   348         return 1;

   349     } else {

   350         return -1;

   351     }

   352 }

   354 int sstrcasecmp(sstr_t s1, sstr_t s2) {

   355     if (s1.length == s2.length) {

   356 #ifdef _WIN32

   357         return _strnicmp(s1.ptr, s2.ptr, s1.length);

   358 #else

   359         return strncasecmp(s1.ptr, s2.ptr, s1.length);

   360 #endif

   361     } else if (s1.length > s2.length) {

   362         return 1;

   363     } else {

   364         return -1;

   365     }

   366 }

   368 sstr_t sstrdup(sstr_t s) {

   369     return sstrdup_a(ucx_default_allocator(), s);

   370 }

   372 sstr_t sstrdup_a(UcxAllocator *allocator, sstr_t s) {

   373     sstr_t newstring;

   374     newstring.ptr = (char*)almalloc(allocator, s.length + 1);

   375     if (newstring.ptr) {

   376         newstring.length = s.length;

   377         newstring.ptr[newstring.length] = 0;

   379         memcpy(newstring.ptr, s.ptr, s.length);

   380     } else {

   381         newstring.length = 0;

   382     }

   384     return newstring;

   385 }

   387 sstr_t sstrtrim(sstr_t string) {

   388     sstr_t newstr = string;

   390     while (newstr.length > 0 && isspace(*newstr.ptr)) {

   391         newstr.ptr++;

   392         newstr.length--;

   393     }

   394     while (newstr.length > 0 && isspace(newstr.ptr[newstr.length-1])) {

   395         newstr.length--;

   396     }

   398     return newstr;

   399 }

   401 int sstrprefix(sstr_t string, sstr_t prefix) {

   402     if (string.length == 0) {

   403         return prefix.length == 0;

   404     }

   405     if (prefix.length == 0) {

   406         return 1;

   407     }

   409     if (prefix.length > string.length) {

   410         return 0;

   411     } else {

   412         return memcmp(string.ptr, prefix.ptr, prefix.length) == 0;

   413     }

   414 }

   416 int sstrsuffix(sstr_t string, sstr_t suffix) {

   417     if (string.length == 0) {

   418         return suffix.length == 0;

   419     }

   420     if (suffix.length == 0) {

   421         return 1;

   422     }

   424     if (suffix.length > string.length) {

   425         return 0;

   426     } else {

   427         return memcmp(string.ptr+string.length-suffix.length,

   428             suffix.ptr, suffix.length) == 0;

   429     }

   430 }

   432 sstr_t sstrlower(sstr_t string) {

   433     sstr_t ret = sstrdup(string);

   434     for (size_t i = 0; i < ret.length ; i++) {

   435         ret.ptr[i] = tolower(ret.ptr[i]);

   436     }

   437     return ret;

   438 }

   440 sstr_t sstrlower_a(UcxAllocator *allocator, sstr_t string) {

   441     sstr_t ret = sstrdup_a(allocator, string);

   442     for (size_t i = 0; i < ret.length ; i++) {

   443         ret.ptr[i] = tolower(ret.ptr[i]);

   444     }

   445     return ret;

   446 }

   448 sstr_t sstrupper(sstr_t string) {

   449     sstr_t ret = sstrdup(string);

   450     for (size_t i = 0; i < ret.length ; i++) {

   451         ret.ptr[i] = toupper(ret.ptr[i]);

   452     }

   453     return ret;

   454 }

   456 sstr_t sstrupper_a(UcxAllocator *allocator, sstr_t string) {

   457     sstr_t ret = sstrdup_a(allocator, string);

   458     for (size_t i = 0; i < ret.length ; i++) {

   459         ret.ptr[i] = toupper(ret.ptr[i]);

   460     }

   461     return ret;

   462 }

Mercurial > hg > ucx / file revision

ucx/string.c@b7d1317b138e

ucx/string.c