summaryrefslogtreecommitdiff
path: root/lib/gl_anytreehash_list1.h
blob: d3b8a0623481ebf60c4d89f84b0e40b2fdfc9da8 (plain)
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
/* Sequential list data type implemented by a hash table with a binary tree.
   Copyright (C) 2006-2007, 2009-2011 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2006.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program 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 General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

/* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c.  */

/* Hash table entry representing the same value at more than one position.  */
struct gl_multiple_nodes
{
  struct gl_hash_entry h;           /* hash table entry fields; must be first */
  void *magic;                      /* used to distinguish from single node */
  gl_oset_t nodes;                  /* set of nodes, sorted by position */
};
/* A value that cannot occur at the corresponding field (->left) in
   gl_list_node_impl.  */
#define MULTIPLE_NODES_MAGIC  (void *) -1

/* Resize the hash table if needed, after list->count was incremented.  */
static inline void
hash_resize_after_add (gl_list_t list)
{
  size_t count = (list->root != 0 ? list->root->branch_size : 0);
  size_t estimate = xsum (count, count / 2); /* 1.5 * count */
  if (estimate > list->table_size)
    hash_resize (list, estimate);
}

/* Return the position of the given node in the tree.  */
static size_t
node_position (gl_list_node_t node)
{
  size_t position = 0;

  if (node->left != NULL)
    position += node->left->branch_size;
  for (;;)
    {
      gl_list_node_t parent = node->parent;

      if (parent == NULL)
        return position;
      /* position is now relative to the subtree of node.  */
      if (parent->right == node)
        {
          position += 1;
          if (parent->left != NULL)
            position += parent->left->branch_size;
        }
      /* position is now relative to the subtree of parent.  */
      node = parent;
    }
}

/* Compares two nodes by their position in the tree.  */
static int
compare_by_position (const void *x1, const void *x2)
{
  gl_list_node_t node1 = (gl_list_node_t) x1;
  gl_list_node_t node2 = (gl_list_node_t) x2;
  size_t position1 = node_position (node1);
  size_t position2 = node_position (node2);

  return (position1 > position2 ? 1 :
          position1 < position2 ? -1 : 0);
}

/* Compares a node's position in the tree with a given threshold.  */
static bool
compare_position_threshold (const void *x, const void *threshold)
{
  gl_list_node_t node = (gl_list_node_t) x;
  size_t position = node_position (node);
  return (position >= (uintptr_t)threshold);
}

/* Return the first element of a non-empty ordered set of nodes.  */
static inline gl_list_node_t
gl_oset_first (gl_oset_t set)
{
  gl_oset_iterator_t iter = gl_oset_iterator (set);
  const void *first;

  if (!gl_oset_iterator_next (&iter, &first))
    abort ();
  gl_oset_iterator_free (&iter);
  return (gl_list_node_t) first;
}

/* Add a node to the hash table structure.
   If duplicates are allowed, this function performs in average time
   O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set
   of size O(n), needing O(log n) comparison function calls.  The comparison
   function is compare_by_position, which is O(log n) worst-case.
   If duplicates are forbidden, this function is O(1).
   Return 0 upon success, -1 upon out-of-memory.  */
static int
add_to_bucket (gl_list_t list, gl_list_node_t new_node)
{
  size_t bucket = new_node->h.hashcode % list->table_size;

  /* If no duplicates are allowed, multiple nodes are not needed.  */
  if (list->base.allow_duplicates)
    {
      size_t hashcode = new_node->h.hashcode;
      const void *value = new_node->value;
      gl_listelement_equals_fn equals = list->base.equals_fn;
      gl_hash_entry_t *entryp;

      for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next)
        {
          gl_hash_entry_t entry = *entryp;

          if (entry->hashcode == hashcode)
            {
              if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
                {
                  /* An entry representing multiple nodes.  */
                  gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
                  /* Only the first node is interesting.  */
                  gl_list_node_t node = gl_oset_first (nodes);
                  if (equals != NULL ? equals (value, node->value) : value == node->value)
                    {
                      /* Found already multiple nodes with the same value.
                         Add the new_node to it.  */
                      return gl_oset_nx_add (nodes, new_node);
                    }
                }
              else
                {
                  /* An entry representing a single node.  */
                  gl_list_node_t node = (struct gl_list_node_impl *) entry;
                  if (equals != NULL ? equals (value, node->value) : value == node->value)
                    {
                      /* Found already a node with the same value.  Turn it
                         into an ordered set, and add new_node to it.  */
                      gl_oset_t nodes;
                      struct gl_multiple_nodes *multi_entry;

                      nodes =
                        gl_oset_nx_create_empty (OSET_TREE_FLAVOR,
                                                 compare_by_position, NULL);
                      if (nodes == NULL)
                        return -1;

                      if (gl_oset_nx_add (nodes, node) < 0)
                        goto fail;
                      if (gl_oset_nx_add (nodes, new_node) < 0)
                        goto fail;

                      multi_entry =
                       (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes));
                      if (multi_entry == NULL)
                        goto fail;
                      multi_entry->h.hash_next = entry->hash_next;
                      multi_entry->h.hashcode = entry->hashcode;
                      multi_entry->magic = MULTIPLE_NODES_MAGIC;
                      multi_entry->nodes = nodes;
                      *entryp = &multi_entry->h;
                      return 0;

                    fail:
                      gl_oset_free (nodes);
                      return -1;
                    }
                }
            }
        }
    }
  /* If no duplicates are allowed, multiple nodes are not needed.  */
  new_node->h.hash_next = list->table[bucket];
  list->table[bucket] = &new_node->h;
  return 0;
}
/* Tell GCC that the likely return value is 0.  */
#if __GNUC__ >= 3
# define add_to_bucket(list,node) \
    __builtin_expect ((add_to_bucket) (list, node), 0)
#endif

/* Remove a node from the hash table structure.
   If duplicates are allowed, this function performs in average time
   O((log n)^2): gl_oset_remove may need to remove an element from an ordered
   set of size O(n), needing O(log n) comparison function calls.  The
   comparison function is compare_by_position, which is O(log n) worst-case.
   If duplicates are forbidden, this function is O(1) on average.  */
static void
remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
{
  size_t bucket = old_node->h.hashcode % list->table_size;

  if (list->base.allow_duplicates)
    {
      size_t hashcode = old_node->h.hashcode;
      const void *value = old_node->value;
      gl_listelement_equals_fn equals = list->base.equals_fn;
      gl_hash_entry_t *entryp;

      for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
        {
          gl_hash_entry_t entry = *entryp;

          if (entry == &old_node->h)
            {
              /* Found old_node as a single node in the bucket.  Remove it.  */
              *entryp = old_node->h.hash_next;
              break;
            }
          if (entry == NULL)
            /* node is not in the right bucket.  Did the hash codes
               change inadvertently?  */
            abort ();
          if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
              && entry->hashcode == hashcode)
            {
              /* An entry representing multiple nodes.  */
              gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
              /* Only the first node is interesting.  */
              gl_list_node_t node = gl_oset_first (nodes);
              if (equals != NULL ? equals (value, node->value) : value == node->value)
                {
                  /* Found multiple nodes with the same value.
                     old_node must be one of them.  Remove it.  */
                  if (!gl_oset_remove (nodes, old_node))
                    abort ();
                  if (gl_oset_size (nodes) == 1)
                    {
                      /* Replace a one-element set with a single node.  */
                      node = gl_oset_first (nodes);
                      node->h.hash_next = entry->hash_next;
                      *entryp = &node->h;
                      gl_oset_free (nodes);
                      free (entry);
                    }
                  break;
                }
            }
        }
    }
  else
    {
      /* If no duplicates are allowed, multiple nodes are not needed.  */
      gl_hash_entry_t *entryp;

      for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
        {
          if (*entryp == &old_node->h)
            {
              *entryp = old_node->h.hash_next;
              break;
            }
          if (*entryp == NULL)
            /* node is not in the right bucket.  Did the hash codes
               change inadvertently?  */
            abort ();
        }
    }
}

/* Build up the hash table during initialization: Store all the nodes of
   list->root in the hash table.
   Return 0 upon success, -1 upon out-of-memory.  */
static inline int
add_nodes_to_buckets (gl_list_t list)
{
  /* Iterate across all nodes.  */
  gl_list_node_t node = list->root;
  iterstack_t stack;
  iterstack_item_t *stack_ptr = &stack[0];

  for (;;)
    {
      /* Descend on left branch.  */
      for (;;)
        {
          if (node == NULL)
            break;
          stack_ptr->node = node;
          stack_ptr->rightp = false;
          node = node->left;
          stack_ptr++;
        }
      /* Climb up again.  */
      for (;;)
        {
          if (stack_ptr == &stack[0])
            goto done;
          stack_ptr--;
          if (!stack_ptr->rightp)
            break;
        }
      node = stack_ptr->node;
      /* Add the current node to the hash table.  */
      node->h.hashcode =
        (list->base.hashcode_fn != NULL
         ? list->base.hashcode_fn (node->value)
         : (size_t)(uintptr_t) node->value);
      if (add_to_bucket (list, node) < 0)
        goto fail;
      /* Descend on right branch.  */
      stack_ptr->rightp = true;
      node = node->right;
      stack_ptr++;
    }
 done:
  return 0;

 fail:
  /* Undo everything.  */
  for (;;)
    {
      /* Descend on left branch.  */
      stack_ptr->rightp = false;
      node = node->left;
      stack_ptr++;
      /* Descend on right branch.  */
      for (;;)
        {
          if (node == NULL)
            break;
          stack_ptr->node = node;
          stack_ptr->rightp = true;
          node = node->right;
          stack_ptr++;
        }
      /* Climb up again.  */
      for (;;)
        {
          if (stack_ptr == &stack[0])
            goto fail_done;
          stack_ptr--;
          if (stack_ptr->rightp)
            break;
        }
      node = stack_ptr->node;
      /* Remove the current node from the hash table.  */
      remove_from_bucket (list, node);
    }
 fail_done:
  return -1;
}
/* Tell GCC that the likely return value is 0.  */
#if __GNUC__ >= 3
# define add_nodes_to_buckets(list) \
    __builtin_expect ((add_nodes_to_buckets) (list), 0)
#endif