src/libpspp/string-set.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2009, 2011 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    string-set-test.c. */
  19
  20 #include <config.h>
  21
  22 #include "libpspp/string-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 string_set_node *string_set_find_node__ (
  32   const struct string_set *, const char *, unsigned int hash);
  33 static void string_set_insert__ (struct string_set *, char *,
  34                                  unsigned int hash);
  35 static bool string_set_delete__ (struct string_set *, const char *,
  36                                  unsigned int hash);
  37
  38 /* Initializes SET as a new string set that is initially empty. */
  39 void
  40 string_set_init (struct string_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 string_set_clone (struct string_set *set, const struct string_set *old)
  49 {
  50   const struct string_set_node *node;
  51   const char *s;
  52
  53   string_set_init (set);
  54   hmap_reserve (&set->hmap, string_set_count (old));
  55   STRING_SET_FOR_EACH (s, node, old)
  56     string_set_insert__ (set, xstrdup (s), node->hmap_node.hash);
  57 }
  58
  59 /* Exchanges the contents of string sets A and B. */
  60 void
  61 string_set_swap (struct string_set *a, struct string_set *b)
  62 {
  63   hmap_swap (&a->hmap, &b->hmap);
  64 }
  65
  66 /* Frees SET and its nodes and strings. */
  67 void
  68 string_set_destroy (struct string_set *set)
  69 {
  70   if (set != NULL)
  71     {
  72       string_set_clear (set);
  73       hmap_destroy (&set->hmap);
  74     }
  75 }
  76
  77 /* Returns true if SET contains S, false otherwise. */
  78 bool
  79 string_set_contains (const struct string_set *set, const char *s)
  80 {
  81   return string_set_find_node (set, s) != NULL;
  82 }
  83
  84 /* Returns the node in SET that contains S, or a null pointer if SET does not
  85    contain S. */
  86 struct string_set_node *
  87 string_set_find_node (const struct string_set *set, const char *s)
  88 {
  89   return string_set_find_node__ (set, s, hash_string (s, 0));
  90 }
  91
  92 /* Inserts a copy of S into SET.  Returns true if successful, false if SET
  93    is unchanged because it already contained S. */
  94 bool
  95 string_set_insert (struct string_set *set, const char *s)
  96 {
  97   unsigned int hash = hash_string (s, 0);
  98   if (!string_set_find_node__ (set, s, hash))
  99     {
 100       string_set_insert__ (set, xstrdup (s), hash);
 101       return true;
 102     }
 103   else
 104     return false;
 105 }
 106
 107 /* Inserts S, which must be a malloc'd string, into SET, transferring ownership
 108    of S to SET.  Returns true if successful, false if SET is unchanged because
 109    it already contained a copy of S.  (In the latter case, S is freed.) */
 110 bool
 111 string_set_insert_nocopy (struct string_set *set, char *s)
 112 {
 113   unsigned int hash = hash_string (s, 0);
 114   if (!string_set_find_node__ (set, s, hash))
 115     {
 116       string_set_insert__ (set, s, hash);
 117       return true;
 118     }
 119   else
 120     {
 121       free (s);
 122       return false;
 123     }
 124 }
 125
 126 /* Deletes S from SET.  Returns true if successful, false if SET is unchanged
 127    because it did not contain a copy of S. */
 128 bool
 129 string_set_delete (struct string_set *set, const char *s)
 130 {
 131   return string_set_delete__ (set, s, hash_string (s, 0));
 132 }
 133
 134 /* Deletes NODE from SET, and frees NODE and its string. */
 135 void
 136 string_set_delete_node (struct string_set *set, struct string_set_node *node)
 137 {
 138   free (string_set_delete_nofree (set, node));
 139 }
 140
 141 /* Deletes NODE from SET and frees NODE.  Returns the string that NODE
 142    contained, transferring ownership to the caller. */
 143 char *
 144 string_set_delete_nofree (struct string_set *set, struct string_set_node *node)
 145 {
 146   char *string = node->string;
 147   hmap_delete (&set->hmap, &node->hmap_node);
 148   free (node);
 149   return string;
 150 }
 151
 152 /* Removes all nodes from SET. */
 153 void
 154 string_set_clear (struct string_set *set)
 155 {
 156   struct string_set_node *node, *next;
 157
 158   HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
 159                       &set->hmap)
 160     string_set_delete_node (set, node);
 161 }
 162
 163 /* Calculates A = union(A, B).
 164
 165    If B may be modified, string_set_union_and_intersection() is
 166    faster than this function. */
 167 void
 168 string_set_union (struct string_set *a, const struct string_set *b)
 169 {
 170   struct string_set_node *node;
 171   HMAP_FOR_EACH (node, struct string_set_node, hmap_node, &b->hmap)
 172     if (!string_set_find_node__ (a, node->string, node->hmap_node.hash))
 173       string_set_insert__ (a, xstrdup (node->string), node->hmap_node.hash);
 174 }
 175
 176 /* Calculates A = union(A, B) and B = intersect(A, B).
 177
 178    If only the intersection is needed, string_set_intersect() is
 179    faster. */
 180 void
 181 string_set_union_and_intersection (struct string_set *a, struct string_set *b)
 182 {
 183   struct string_set_node *node, *next;
 184
 185   HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
 186                       &b->hmap)
 187     if (!string_set_find_node__ (a, node->string, node->hmap_node.hash))
 188       {
 189         hmap_delete (&b->hmap, &node->hmap_node);
 190         hmap_insert (&a->hmap, &node->hmap_node, node->hmap_node.hash);
 191       }
 192 }
 193
 194 /* Calculates A = intersect(A, B). */
 195 void
 196 string_set_intersect (struct string_set *a, const struct string_set *b)
 197 {
 198   struct string_set_node *node, *next;
 199
 200   HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
 201                       &a->hmap)
 202     if (!string_set_find_node__ (b, node->string, node->hmap_node.hash))
 203       string_set_delete_node (a, node);
 204 }
 205
 206 /* Removes from A all of the strings in B. */
 207 void
 208 string_set_subtract (struct string_set *a, const struct string_set *b)
 209 {
 210   struct string_set_node *node, *next;
 211
 212   if (string_set_count (a) < string_set_count (b))
 213     {
 214       HMAP_FOR_EACH_SAFE (node, next, struct string_set_node, hmap_node,
 215                           &a->hmap)
 216         if (string_set_find_node__ (b, node->string, node->hmap_node.hash))
 217           string_set_delete_node (a, node);
 218     }
 219   else
 220     {
 221       HMAP_FOR_EACH (node, struct string_set_node, hmap_node, &b->hmap)
 222         string_set_delete__ (a, node->string, node->hmap_node.hash);
 223     }
 224 }
 225 \f
 226 /* Internal functions. */
 227
 228 static struct string_set_node *
 229 string_set_find_node__ (const struct string_set *set, const char *s,
 230                         unsigned int hash)
 231 {
 232   struct string_set_node *node;
 233
 234   HMAP_FOR_EACH_WITH_HASH (node, struct string_set_node, hmap_node,
 235                            hash, &set->hmap)
 236     if (!strcmp (s, node->string))
 237       return node;
 238
 239   return NULL;
 240 }
 241
 242 static void
 243 string_set_insert__ (struct string_set *set, char *s, unsigned int hash)
 244 {
 245   struct string_set_node *node = xmalloc (sizeof *node);
 246   node->string = s;
 247   hmap_insert (&set->hmap, &node->hmap_node, hash);
 248 }
 249
 250 static bool
 251 string_set_delete__ (struct string_set *set, const char *s, unsigned int hash)
 252 {
 253   struct string_set_node *node = string_set_find_node__ (set, s, hash);
 254   if (node != NULL)
 255     {
 256       string_set_delete_node (set, node);
 257       return true;
 258     }
 259   else
 260     return false;
 261 }