lib/struniq.h

   1 /* Define a file-local string uniquification function.
   2    Copyright (C) 2009-2024 Free Software Foundation, Inc.
   3
   4    This file is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU Lesser General Public License as
   6    published by the Free Software Foundation; either version 2.1 of the
   7    License, or (at your option) any later version.
   8
   9    This file 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 Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Bruno Haible <bruno@clisp.org>, 2009.  */
  18
  19
  20 /* This file needs the following includes:
  21
  22      #include <limits.h>
  23      #include <stdlib.h>
  24      #include <string.h>
  25      #include "flexmember.h"
  26      #include "glthread/lock.h"
  27      #include "thread-optim.h"
  28
  29    and the following gnulib modules as dependencies:
  30
  31      flexmember
  32      lock
  33      stdbool
  34      thread-optim
  35  */
  36
  37
  38 /* Simple hash set of strings.  We don't want to drag in lots of hash table
  39    code here.  */
  40
  41 #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
  42
  43 /* A hash function for NUL-terminated char* strings using
  44    the method described by Bruno Haible.
  45    See https://www.haible.de/bruno/hashfunc.html.  */
  46 static size_t _GL_ATTRIBUTE_PURE
  47 string_hash (const void *x)
  48 {
  49   const char *s = (const char *) x;
  50   size_t h = 0;
  51
  52   for (; *s; s++)
  53     h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
  54
  55   return h;
  56 }
  57
  58 /* A hash table of fixed size.  Multiple threads can access it read-only
  59    simultaneously, but only one thread can insert into it at the same time.  */
  60
  61 /* A node in a hash bucket collision list.  */
  62 struct struniq_hash_node
  63   {
  64     struct struniq_hash_node * volatile next;
  65     char contents[FLEXIBLE_ARRAY_MEMBER];
  66   };
  67
  68 #define STRUNIQ_HASH_TABLE_SIZE 257
  69 static struct struniq_hash_node * volatile struniq_hash_table[STRUNIQ_HASH_TABLE_SIZE]
  70   /* = { NULL, ..., NULL } */;
  71
  72 /* This lock protects the struniq_hash_table against multiple simultaneous
  73    insertions.  */
  74 gl_lock_define_initialized(static, struniq_lock)
  75
  76 /* Store a copy of the given string in a string pool with indefinite extent.
  77    Return a pointer to this copy.  */
  78 static const char *
  79 struniq (const char *string)
  80 {
  81   size_t hashcode = string_hash (string);
  82   size_t slot = hashcode % STRUNIQ_HASH_TABLE_SIZE;
  83   size_t size;
  84   struct struniq_hash_node *new_node;
  85   struct struniq_hash_node *p;
  86   for (p = struniq_hash_table[slot]; p != NULL; p = p->next)
  87     if (strcmp (p->contents, string) == 0)
  88       return p->contents;
  89   size = strlen (string) + 1;
  90   new_node =
  91     (struct struniq_hash_node *)
  92     malloc (FLEXSIZEOF (struct struniq_hash_node, contents, size));
  93   if (new_node == NULL)
  94     /* Out of memory.  Return a statically allocated string.  */
  95     return "C";
  96   memcpy (new_node->contents, string, size);
  97   {
  98     bool mt = gl_multithreaded ();
  99     /* Lock while inserting new_node.  */
 100     if (mt) gl_lock_lock (struniq_lock);
 101     /* Check whether another thread already added the string while we were
 102        waiting on the lock.  */
 103     for (p = struniq_hash_table[slot]; p != NULL; p = p->next)
 104       if (strcmp (p->contents, string) == 0)
 105         {
 106           free (new_node);
 107           new_node = p;
 108           goto done;
 109         }
 110     /* Really insert new_node into the hash table.  Fill new_node entirely
 111        first, because other threads may be iterating over the linked list.  */
 112     new_node->next = struniq_hash_table[slot];
 113     struniq_hash_table[slot] = new_node;
 114    done:
 115     /* Unlock after new_node is inserted.  */
 116     if (mt) gl_lock_unlock (struniq_lock);
 117   }
 118   return new_node->contents;
 119 }