pintos-os.org Git - pspp/blob - src/libpspp/stringi-set.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2009, 2010, 2012 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 /* If you add routines in this file, please add a corresponding test to
  18    stringi-set-test.c. */
  19
  20 #include <config.h>
  21
  22 #include "libpspp/stringi-set.h"
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include "libpspp/cast.h"
  28 #include "libpspp/hash-functions.h"
  29 #include "libpspp/i18n.h"
  30
  31 #include "gl/xalloc.h"
  32
  33 static struct stringi_set_node *stringi_set_find_node__ (
  34   const struct stringi_set *, const char *, unsigned int hash);
  35 static void stringi_set_insert__ (struct stringi_set *, char *,
  36                                  unsigned int hash);
  37 static bool stringi_set_delete__ (struct stringi_set *, const char *,
  38                                  unsigned int hash);
  39
  40 /* Initializes SET as a new string set that is initially empty. */
  41 void
  42 stringi_set_init (struct stringi_set *set)
  43 {
  44   hmap_init (&set->hmap);
  45 }
  46
  47 /* Initializes SET as a new string set that initially contains the same strings
  48    as OLD. */
  49 void
  50 stringi_set_clone (struct stringi_set *set, const struct stringi_set *old)
  51 {
  52   const struct stringi_set_node *node;
  53   const char *s;
  54
  55   stringi_set_init (set);
  56   hmap_reserve (&set->hmap, stringi_set_count (old));
  57   STRINGI_SET_FOR_EACH (s, node, old)
  58     stringi_set_insert__ (set, xstrdup (s), node->hmap_node.hash);
  59 }
  60
  61 /* Exchanges the contents of string sets A and B. */
  62 void
  63 stringi_set_swap (struct stringi_set *a, struct stringi_set *b)
  64 {
  65   hmap_swap (&a->hmap, &b->hmap);
  66 }
  67
  68 /* Frees SET and its nodes and strings. */
  69 void
  70 stringi_set_destroy (struct stringi_set *set)
  71 {
  72   if (set != NULL)
  73     {
  74       stringi_set_clear (set);
  75       hmap_destroy (&set->hmap);
  76     }
  77 }
  78
  79 /* Returns true if SET contains S (or a similar string with different case),
  80    false otherwise. */
  81 bool
  82 stringi_set_contains (const struct stringi_set *set, const char *s)
  83 {
  84   return stringi_set_find_node (set, s) != NULL;
  85 }
  86
  87 /* Returns the node in SET that contains S, or a null pointer if SET does not
  88    contain S. */
  89 struct stringi_set_node *
  90 stringi_set_find_node (const struct stringi_set *set, const char *s)
  91 {
  92   return stringi_set_find_node__ (set, s, utf8_hash_case_string (s, 0));
  93 }
  94
  95 /* Inserts a copy of S into SET.  Returns true if successful, false if SET
  96    is unchanged because it already contained S. */
  97 bool
  98 stringi_set_insert (struct stringi_set *set, const char *s)
  99 {
 100   unsigned int hash = utf8_hash_case_string (s, 0);
 101   if (!stringi_set_find_node__ (set, s, hash))
 102     {
 103       stringi_set_insert__ (set, xstrdup (s), hash);
 104       return true;
 105     }
 106   else
 107     return false;
 108 }
 109
 110 /* Inserts S, which must be a malloc'd string, into SET, transferring ownership
 111    of S to SET.  Returns true if successful, false if SET is unchanged because
 112    it already contained a copy of S.  (In the latter case, S is freed.) */
 113 bool
 114 stringi_set_insert_nocopy (struct stringi_set *set, char *s)
 115 {
 116   unsigned int hash = utf8_hash_case_string (s, 0);
 117   if (!stringi_set_find_node__ (set, s, hash))
 118     {
 119       stringi_set_insert__ (set, s, hash);
 120       return true;
 121     }
 122   else
 123     {
 124       free (s);
 125       return false;
 126     }
 127 }
 128
 129 /* Deletes S from SET.  Returns true if successful, false if SET is unchanged
 130    because it did not contain a copy of S. */
 131 bool
 132 stringi_set_delete (struct stringi_set *set, const char *s)
 133 {
 134   return stringi_set_delete__ (set, s, utf8_hash_case_string (s, 0));
 135 }
 136
 137 /* Deletes NODE from SET, and frees NODE and its string. */
 138 void
 139 stringi_set_delete_node (struct stringi_set *set,
 140                          struct stringi_set_node *node)
 141 {
 142   free (stringi_set_delete_nofree (set, node));
 143 }
 144
 145 /* Deletes NODE from SET and frees NODE.  Returns the string that NODE
 146    contained, transferring ownership to the caller. */
 147 char *
 148 stringi_set_delete_nofree (struct stringi_set *set,
 149                            struct stringi_set_node *node)
 150 {
 151   char *string = node->string;
 152   hmap_delete (&set->hmap, &node->hmap_node);
 153   free (node);
 154   return string;
 155 }
 156
 157 /* Removes all nodes from SET. */
 158 void
 159 stringi_set_clear (struct stringi_set *set)
 160 {
 161   struct stringi_set_node *node, *next;
 162
 163   HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
 164                       &set->hmap)
 165     stringi_set_delete_node (set, node);
 166 }
 167
 168 /* Calculates A = union(A, B).
 169
 170    If B may be modified, stringi_set_union_and_intersection() is
 171    faster than this function. */
 172 void
 173 stringi_set_union (struct stringi_set *a, const struct stringi_set *b)
 174 {
 175   struct stringi_set_node *node;
 176   HMAP_FOR_EACH (node, struct stringi_set_node, hmap_node, &b->hmap)
 177     if (!stringi_set_find_node__ (a, node->string, node->hmap_node.hash))
 178       stringi_set_insert__ (a, xstrdup (node->string), node->hmap_node.hash);
 179 }
 180
 181 /* Calculates A = union(A, B) and B = intersect(A, B).
 182
 183    If only the intersection is needed, stringi_set_intersect() is
 184    faster. */
 185 void
 186 stringi_set_union_and_intersection (struct stringi_set *a,
 187                                     struct stringi_set *b)
 188 {
 189   struct stringi_set_node *node, *next;
 190
 191   HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
 192                       &b->hmap)
 193     if (!stringi_set_find_node__ (a, node->string, node->hmap_node.hash))
 194       {
 195         hmap_delete (&b->hmap, &node->hmap_node);
 196         hmap_insert (&a->hmap, &node->hmap_node, node->hmap_node.hash);
 197       }
 198 }
 199
 200 /* Calculates A = intersect(A, B). */
 201 void
 202 stringi_set_intersect (struct stringi_set *a, const struct stringi_set *b)
 203 {
 204   struct stringi_set_node *node, *next;
 205
 206   HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
 207                       &a->hmap)
 208     if (!stringi_set_find_node__ (b, node->string, node->hmap_node.hash))
 209       stringi_set_delete_node (a, node);
 210 }
 211
 212 /* Removes from A all of the strings in B. */
 213 void
 214 stringi_set_subtract (struct stringi_set *a, const struct stringi_set *b)
 215 {
 216   struct stringi_set_node *node, *next;
 217
 218   if (stringi_set_count (a) < stringi_set_count (b))
 219     {
 220       HMAP_FOR_EACH_SAFE (node, next, struct stringi_set_node, hmap_node,
 221                           &a->hmap)
 222         if (stringi_set_find_node__ (b, node->string, node->hmap_node.hash))
 223           stringi_set_delete_node (a, node);
 224     }
 225   else
 226     {
 227       HMAP_FOR_EACH (node, struct stringi_set_node, hmap_node, &b->hmap)
 228         stringi_set_delete__ (a, node->string, node->hmap_node.hash);
 229     }
 230 }
 231
 232 /* Allocates and returns an array that points to each of the strings in SET.
 233    The caller must not free or modify any of the strings.  Removing a string
 234    from SET invalidates the corresponding element of the returned array.  The
 235    caller it is responsible for freeing the returned array itself (with
 236    free()).
 237
 238    The returned array is in the same order as observed by stringi_set_first()
 239    and stringi_set_next(), that is, no particular order. */
 240 char **
 241 stringi_set_get_array (const struct stringi_set *set)
 242 {
 243   const struct stringi_set_node *node;
 244   const char *s;
 245   char **array;
 246   size_t i;
 247
 248   array = xnmalloc (stringi_set_count (set), sizeof *array);
 249
 250   i = 0;
 251   STRINGI_SET_FOR_EACH (s, node, set)
 252     array[i++] = CONST_CAST (char *, s);
 253
 254   return array;
 255 }
 256
 257 static int
 258 compare_strings (const void *a_, const void *b_)
 259 {
 260   const char *const *a = a_;
 261   const char *const *b = b_;
 262   return utf8_strcasecmp (*a, *b);
 263 }
 264
 265 /* Allocates and returns an array that points to each of the strings in SET.
 266    The caller must not free or modify any of the strings.  Removing a string
 267    from SET invalidates the corresponding element of the returned array.  The
 268    caller it is responsible for freeing the returned array itself (with
 269    free()).
 270
 271    The returned array is ordered according to utf8_strcasecmp(). */
 272 char **
 273 stringi_set_get_sorted_array (const struct stringi_set *set)
 274 {
 275   char **array = stringi_set_get_array (set);
 276   qsort (array, stringi_set_count (set), sizeof *array, compare_strings);
 277   return array;
 278 }
 279 \f
 280 /* Internal functions. */
 281
 282 static struct stringi_set_node *
 283 stringi_set_find_node__ (const struct stringi_set *set, const char *s,
 284                         unsigned int hash)
 285 {
 286   struct stringi_set_node *node;
 287
 288   HMAP_FOR_EACH_WITH_HASH (node, struct stringi_set_node, hmap_node,
 289                            hash, &set->hmap)
 290     if (!utf8_strcasecmp (s, node->string))
 291       return node;
 292
 293   return NULL;
 294 }
 295
 296 static void
 297 stringi_set_insert__ (struct stringi_set *set, char *s, unsigned int hash)
 298 {
 299   struct stringi_set_node *node = xmalloc (sizeof *node);
 300   node->string = s;
 301   hmap_insert (&set->hmap, &node->hmap_node, hash);
 302 }
 303
 304 static bool
 305 stringi_set_delete__ (struct stringi_set *set, const char *s,
 306                       unsigned int hash)
 307 {
 308   struct stringi_set_node *node = stringi_set_find_node__ (set, s, hash);
 309   if (node != NULL)
 310     {
 311       stringi_set_delete_node (set, node);
 312       return true;
 313     }
 314   else
 315     return false;
 316 }