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