src/libpspp/string-array.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2010 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include "libpspp/string-array.h"
  20
  21 #include <stdint.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include "libpspp/array.h"
  26 #include "libpspp/str.h"
  27
  28 #include "gl/xalloc.h"
  29
  30 /* Initializes SA as an initially empty array of strings. */
  31 void
  32 string_array_init (struct string_array *sa)
  33 {
  34   sa->strings = NULL;
  35   sa->n = 0;
  36   sa->allocated = 0;
  37 }
  38
  39 /* Initializes DST as an array of strings whose contents are initially copies
  40    of the strings in SRC. */
  41 void
  42 string_array_clone (struct string_array *dst, const struct string_array *src)
  43 {
  44   size_t i;
  45
  46   dst->strings = xmalloc (sizeof *dst->strings * src->n);
  47   for (i = 0; i < src->n; i++)
  48     dst->strings[i] = xstrdup (src->strings[i]);
  49   dst->n = src->n;
  50   dst->allocated = src->n;
  51 }
  52
  53 /* Exchanges the contents of A and B. */
  54 void
  55 string_array_swap (struct string_array *a, struct string_array *b)
  56 {
  57   struct string_array tmp = *a;
  58   *a = *b;
  59   *b = tmp;
  60 }
  61
  62 /* Frees the strings in SA.  SA must be reinitialized (with
  63    string_array_init()) before it is used again. */
  64 void
  65 string_array_destroy (struct string_array *sa)
  66 {
  67   if (sa != NULL)
  68     {
  69       string_array_clear (sa);
  70       free (sa->strings);
  71     }
  72 }
  73
  74 /* Returns true if SA contains at least one copy of STRING, otherwise false.
  75
  76    This function runs in O(n) time in the number of strings in SA. */
  77 bool
  78 string_array_contains (const struct string_array *sa, const char *string)
  79 {
  80   return string_array_find (sa, string) != SIZE_MAX;
  81 }
  82
  83 /* If SA contains at least one copy of STRING, returns the smallest index of
  84    any of those copies.  If SA does not contain STRING, returns SIZE_MAX.
  85
  86    This function runs in O(n) time in the number of strings in SA. */
  87 size_t
  88 string_array_find (const struct string_array *sa, const char *string)
  89 {
  90   size_t i;
  91
  92   for (i = 0; i < sa->n; i++)
  93     if (!strcmp (sa->strings[i], string))
  94       return i;
  95   return SIZE_MAX;
  96 }
  97
  98 /* Appends a copy of STRING to SA.  The caller retains ownership of STRING. */
  99 void
 100 string_array_append (struct string_array *sa, const char *string)
 101 {
 102   string_array_insert (sa, string, sa->n);
 103 }
 104
 105 /* Appends STRING to SA.  Ownership of STRING transfers to SA. */
 106 void
 107 string_array_append_nocopy (struct string_array *sa, char *string)
 108 {
 109   string_array_insert_nocopy (sa, string, sa->n);
 110 }
 111
 112 /* Inserts a copy of STRING in SA just before the string with index BEFORE,
 113    which must be less than or equal to the number of strings in SA.  The caller
 114    retains ownership of STRING.
 115
 116    In general, this function runs in O(n) time in the number of strings that
 117    must be shifted to higher indexes; if BEFORE is the number of strings in SA,
 118    it runs in amortized constant time. */
 119 void
 120 string_array_insert (struct string_array *sa,
 121                      const char *string, size_t before)
 122 {
 123   string_array_insert_nocopy (sa, xstrdup (string), before);
 124 }
 125
 126 static void
 127 string_array_expand__ (struct string_array *sa)
 128 {
 129   if (sa->n >= sa->allocated)
 130     sa->strings = x2nrealloc (sa->strings, &sa->allocated,
 131                               sizeof *sa->strings);
 132 }
 133
 134 /* Inserts STRING in SA just before the string with index BEFORE, which must be
 135    less than or equal to the number of strings in SA.  Ownership of STRING
 136    transfers to SA.
 137
 138    In general, this function runs in O(n) time in the number of strings that
 139    must be shifted to higher indexes; if BEFORE is the number of strings in SA,
 140    it runs in amortized constant time. */
 141 void
 142 string_array_insert_nocopy (struct string_array *sa, char *string,
 143                             size_t before)
 144 {
 145   string_array_expand__ (sa);
 146   if (before < sa->n)
 147     insert_element (sa->strings, sa->n, sizeof *sa->strings, before);
 148
 149   sa->strings[before] = string;
 150   sa->n++;
 151 }
 152
 153 /* Deletes from SA the string with index IDX, which must be less than the
 154    number of strings in SA, and shifts down the strings with higher indexes.
 155    Frees the string.
 156
 157    In general, this function runs in O(n) time in the number of strings that
 158    must be shifted to lower indexes.  If IDX is the last string in SA, it runs
 159    in amortized constant time. */
 160 void
 161 string_array_delete (struct string_array *sa, size_t idx)
 162 {
 163   free (string_array_delete_nofree (sa, idx));
 164 }
 165
 166 /* Deletes from SA the string with index IDX, which must be less than the
 167    number of strings in SA.  Returns the string, which the caller is
 168    responsible for freeing with free().
 169
 170    In general, this function runs in O(n) time in the number of strings that
 171    must be shifted to lower indexes.  If IDX is the last string in SA, it runs
 172    in amortized constant time. */
 173 char *
 174 string_array_delete_nofree (struct string_array *sa, size_t idx)
 175 {
 176   char *s = sa->strings[idx];
 177   if (idx != sa->n - 1)
 178     remove_element (sa->strings, sa->n, sizeof *sa->strings, idx);
 179   sa->n--;
 180   return s;
 181 }
 182
 183 /* Deletes all of the strings from SA and frees them. */
 184 void
 185 string_array_clear (struct string_array *sa)
 186 {
 187   size_t i;
 188
 189   for (i = 0; i < sa->n; i++)
 190     free (sa->strings[i]);
 191   sa->n = 0;
 192 }
 193
 194 /* Ensures that 'sa->strings[sa->n]' is a null pointer (until SA is modified
 195    further). */
 196 void
 197 string_array_terminate_null (struct string_array *sa)
 198 {
 199   string_array_expand__ (sa);
 200   sa->strings[sa->n] = NULL;
 201 }
 202
 203 /* Reduces the amount of memory allocated for SA's strings to the minimum
 204    necessary. */
 205 void
 206 string_array_shrink (struct string_array *sa)
 207 {
 208   if (sa->allocated > sa->n)
 209     {
 210       if (sa->n > 0)
 211         sa->strings = xrealloc (sa->strings, sa->n * sizeof *sa->strings);
 212       else
 213         {
 214           free (sa->strings);
 215           sa->strings = NULL;
 216         }
 217       sa->allocated = sa->n;
 218     }
 219 }
 220
 221 static int
 222 compare_strings (const void *a_, const void *b_)
 223 {
 224   const void *const *a = a_;
 225   const void *const *b = b_;
 226
 227   return strcmp (*a, *b);
 228 }
 229
 230 /* Sorts the strings in SA into order according to strcmp(). */
 231 void
 232 string_array_sort (struct string_array *sa)
 233 {
 234   qsort (sa->strings, sa->n, sizeof *sa->strings, compare_strings);
 235 }
 236
 237 /* Removes all but one of any series of adjacent duplicate strings in SA. */
 238 void
 239 string_array_uniq (struct string_array *sa)
 240 {
 241   if (!sa->n)
 242     return;
 243
 244   size_t n = 1;
 245   for (size_t i = 1; i < sa->n; i++)
 246     {
 247       char *s = sa->strings[i];
 248       if (strcmp (sa->strings[n - 1], s))
 249         sa->strings[n++] = s;
 250       else
 251         free (s);
 252     }
 253   sa->n = n;
 254 }
 255
 256 /* Divides STRING into tokens at DELIMITERS and adds each token to SA. */
 257 void
 258 string_array_parse (struct string_array *sa, struct substring string,
 259                     struct substring delimiters)
 260 {
 261   size_t save_idx = 0;
 262   struct substring token;
 263   while (ss_tokenize (string, delimiters, &save_idx, &token))
 264     string_array_append_nocopy (sa, ss_xstrdup (token));
 265 }
 266
 267 /* Returns a single string that consists of each of the strings in SA
 268    concatenated, separated from each other with SEPARATOR.
 269
 270    The caller is responsible for freeing the returned string with free(). */
 271 char *
 272 string_array_join (const struct string_array *sa, const char *separator)
 273 {
 274   struct string dst;
 275   const char *s;
 276   size_t i;
 277
 278   ds_init_empty (&dst);
 279   STRING_ARRAY_FOR_EACH (s, i, sa)
 280     {
 281       if (i > 0)
 282         ds_put_cstr (&dst, separator);
 283       ds_put_cstr (&dst, s);
 284     }
 285   return ds_steal_cstr (&dst);
 286 }