src/libpspp/stringi-set.c

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