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