Merge pull request #9085 from pauloscustodio/master

Add Perl, C and C++ solutions

15 files changed, 1320 insertions, 2 deletions

diff --git a/challenge-001/paulo-custodio/forth/ch-1.fs b/challenge-001/paulo-custodio/forth/ch-1.fs
index 6f8220bcf9..0c41bf47c7 100644
--- a/challenge-001/paulo-custodio/forth/ch-1.fs
+++ b/challenge-001/paulo-custodio/forth/ch-1.fs
@@ -3,8 +3,8 @@
 \ Challenge 001
 \
 \ Challenge #1
-\ Write a script to replace the character ‘e’ with ‘E’ in the string
-\ ‘Perl Weekly Challenge’. Also print the number of times the character ‘e’
+\ Write a script to replace the character 'e' with 'E' in the string
+\ 'Perl Weekly Challenge'. Also print the number of times the character 'e'
 \ is found in the string.
 
 \ init PAD as empty string
diff --git a/challenge-240/paulo-custodio/Makefile b/challenge-240/paulo-custodio/Makefile
new file mode 100644
index 0000000000..c3c762d746
--- /dev/null
+++ b/challenge-240/paulo-custodio/Makefile
@@ -0,0 +1,2 @@
+all:
+	perl ../../challenge-001/paulo-custodio/test.pl
diff --git a/challenge-240/paulo-custodio/c/ch-1.c b/challenge-240/paulo-custodio/c/ch-1.c
new file mode 100644
index 0000000000..dc0865dc37
--- /dev/null
+++ b/challenge-240/paulo-custodio/c/ch-1.c
@@ -0,0 +1,97 @@
+/*
+Challenge 240
+
+Task 1: Acronym
+Submitted by: Mohammad S Anwar
+
+You are given an array of strings and a check string.
+
+Write a script to find out if the check string is the acronym of the words in
+the given array.
+Example 1
+
+Input: @str = ("Perl", "Python", "Pascal")
+       $chk = "ppp"
+Output: true
+
+Example 2
+
+Input: @str = ("Perl", "Raku")
+       $chk = "rp"
+Output: false
+
+Example 3
+
+Input: @str = ("Oracle", "Awk", "C")
+       $chk = "oac"
+Output: true
+*/
+
+#include "utarray.h"
+#include "utstring.h"
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+void usage(void) {
+    fputs("Usage: ch-1 -str s1 s2 s3 ... -chk check\n", stderr);
+    exit(EXIT_FAILURE);
+}
+
+int main(int argc, char* argv[]) {
+    UT_array* strs;
+    utarray_new(strs, &ut_str_icd);
+
+    UT_string* check;
+    utstring_new(check);
+
+    UT_string* inits;
+    utstring_new(inits);
+
+    // parse args
+    int i = 1;
+    while (i < argc) {
+        if (0 == strcmp(argv[i], "-str")) {
+            i++;
+            while (i < argc && argv[i][0] != '-') {
+                utarray_push_back(strs, &argv[i]);
+                i++;
+            }
+        }
+        else if (0 == strcmp(argv[i], "-chk")) {
+            i++;
+            if (i < argc) {
+                utstring_clear(check);
+                utstring_printf(check, "%s", argv[i]);
+                i++;
+            }
+        }
+        else {
+            usage();
+        }
+    }
+    if (utarray_len(strs) == 0 || utstring_len(check) == 0)
+        usage();
+
+    // process
+    utstring_clear(inits);
+    for (size_t i = 0; i < utarray_len(strs); i++) {
+        char* str = *(char**)utarray_eltptr(strs, i);
+        utstring_printf(inits, "%c", tolower(str[0]));
+    }
+
+    for (size_t i = 0; i < utstring_len(check); i++) {
+        utstring_body(check)[i] = tolower(utstring_body(check)[i]);
+    }
+
+    if (0 == strcmp(utstring_body(inits), utstring_body(check))) {
+        puts("true");
+    }
+    else {
+        puts("false");
+    }
+
+    utarray_free(strs);
+    utstring_free(check);
+    utstring_free(inits);
+}
diff --git a/challenge-240/paulo-custodio/c/ch-2.c b/challenge-240/paulo-custodio/c/ch-2.c
new file mode 100644
index 0000000000..a95c66a1ba
--- /dev/null
+++ b/challenge-240/paulo-custodio/c/ch-2.c
@@ -0,0 +1,60 @@
+/*
+Challenge 240
+
+Task 2: Build Array
+Submitted by: Mohammad S Anwar
+
+You are given an array of integers.
+
+Write a script to create an array such that new[i] = old[old[i]] where 0 <= i < new.length.
+Example 1
+
+Input: @int = (0, 2, 1, 5, 3, 4)
+Output: (0, 1, 2, 4, 5, 3)
+
+Example 2
+
+Input: @int = (5, 0, 1, 2, 3, 4)
+Output: (4, 5, 0, 1, 2, 3)
+*/
+
+#include "utarray.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+int main(int argc, char* argv[]) {
+    if (argc < 2) {
+        fputs("Usage: ch-2 n n n ...\n", stderr);
+        exit(EXIT_FAILURE);
+    }
+
+    UT_array* old;
+    utarray_new(old, &ut_int_icd);
+
+    UT_array* new;
+    utarray_new(new, &ut_int_icd);
+
+    // parse args
+    for (int i = 1; i < argc; i++) {
+        int n = atoi(argv[i]);
+        utarray_push_back(old, &n);
+    }
+
+    // process
+    for (size_t i = 0; i < utarray_len(old); i++) {
+        int* old_p = (int*)utarray_eltptr(old, 0);
+        int n = old_p[old_p[i]];
+        utarray_push_back(new, &n);
+    }
+
+    // output
+    const char* sep = "";
+    for (size_t i = 0; i < utarray_len(new); i++) {
+        printf("%s%d", sep, *(int*)utarray_eltptr(new, i));
+        sep = " ";
+    }
+    printf("\n");
+
+    utarray_free(old);
+    utarray_free(new);
+}
diff --git a/challenge-240/paulo-custodio/c/utarray.h b/challenge-240/paulo-custodio/c/utarray.h
new file mode 100644
index 0000000000..1fe8bc1c74
--- /dev/null
+++ b/challenge-240/paulo-custodio/c/utarray.h
@@ -0,0 +1,252 @@
+/*
+Copyright (c) 2008-2022, Troy D. Hanson  https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a dynamic array implementation using macros
+ */
+#ifndef UTARRAY_H
+#define UTARRAY_H
+
+#define UTARRAY_VERSION 2.3.0
+
+#include <stddef.h>  /* size_t */
+#include <string.h>  /* memset, etc */
+#include <stdlib.h>  /* exit */
+
+#ifdef __GNUC__
+#define UTARRAY_UNUSED __attribute__((__unused__))
+#else
+#define UTARRAY_UNUSED
+#endif
+
+#ifndef utarray_oom
+#define utarray_oom() exit(-1)
+#endif
+
+typedef void (ctor_f)(void *dst, const void *src);
+typedef void (dtor_f)(void *elt);
+typedef void (init_f)(void *elt);
+typedef struct {
+    size_t sz;
+    init_f *init;
+    ctor_f *copy;
+    dtor_f *dtor;
+} UT_icd;
+
+typedef struct {
+    unsigned i,n;/* i: index of next available slot, n: num slots */
+    UT_icd icd;  /* initializer, copy and destructor functions */
+    char *d;     /* n slots of size icd->sz*/
+} UT_array;
+
+#define utarray_init(a,_icd) do {                                             \
+  memset(a,0,sizeof(UT_array));                                               \
+  (a)->icd = *(_icd);                                                         \
+} while(0)
+
+#define utarray_done(a) do {                                                  \
+  if ((a)->n) {                                                               \
+    if ((a)->icd.dtor) {                                                      \
+      unsigned _ut_i;                                                         \
+      for(_ut_i=0; _ut_i < (a)->i; _ut_i++) {                                 \
+        (a)->icd.dtor(utarray_eltptr(a,_ut_i));                               \
+      }                                                                       \
+    }                                                                         \
+    free((a)->d);                                                             \
+  }                                                                           \
+  (a)->n=0;                                                                   \
+} while(0)
+
+#define utarray_new(a,_icd) do {                                              \
+  (a) = (UT_array*)malloc(sizeof(UT_array));                                  \
+  if ((a) == NULL) {                                                          \
+    utarray_oom();                                                            \
+  }                                                                           \
+  utarray_init(a,_icd);                                                       \
+} while(0)
+
+#define utarray_free(a) do {                                                  \
+  utarray_done(a);                                                            \
+  free(a);                                                                    \
+} while(0)
+
+#define utarray_reserve(a,by) do {                                            \
+  if (((a)->i+(by)) > (a)->n) {                                               \
+    char *utarray_tmp;                                                        \
+    while (((a)->i+(by)) > (a)->n) { (a)->n = ((a)->n ? (2*(a)->n) : 8); }    \
+    utarray_tmp=(char*)realloc((a)->d, (a)->n*(a)->icd.sz);                   \
+    if (utarray_tmp == NULL) {                                                \
+      utarray_oom();                                                          \
+    }                                                                         \
+    (a)->d=utarray_tmp;                                                       \
+  }                                                                           \
+} while(0)
+
+#define utarray_push_back(a,p) do {                                           \
+  utarray_reserve(a,1);                                                       \
+  if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); }      \
+  else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); };              \
+} while(0)
+
+#define utarray_pop_back(a) do {                                              \
+  if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); }       \
+  else { (a)->i--; }                                                          \
+} while(0)
+
+#define utarray_extend_back(a) do {                                           \
+  utarray_reserve(a,1);                                                       \
+  if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); }            \
+  else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); }                   \
+  (a)->i++;                                                                   \
+} while(0)
+
+#define utarray_len(a) ((a)->i)
+
+#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL)
+#define _utarray_eltptr(a,j) ((void*)((a)->d + ((a)->icd.sz * (j))))
+
+#define utarray_insert(a,p,j) do {                                            \
+  if ((j) > (a)->i) utarray_resize(a,j);                                      \
+  utarray_reserve(a,1);                                                       \
+  if ((j) < (a)->i) {                                                         \
+    memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j),                  \
+             ((a)->i - (j))*((a)->icd.sz));                                   \
+  }                                                                           \
+  if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); }             \
+  else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); };                     \
+  (a)->i++;                                                                   \
+} while(0)
+
+#define utarray_inserta(a,w,j) do {                                           \
+  if (utarray_len(w) == 0) break;                                             \
+  if ((j) > (a)->i) utarray_resize(a,j);                                      \
+  utarray_reserve(a,utarray_len(w));                                          \
+  if ((j) < (a)->i) {                                                         \
+    memmove(_utarray_eltptr(a,(j)+utarray_len(w)),                            \
+            _utarray_eltptr(a,j),                                             \
+            ((a)->i - (j))*((a)->icd.sz));                                    \
+  }                                                                           \
+  if ((a)->icd.copy) {                                                        \
+    unsigned _ut_i;                                                           \
+    for(_ut_i=0;_ut_i<(w)->i;_ut_i++) {                                       \
+      (a)->icd.copy(_utarray_eltptr(a, (j) + _ut_i), _utarray_eltptr(w, _ut_i)); \
+    }                                                                         \
+  } else {                                                                    \
+    memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0),                        \
+           utarray_len(w)*((a)->icd.sz));                                     \
+  }                                                                           \
+  (a)->i += utarray_len(w);                                                   \
+} while(0)
+
+#define utarray_resize(dst,num) do {                                          \
+  unsigned _ut_i;                                                             \
+  if ((dst)->i > (unsigned)(num)) {                                           \
+    if ((dst)->icd.dtor) {                                                    \
+      for (_ut_i = (num); _ut_i < (dst)->i; ++_ut_i) {                        \
+        (dst)->icd.dtor(_utarray_eltptr(dst, _ut_i));                         \
+      }                                                                       \
+    }                                                                         \
+  } else if ((dst)->i < (unsigned)(num)) {                                    \
+    utarray_reserve(dst, (num) - (dst)->i);                                   \
+    if ((dst)->icd.init) {                                                    \
+      for (_ut_i = (dst)->i; _ut_i < (unsigned)(num); ++_ut_i) {              \
+        (dst)->icd.init(_utarray_eltptr(dst, _ut_i));                         \
+      }                                                                       \
+    } else {                                                                  \
+      memset(_utarray_eltptr(dst, (dst)->i), 0, (dst)->icd.sz*((num) - (dst)->i)); \
+    }                                                                         \
+  }                                                                           \
+  (dst)->i = (num);                                                           \
+} while(0)
+
+#define utarray_concat(dst,src) do {                                          \
+  utarray_inserta(dst, src, utarray_len(dst));                                \
+} while(0)
+
+#define utarray_erase(a,pos,len) do {                                         \
+  if ((a)->icd.dtor) {                                                        \
+    unsigned _ut_i;                                                           \
+    for (_ut_i = 0; _ut_i < (len); _ut_i++) {                                 \
+      (a)->icd.dtor(utarray_eltptr(a, (pos) + _ut_i));                        \
+    }                                                                         \
+  }                                                                           \
+  if ((a)->i > ((pos) + (len))) {                                             \
+    memmove(_utarray_eltptr(a, pos), _utarray_eltptr(a, (pos) + (len)),       \
+            ((a)->i - ((pos) + (len))) * (a)->icd.sz);                        \
+  }                                                                           \
+  (a)->i -= (len);                                                            \
+} while(0)
+
+#define utarray_renew(a,u) do {                                               \
+  if (a) utarray_clear(a);                                                    \
+  else utarray_new(a, u);                                                     \
+} while(0)
+
+#define utarray_clear(a) do {                                                 \
+  if ((a)->i > 0) {                                                           \
+    if ((a)->icd.dtor) {                                                      \
+      unsigned _ut_i;                                                         \
+      for(_ut_i=0; _ut_i < (a)->i; _ut_i++) {                                 \
+        (a)->icd.dtor(_utarray_eltptr(a, _ut_i));                             \
+      }                                                                       \
+    }                                                                         \
+    (a)->i = 0;                                                               \
+  }                                                                           \
+} while(0)
+
+#define utarray_sort(a,cmp) do {                                              \
+  qsort((a)->d, (a)->i, (a)->icd.sz, cmp);                                    \
+} while(0)
+
+#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp)
+
+#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL)
+#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : (((a)->i != utarray_eltidx(a,e)+1) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL))
+#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) != 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL))
+#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL)
+#define utarray_eltidx(a,e) (((char*)(e) - (a)->d) / (a)->icd.sz)
+
+/* last we pre-define a few icd for common utarrays of ints and strings */
+static void utarray_str_cpy(void *dst, const void *src) {
+  char *const *srcc = (char *const *)src;
+  char **dstc = (char**)dst;
+  if (*srcc == NULL) {
+    *dstc = NULL;
+  } else {
+    *dstc = (char*)malloc(strlen(*srcc) + 1);
+    if (*dstc == NULL) {
+      utarray_oom();
+    } else {
+      strcpy(*dstc, *srcc);
+    }
+  }
+}
+static void utarray_str_dtor(void *elt) {
+  char **eltc = (char**)elt;
+  if (*eltc != NULL) free(*eltc);
+}
+static const UT_icd ut_str_icd UTARRAY_UNUSED = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor};
+static const UT_icd ut_int_icd UTARRAY_UNUSED = {sizeof(int),NULL,NULL,NULL};
+static const UT_icd ut_ptr_icd UTARRAY_UNUSED = {sizeof(void*),NULL,NULL,NULL};
+
+
+#endif /* UTARRAY_H */
diff --git a/challenge-240/paulo-custodio/c/utstring.h b/challenge-240/paulo-custodio/c/utstring.h
new file mode 100644
index 0000000000..f0270fb632
--- /dev/null
+++ b/challenge-240/paulo-custodio/c/utstring.h
@@ -0,0 +1,407 @@
+/*
+Copyright (c) 2008-2022, Troy D. Hanson  https://troydhanson.github.io/uthash/
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* a dynamic string implementation using macros
+ */
+#ifndef UTSTRING_H
+#define UTSTRING_H
+
+#define UTSTRING_VERSION 2.3.0
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdarg.h>
+
+#ifdef __GNUC__
+#define UTSTRING_UNUSED __attribute__((__unused__))
+#else
+#define UTSTRING_UNUSED
+#endif
+
+#ifdef oom
+#error "The name of macro 'oom' has been changed to 'utstring_oom'. Please update your code."
+#define utstring_oom() oom()
+#endif
+
+#ifndef utstring_oom
+#define utstring_oom() exit(-1)
+#endif
+
+typedef struct {
+    char *d;  /* pointer to allocated buffer */
+    size_t n; /* allocated capacity */
+    size_t i; /* index of first unused byte */
+} UT_string;
+
+#define utstring_reserve(s,amt)                            \
+do {                                                       \
+  if (((s)->n - (s)->i) < (size_t)(amt)) {                 \
+    char *utstring_tmp = (char*)realloc(                   \
+      (s)->d, (s)->n + (amt));                             \
+    if (!utstring_tmp) {                                   \
+      utstring_oom();                                      \
+    }                                                      \
+    (s)->d = utstring_tmp;                                 \
+    (s)->n += (amt);                                       \
+  }                                                        \
+} while(0)
+
+#define utstring_init(s)                                   \
+do {                                                       \
+  (s)->n = 0; (s)->i = 0; (s)->d = NULL;                   \
+  utstring_reserve(s,100);                                 \
+  (s)->d[0] = '\0';                                        \
+} while(0)
+
+#define utstring_done(s)                                   \
+do {                                                       \
+  if ((s)->d != NULL) free((s)->d);                        \
+  (s)->n = 0;                                              \
+} while(0)
+
+#define utstring_free(s)                                   \
+do {                                                       \
+  utstring_done(s);                                        \
+  free(s);                                                 \
+} while(0)
+
+#define utstring_new(s)                                    \
+do {                                                       \
+  (s) = (UT_string*)malloc(sizeof(UT_string));             \
+  if (!(s)) {                                              \
+    utstring_oom();                                        \
+  }                                                        \
+  utstring_init(s);                                        \
+} while(0)
+
+#define utstring_renew(s)                                  \
+do {                                                       \
+   if (s) {                                                \
+     utstring_clear(s);                                    \
+   } else {                                                \
+     utstring_new(s);                                      \
+   }                                                       \
+} while(0)
+
+#define utstring_clear(s)                                  \
+do {                                                       \
+  (s)->i = 0;                                              \
+  (s)->d[0] = '\0';                                        \
+} while(0)
+
+#define utstring_bincpy(s,b,l)                             \
+do {                                                       \
+  utstring_reserve((s),(l)+1);                             \
+  if (l) memcpy(&(s)->d[(s)->i], b, l);                    \
+  (s)->i += (l);                                           \
+  (s)->d[(s)->i]='\0';                                     \
+} while(0)
+
+#define utstring_concat(dst,src)                                 \
+do {                                                             \
+  utstring_reserve((dst),((src)->i)+1);                          \
+  if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \
+  (dst)->i += (src)->i;                                          \
+  (dst)->d[(dst)->i]='\0';                                       \
+} while(0)
+
+#define utstring_len(s) ((s)->i)
+
+#define utstring_body(s) ((s)->d)
+
+UTSTRING_UNUSED static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
+   int n;
+   va_list cp;
+   for (;;) {
+#ifdef _WIN32
+      cp = ap;
+#else
+      va_copy(cp, ap);
+#endif
+      n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
+      va_end(cp);
+
+      if ((n > -1) && ((size_t) n < (s->n-s->i))) {
+        s->i += n;
+        return;
+      }
+
+      /* Else try again with more space. */
+      if (n > -1) utstring_reserve(s,n+1); /* exact */
+      else utstring_reserve(s,(s->n)*2);   /* 2x */
+   }
+}
+#ifdef __GNUC__
+/* support printf format checking (2=the format string, 3=start of varargs) */
+static void utstring_printf(UT_string *s, const char *fmt, ...)
+  __attribute__ (( format( printf, 2, 3) ));
+#endif
+UTSTRING_UNUSED static void utstring_printf(UT_string *s, const char *fmt, ...) {
+   va_list ap;
+   va_start(ap,fmt);
+   utstring_printf_va(s,fmt,ap);
+   va_end(ap);
+}
+
+/*******************************************************************************
+ * begin substring search functions                                            *
+ ******************************************************************************/
+/* Build KMP table from left to right. */
+UTSTRING_UNUSED static void _utstring_BuildTable(
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+
+    i = 0;
+    j = i - 1;
+    P_KMP_Table[i] = j;
+    while (i < (long) P_NeedleLen)
+    {
+        while ( (j > -1) && (P_Needle[i] != P_Needle[j]) )
+        {
+           j = P_KMP_Table[j];
+        }
+        i++;
+        j++;
+        if (i < (long) P_NeedleLen)
+        {
+            if (P_Needle[i] == P_Needle[j])
+            {
+                P_KMP_Table[i] = P_KMP_Table[j];
+            }
+            else
+            {
+                P_KMP_Table[i] = j;
+            }
+        }
+        else
+        {
+            P_KMP_Table[i] = j;
+        }
+    }
+
+    return;
+}
+
+
+/* Build KMP table from right to left. */
+UTSTRING_UNUSED static void _utstring_BuildTableR(
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+
+    i = P_NeedleLen - 1;
+    j = i + 1;
+    P_KMP_Table[i + 1] = j;
+    while (i >= 0)
+    {
+        while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) )
+        {
+           j = P_KMP_Table[j + 1];
+        }
+        i--;
+        j--;
+        if (i >= 0)
+        {
+            if (P_Needle[i] == P_Needle[j])
+            {
+                P_KMP_Table[i + 1] = P_KMP_Table[j + 1];
+            }
+            else
+            {
+                P_KMP_Table[i + 1] = j;
+            }
+        }
+        else
+        {
+            P_KMP_Table[i + 1] = j;
+        }
+    }
+
+    return;
+}
+
+
+/* Search data from left to right. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_find(
+    const char *P_Haystack,
+    size_t P_HaystackLen,
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+    long V_FindPosition = -1;
+
+    /* Search from left to right. */
+    i = j = 0;
+    while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) )
+    {
+        while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) )
+        {
+            i = P_KMP_Table[i];
+        }
+        i++;
+        j++;
+        if (i >= (int)P_NeedleLen)
+        {
+            /* Found. */
+            V_FindPosition = j - i;
+            break;
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( Multiple search mode. ) */
+UTSTRING_UNUSED static long _utstring_findR(
+    const char *P_Haystack,
+    size_t P_HaystackLen,
+    const char *P_Needle,
+    size_t P_NeedleLen,
+    long *P_KMP_Table)
+{
+    long i, j;
+    long V_FindPosition = -1;
+
+    /* Search from right to left. */
+    j = (P_HaystackLen - 1);
+    i = (P_NeedleLen - 1);
+    while ( (j >= 0) && (j >= i) )
+    {
+        while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) )
+        {
+            i = P_KMP_Table[i + 1];
+        }
+        i--;
+        j--;
+        if (i < 0)
+        {
+            /* Found. */
+            V_FindPosition = j + 1;
+            break;
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from left to right. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_find(
+    UT_string *s,
+    long P_StartPosition,   /* Start from 0. -1 means last position. */
+    const char *P_Needle,
+    size_t P_NeedleLen)
+{
+    long V_StartPosition;
+    long V_HaystackLen;
+    long *V_KMP_Table;
+    long V_FindPosition = -1;
+
+    if (P_StartPosition < 0)
+    {
+        V_StartPosition = s->i + P_StartPosition;
+    }
+    else
+    {
+        V_StartPosition = P_StartPosition;
+    }
+    V_HaystackLen = s->i - V_StartPosition;
+    if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+    {
+        V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+        if (V_KMP_Table != NULL)
+        {
+            _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table);
+
+            V_FindPosition = _utstring_find(s->d + V_StartPosition,
+                                            V_HaystackLen,
+                                            P_Needle,
+                                            P_NeedleLen,
+                                            V_KMP_Table);
+            if (V_FindPosition >= 0)
+            {
+                V_FindPosition += V_StartPosition;
+            }
+
+            free(V_KMP_Table);
+        }
+    }
+
+    return V_FindPosition;
+}
+
+
+/* Search data from right to left. ( One time search mode. ) */
+UTSTRING_UNUSED static long utstring_findR(
+    UT_string *s,
+    long P_StartPosition,   /* Start from 0. -1 means last position. */
+    const char *P_Needle,
+    size_t P_NeedleLen)
+{
+    long V_StartPosition;
+    long V_HaystackLen;
+    long *V_KMP_Table;
+    long V_FindPosition = -1;
+
+    if (P_StartPosition < 0)
+    {
+        V_StartPosition = s->i + P_StartPosition;
+    }
+    else
+    {
+        V_StartPosition = P_StartPosition;
+    }
+    V_HaystackLen = V_StartPosition + 1;
+    if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) )
+    {
+        V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1));
+        if (V_KMP_Table != NULL)
+        {
+            _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table);
+
+            V_FindPosition = _utstring_findR(s->d,
+                                             V_HaystackLen,
+                                             P_Needle,
+                                             P_NeedleLen,
+                                             V_KMP_Table);
+
+            free(V_KMP_Table);
+        }
+    }
+
+    return V_FindPosition;
+}
+/*******************************************************************************
+ * end substring search functions                                              *
+ ******************************