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