pintos-os.org Git - pspp/blob - 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/i18n.h"
  27 #include "libpspp/str.h"
  28
  29 #include "gl/xalloc.h"
  30
  31 /* Initializes SA as an initially empty array of strings. */
  32 void
  33 string_array_init (struct string_array *sa)
  34 {
  35   sa->strings = NULL;
  36   sa->n = 0;
  37   sa->allocated = 0;
  38 }
  39
  40 /* Initializes DST as an array of strings whose contents are initially copies
  41    of the strings in SRC. */
  42 void
  43 string_array_clone (struct string_array *dst, const struct string_array *src)
  44 {
  45   size_t i;
  46
  47   dst->strings = xmalloc (sizeof *dst->strings * src->n);
  48   for (i = 0; i < src->n; i++)
  49     dst->strings[i] = xstrdup (src->strings[i]);
  50   dst->n = src->n;
  51   dst->allocated = src->n;
  52 }
  53
  54 /* Exchanges the contents of A and B. */
  55 void
  56 string_array_swap (struct string_array *a, struct string_array *b)
  57 {
  58   struct string_array tmp = *a;
  59   *a = *b;
  60   *b = tmp;
  61 }
  62
  63 /* Frees the strings in SA.  SA must be reinitialized (with
  64    string_array_init()) before it is used again. */
  65 void
  66 string_array_destroy (struct string_array *sa)
  67 {
  68   if (sa != NULL)
  69     {
  70       string_array_clear (sa);
  71       free (sa->strings);
  72     }
  73 }
  74
  75 /* Returns true if SA contains at least one copy of STRING, otherwise false.
  76
  77    This function runs in O(n) time in the number of strings in SA. */
  78 bool
  79 string_array_contains (const struct string_array *sa, const char *string)
  80 {
  81   return string_array_find (sa, string) != SIZE_MAX;
  82 }
  83
  84 /* If SA contains at least one copy of STRING, returns the smallest index of
  85    any of those copies.  If SA does not contain STRING, returns SIZE_MAX.
  86
  87    This function runs in O(n) time in the number of strings in SA. */
  88 size_t
  89 string_array_find (const struct string_array *sa, const char *string)
  90 {
  91   size_t i;
  92
  93   for (i = 0; i < sa->n; i++)
  94     if (!strcmp (sa->strings[i], string))
  95       return i;
  96   return SIZE_MAX;
  97 }
  98
  99 /* Appends a copy of STRING to SA.  The caller retains ownership of STRING. */
 100 void
 101 string_array_append (struct string_array *sa, const char *string)
 102 {
 103   string_array_insert (sa, string, sa->n);
 104 }
 105
 106 /* Appends STRING to SA.  Ownership of STRING transfers to SA. */
 107 void
 108 string_array_append_nocopy (struct string_array *sa, char *string)
 109 {
 110   string_array_insert_nocopy (sa, string, sa->n);
 111 }
 112
 113 /* Inserts a copy of STRING in SA just before the string with index BEFORE,
 114    which must be less than or equal to the number of strings in SA.  The caller
 115    retains ownership of STRING.
 116
 117    In general, this function runs in O(n) time in the number of strings that
 118    must be shifted to higher indexes; if BEFORE is the number of strings in SA,
 119    it runs in amortized constant time. */
 120 void
 121 string_array_insert (struct string_array *sa,
 122                      const char *string, size_t before)
 123 {
 124   string_array_insert_nocopy (sa, xstrdup (string), before);
 125 }
 126
 127 static void
 128 string_array_expand__ (struct string_array *sa)
 129 {
 130   if (sa->n >= sa->allocated)
 131     sa->strings = x2nrealloc (sa->strings, &sa->allocated,
 132                               sizeof *sa->strings);
 133 }
 134
 135 /* Inserts STRING in SA just before the string with index BEFORE, which must be
 136    less than or equal to the number of strings in SA.  Ownership of STRING
 137    transfers to SA.
 138
 139    In general, this function runs in O(n) time in the number of strings that
 140    must be shifted to higher indexes; if BEFORE is the number of strings in SA,
 141    it runs in amortized constant time. */
 142 void
 143 string_array_insert_nocopy (struct string_array *sa, char *string,
 144                             size_t before)
 145 {
 146   string_array_expand__ (sa);
 147   if (before < sa->n)
 148     insert_element (sa->strings, sa->n, sizeof *sa->strings, before);
 149
 150   sa->strings[before] = string;
 151   sa->n++;
 152 }
 153
 154 /* Deletes from SA the string with index IDX, which must be less than the
 155    number of strings in SA, and shifts down the strings with higher indexes.
 156    Frees the string.
 157
 158    In general, this function runs in O(n) time in the number of strings that
 159    must be shifted to lower indexes.  If IDX is the last string in SA, it runs
 160    in amortized constant time. */
 161 void
 162 string_array_delete (struct string_array *sa, size_t idx)
 163 {
 164   free (string_array_delete_nofree (sa, idx));
 165 }
 166
 167 /* Deletes from SA the string with index IDX, which must be less than the
 168    number of strings in SA.  Returns the string, which the caller is
 169    responsible for freeing with free().
 170
 171    In general, this function runs in O(n) time in the number of strings that
 172    must be shifted to lower indexes.  If IDX is the last string in SA, it runs
 173    in amortized constant time. */
 174 char *
 175 string_array_delete_nofree (struct string_array *sa, size_t idx)
 176 {
 177   char *s = sa->strings[idx];
 178   if (idx != sa->n - 1)
 179     remove_element (sa->strings, sa->n, sizeof *sa->strings, idx);
 180   sa->n--;
 181   return s;
 182 }
 183
 184 /* Deletes all of the strings from SA and frees them. */
 185 void
 186 string_array_clear (struct string_array *sa)
 187 {
 188   size_t i;
 189
 190   for (i = 0; i < sa->n; i++)
 191     free (sa->strings[i]);
 192   sa->n = 0;
 193 }
 194
 195 /* Ensures that 'sa->strings[sa->n]' is a null pointer (until SA is modified
 196    further). */
 197 void
 198 string_array_terminate_null (struct string_array *sa)
 199 {
 200   string_array_expand__ (sa);
 201   sa->strings[sa->n] = NULL;
 202 }
 203
 204 /* Reduces the amount of memory allocated for SA's strings to the minimum
 205    necessary. */
 206 void
 207 string_array_shrink (struct string_array *sa)
 208 {
 209   if (sa->allocated > sa->n)
 210     {
 211       if (sa->n > 0)
 212         sa->strings = xrealloc (sa->strings, sa->n * sizeof *sa->strings);
 213       else
 214         {
 215           free (sa->strings);
 216           sa->strings = NULL;
 217         }
 218       sa->allocated = sa->n;
 219     }
 220 }
 221
 222 static int
 223 compare_strings (const void *a_, const void *b_)
 224 {
 225   const void *const *a = a_;
 226   const void *const *b = b_;
 227
 228   return strcmp (*a, *b);
 229 }
 230
 231 /* Sorts the strings in SA into order according to strcmp(). */
 232 void
 233 string_array_sort (struct string_array *sa)
 234 {
 235   qsort (sa->strings, sa->n, sizeof *sa->strings, compare_strings);
 236 }
 237
 238 /* Removes all but one of any series of adjacent duplicate strings in SA. */
 239 void
 240 string_array_uniq (struct string_array *sa)
 241 {
 242   if (!sa->n)
 243     return;
 244
 245   size_t n = 1;
 246   for (size_t i = 1; i < sa->n; i++)
 247     {
 248       char *s = sa->strings[i];
 249       if (strcmp (sa->strings[n - 1], s))
 250         sa->strings[n++] = s;
 251       else
 252         free (s);
 253     }
 254   sa->n = n;
 255 }
 256
 257 /* Returns true if A and B contain the same strings in the same order,
 258    false otherwise. */
 259 bool
 260 string_array_equal (const struct string_array *a,
 261                     const struct string_array *b)
 262 {
 263   if (a->n != b->n)
 264     return false;
 265
 266   for (size_t i = 0; i < a->n; i++)
 267     if (strcmp (a->strings[i], b->strings[i]))
 268       return false;
 269   return true;
 270 }
 271
 272 /* Returns true if A and B contain the same strings in the same order,
 273    false otherwise. */
 274 bool
 275 string_array_equal_case (const struct string_array *a,
 276                          const struct string_array *b)
 277 {
 278   if (a->n != b->n)
 279     return false;
 280
 281   for (size_t i = 0; i < a->n; i++)
 282     if (utf8_strcasecmp (a->strings[i], b->strings[i]))
 283       return false;
 284   return true;
 285 }
 286
 287 /* Divides STRING into tokens at DELIMITERS and adds each token to SA. */
 288 void
 289 string_array_parse (struct string_array *sa, struct substring string,
 290                     struct substring delimiters)
 291 {
 292   size_t save_idx = 0;
 293   struct substring token;
 294   while (ss_tokenize (string, delimiters, &save_idx, &token))
 295     string_array_append_nocopy (sa, ss_xstrdup (token));
 296 }
 297
 298 /* Returns a single string that consists of each of the strings in SA
 299    concatenated, separated from each other with SEPARATOR.
 300
 301    The caller is responsible for freeing the returned string with free(). */
 302 char *
 303 string_array_join (const struct string_array *sa, const char *separator)
 304 {
 305   struct string dst;
 306   const char *s;
 307   size_t i;
 308
 309   ds_init_empty (&dst);
 310   STRING_ARRAY_FOR_EACH (s, i, sa)
 311     {
 312       if (i > 0)
 313         ds_put_cstr (&dst, separator);
 314       ds_put_cstr (&dst, s);
 315     }
 316   return ds_steal_cstr (&dst);
 317 }