toolkit: comparison ucx/string.c

-:11f3bb408051
+:62921b370c60
 /*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
-* Copyright 2015 Olaf Wintermann. All rights reserved.
+* Copyright 2016 Olaf Wintermann. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 */
 #include <stdlib.h>
 #include <string.h>
 #include <stdarg.h>
+#include <stdint.h>
 #include <ctype.h>
 #include "string.h"
 #include "allocator.h"
 n.ptr = NULL;
 n.length = 0;
 return n;
 }
+#define ptable_r(dest, useheap, ptable, index) (dest = useheap ? \
+((size_t*)ptable)[index] : (size_t) ((uint8_t*)ptable)[index])
+#define ptable_w(useheap, ptable, index, src) do {\
+if (!useheap) ((uint8_t*)ptable)[index] = (uint8_t) src;\
+else ((size_t*)ptable)[index] = src;\
+} while (0);
+sstr_t sstrstr(sstr_t string, sstr_t match) {
+if (match.length == 0) {
+return string;
+}
+/* prepare default return value in case of no match */
+sstr_t result = sstrn(NULL, 0);
+/*
+* IMPORTANT:
+* our prefix table contains the prefix length PLUS ONE
+* this is our decision, because we want to use the full range of size_t
+* the original algorithm needs a (-1) at one single place
+* and we want to avoid that
+*/
+/* static prefix table */
+static uint8_t s_prefix_table[256];
+/* check pattern length and use appropriate prefix table */
+/* if the pattern exceeds static prefix table, allocate on the heap */
+register int useheap = match.length > 255;
+register void* ptable = useheap ?
+calloc(match.length+1, sizeof(size_t)): s_prefix_table;
+/* keep counter in registers */
+register size_t i, j;
+/* fill prefix table */
+i = 0; j = 0;
+ptable_w(useheap, ptable, i, j);
+while (i < match.length) {
+while (j >= 1 && match.ptr[j-1] != match.ptr[i]) {
+ptable_r(j, useheap, ptable, j-1);
+}
+i++; j++;
+ptable_w(useheap, ptable, i, j);
+}
+/* search */
+i = 0; j = 1;
+while (i < string.length) {
+while (j >= 1 && string.ptr[i] != match.ptr[j-1]) {
+ptable_r(j, useheap, ptable, j-1);
+}
+i++; j++;
+if (j-1 == match.length) {
+size_t start = i - match.length;
+result.ptr = string.ptr + start;
+result.length = string.length - start;
+break;
+}
+}
+/* if prefix table was allocated on the heap, free it */
+if (ptable != s_prefix_table) {
+free(ptable);
+}
+return result;
+}
+#undef ptable_r
+#undef ptable_w
 sstr_t* sstrsplit(sstr_t s, sstr_t d, ssize_t *n) {
 return sstrsplit_a(ucx_default_allocator(), s, d, n);
 }
 sstr_t* sstrsplit_a(UcxAllocator *allocator, sstr_t s, sstr_t d, ssize_t *n) {
 if (s.length == 0 || d.length == 0) {
 *n = -1;
 return NULL;
 }
-sstr_t* result;
+/* special cases: delimiter is at least as large as the string */
+if (d.length >= s.length) {
+/* exact match */
+if (sstrcmp(s, d) == 0) {
+*n = 0;
+return NULL;
+} else /* no match possible */ {
+*n = 1;
+sstr_t *result = (sstr_t*) almalloc(allocator, sizeof(sstr_t));
+*result = sstrdup_a(allocator, s);
+return result;
+}
+}
 ssize_t nmax = *n;
-*n = 1;
+size_t arrlen = 16;
+sstr_t* result = (sstr_t*) almalloc(allocator, arrlen*sizeof(sstr_t));
-/* special case: exact match - no processing needed */
-if (sstrcmp(s, d) == 0) {
+if (result) {
-*n = 0;
+sstr_t curpos = s;
-return NULL;
+ssize_t j = 1;
-}
+while (1) {
-sstr_t sv = sstrdup(s);
+sstr_t match;
-if (sv.length == 0) {
+/* optimize for one byte delimiters */
-*n = -2;
+if (d.length == 1) {
-return NULL;
+match = curpos;
-}
+for (size_t i = 0 ; i < curpos.length ; i++) {
+if (curpos.ptr[i] == *(d.ptr)) {
-for (size_t i = 0 ; i < s.length ; i++) {
+match.ptr = curpos.ptr + i;
-if (sv.ptr[i] == d.ptr[0]) {
+break;
-_Bool match = 1;
+}
-for (size_t j = 1 ; j < d.length ; j++) {
+match.length--;
-if (j+i < s.length) {
+}
-match &= (sv.ptr[i+j] == d.ptr[j]);
+} else {
+match = sstrstr(curpos, d);
+}
+if (match.length > 0) {
+/* is this our last try? */
+if (nmax == 0 || j < nmax) {
+/* copy the current string to the array */
+sstr_t item = sstrn(curpos.ptr, match.ptr - curpos.ptr);
+result[j-1] = sstrdup_a(allocator, item);
+size_t processed = item.length + d.length;
+curpos.ptr += processed;
+curpos.length -= processed;
+/* allocate memory for the next string */
+j++;
+if (j > arrlen) {
+arrlen *= 2;
+sstr_t* reallocated = (sstr_t*) alrealloc(
+allocator, result, arrlen*sizeof(sstr_t));
+if (reallocated) {
+result = reallocated;
+} else {
+for (ssize_t i = 0 ; i < j-1 ; i++) {
+alfree(allocator, result[i].ptr);
+}
+alfree(allocator, result);
+*n = -2;
+return NULL;
+}
+}
 } else {
-match = 0;
+/* nmax reached, copy the _full_ remaining string */
+result[j-1] = sstrdup_a(allocator, curpos);
 break;
 }
-}
-if (match) {
-(*n)++;
-for (size_t j = 0 ; j < d.length ; j++) {
-sv.ptr[i+j] = 0;
-}
-i += d.length;
-}
-}
-if ((*n) == nmax) break;
-}
-result = (sstr_t*) almalloc(allocator, sizeof(sstr_t)*(*n));
-if (result) {
-char *pptr = sv.ptr;
-for (ssize_t i = 0 ; i < *n ; i++) {
-size_t l = strlen(pptr);
-char* ptr = (char*) almalloc(allocator, l + 1);
-if (ptr) {
-memcpy(ptr, pptr, l);
-ptr[l] = 0;
-result[i] = sstrn(ptr, l);
-pptr += l + d.length;
 } else {
-for (ssize_t j = i-1 ; j >= 0 ; j--) {
+/* no more matches, copy last string */
-alfree(allocator, result[j].ptr);
+result[j-1] = sstrdup_a(allocator, curpos);
-}
-alfree(allocator, result);
-*n = -2;
 break;
 }
 }
+*n = j;
 } else {
 *n = -2;
 }
-free(sv.ptr);
 return result;
 }
 int sstrcmp(sstr_t s1, sstr_t s2) {

Mercurial > hg > toolkit / file comparison

comparison: ucx/string.c

ucx/string.c