Coverage Report

Created: 2025-03-06 07:58

/src/gnutls/gl/gl_anylinked_list2.h
Line
Count
Source (jump to first uncovered line)
1
/* Sequential list data type implemented by a linked list.
2
   Copyright (C) 2006-2025 Free Software Foundation, Inc.
3
   Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5
   This file is free software: you can redistribute it and/or modify
6
   it under the terms of the GNU Lesser General Public License as
7
   published by the Free Software Foundation; either version 2.1 of the
8
   License, or (at your option) any later version.
9
10
   This file is distributed in the hope that it will be useful,
11
   but WITHOUT ANY WARRANTY; without even the implied warranty of
12
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
   GNU Lesser General Public License for more details.
14
15
   You should have received a copy of the GNU Lesser General Public License
16
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
17
18
/* Common code of gl_linked_list.c and gl_linkedhash_list.c.  */
19
20
/* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
21
   a way that a gl_list_t data structure may be used from within a signal
22
   handler.  The operations allowed in the signal handler are:
23
     gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
24
   The list and node fields that are therefore accessed from the signal handler
25
   are:
26
     list->root, node->next, node->value.
27
   We are careful to make modifications to these fields only in an order
28
   that maintains the consistency of the list data structure at any moment,
29
   and we use 'volatile' assignments to prevent the compiler from reordering
30
   such assignments.  */
31
#ifdef SIGNAL_SAFE_LIST
32
# define ASYNCSAFE(type) *(type volatile *)&
33
#else
34
# define ASYNCSAFE(type)
35
#endif
36
37
/* -------------------------- gl_list_t Data Type -------------------------- */
38
39
static gl_list_t
40
gl_linked_nx_create_empty (gl_list_implementation_t implementation,
41
                           gl_listelement_equals_fn equals_fn,
42
                           gl_listelement_hashcode_fn hashcode_fn,
43
                           gl_listelement_dispose_fn dispose_fn,
44
                           bool allow_duplicates)
45
20
{
46
20
  struct gl_list_impl *list =
47
20
    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
48
49
20
  if (list == NULL)
50
0
    return NULL;
51
52
20
  list->base.vtable = implementation;
53
20
  list->base.equals_fn = equals_fn;
54
20
  list->base.hashcode_fn = hashcode_fn;
55
20
  list->base.dispose_fn = dispose_fn;
56
20
  list->base.allow_duplicates = allow_duplicates;
57
20
#if WITH_HASHTABLE
58
20
  list->table_size = 11;
59
20
  list->table =
60
20
    (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
61
20
  if (list->table == NULL)
62
0
    goto fail;
63
20
#endif
64
20
  list->root.next = &list->root;
65
20
  list->root.prev = &list->root;
66
20
  list->count = 0;
67
68
20
  return list;
69
70
0
#if WITH_HASHTABLE
71
0
 fail:
72
0
  free (list);
73
0
  return NULL;
74
20
#endif
75
20
}
76
77
static gl_list_t
78
gl_linked_nx_create (gl_list_implementation_t implementation,
79
                     gl_listelement_equals_fn equals_fn,
80
                     gl_listelement_hashcode_fn hashcode_fn,
81
                     gl_listelement_dispose_fn dispose_fn,
82
                     bool allow_duplicates,
83
                     size_t count, const void **contents)
84
0
{
85
0
  struct gl_list_impl *list =
86
0
    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
87
0
  gl_list_node_t tail;
88
89
0
  if (list == NULL)
90
0
    return NULL;
91
92
0
  list->base.vtable = implementation;
93
0
  list->base.equals_fn = equals_fn;
94
0
  list->base.hashcode_fn = hashcode_fn;
95
0
  list->base.dispose_fn = dispose_fn;
96
0
  list->base.allow_duplicates = allow_duplicates;
97
0
#if WITH_HASHTABLE
98
0
  {
99
0
    size_t estimate = xsum (count, count / 2); /* 1.5 * count */
100
0
    if (estimate < 10)
101
0
      estimate = 10;
102
0
    list->table_size = next_prime (estimate);
103
0
    if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
104
0
      goto fail1;
105
0
    list->table =
106
0
      (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
107
0
    if (list->table == NULL)
108
0
      goto fail1;
109
0
  }
110
0
#endif
111
0
  list->count = count;
112
0
  tail = &list->root;
113
0
  for (; count > 0; contents++, count--)
114
0
    {
115
0
      gl_list_node_t node =
116
0
        (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
117
118
0
      if (node == NULL)
119
0
        goto fail2;
120
121
0
      node->value = *contents;
122
0
#if WITH_HASHTABLE
123
0
      node->h.hashcode =
124
0
        (list->base.hashcode_fn != NULL
125
0
         ? list->base.hashcode_fn (node->value)
126
0
         : (size_t)(uintptr_t) node->value);
127
128
      /* Add node to the hash table.  */
129
0
      if (add_to_bucket (list, node) < 0)
130
0
        {
131
0
          free (node);
132
0
          goto fail2;
133
0
        }
134
0
#endif
135
136
      /* Add node to the list.  */
137
0
      node->prev = tail;
138
0
      tail->next = node;
139
0
      tail = node;
140
0
    }
141
0
  tail->next = &list->root;
142
0
  list->root.prev = tail;
143
144
0
  return list;
145
146
0
 fail2:
147
0
  {
148
0
    gl_list_node_t node;
149
150
0
    for (node = tail; node != &list->root; )
151
0
      {
152
0
        gl_list_node_t prev = node->prev;
153
154
0
        free (node);
155
0
        node = prev;
156
0
      }
157
0
  }
158
0
#if WITH_HASHTABLE
159
0
  free (list->table);
160
0
 fail1:
161
0
#endif
162
0
  free (list);
163
0
  return NULL;
164
0
}
165
166
static size_t _GL_ATTRIBUTE_PURE
167
gl_linked_size (gl_list_t list)
168
0
{
169
0
  return list->count;
170
0
}
171
172
static const void * _GL_ATTRIBUTE_PURE
173
gl_linked_node_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
174
                      gl_list_node_t node)
175
0
{
176
0
  return node->value;
177
0
}
178
179
static int
180
gl_linked_node_nx_set_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
181
                             gl_list_node_t node,
182
                             const void *elt)
183
0
{
184
0
#if WITH_HASHTABLE
185
0
  if (elt != node->value)
186
0
    {
187
0
      size_t new_hashcode =
188
0
        (list->base.hashcode_fn != NULL
189
0
         ? list->base.hashcode_fn (elt)
190
0
         : (size_t)(uintptr_t) elt);
191
192
0
      if (new_hashcode != node->h.hashcode)
193
0
        {
194
0
          remove_from_bucket (list, node);
195
0
          node->value = elt;
196
0
          node->h.hashcode = new_hashcode;
197
0
          if (add_to_bucket (list, node) < 0)
198
0
            {
199
              /* Out of memory.  We removed node from a bucket but cannot add
200
                 it to another bucket.  In order to avoid inconsistencies, we
201
                 must remove node entirely from the list.  */
202
0
              gl_list_node_t before_removed = node->prev;
203
0
              gl_list_node_t after_removed = node->next;
204
0
              ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
205
0
              after_removed->prev = before_removed;
206
0
              list->count--;
207
0
              free (node);
208
0
              return -1;
209
0
            }
210
0
        }
211
0
      else
212
0
        node->value = elt;
213
0
    }
214
#else
215
  node->value = elt;
216
#endif
217
0
  return 0;
218
0
}
219
220
static gl_list_node_t _GL_ATTRIBUTE_PURE
221
gl_linked_next_node (gl_list_t list, gl_list_node_t node)
222
0
{
223
0
  return (node->next != &list->root ? node->next : NULL);
224
0
}
225
226
static gl_list_node_t _GL_ATTRIBUTE_PURE
227
gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
228
0
{
229
0
  return (node->prev != &list->root ? node->prev : NULL);
230
0
}
231
232
static gl_list_node_t _GL_ATTRIBUTE_PURE
233
gl_linked_first_node (gl_list_t list)
234
0
{
235
0
  if (list->count > 0)
236
0
    return list->root.next;
237
0
  else
238
0
    return NULL;
239
0
}
240
241
static gl_list_node_t _GL_ATTRIBUTE_PURE
242
gl_linked_last_node (gl_list_t list)
243
0
{
244
0
  if (list->count > 0)
245
0
    return list->root.prev;
246
0
  else
247
0
    return NULL;
248
0
}
249
250
static const void * _GL_ATTRIBUTE_PURE
251
gl_linked_get_at (gl_list_t list, size_t position)
252
0
{
253
0
  size_t count = list->count;
254
0
  gl_list_node_t node;
255
256
0
  if (!(position < count))
257
    /* Invalid argument.  */
258
0
    abort ();
259
  /* Here we know count > 0.  */
260
0
  if (position <= ((count - 1) / 2))
261
0
    {
262
0
      node = list->root.next;
263
0
      for (; position > 0; position--)
264
0
        node = node->next;
265
0
    }
266
0
  else
267
0
    {
268
0
      position = count - 1 - position;
269
0
      node = list->root.prev;
270
0
      for (; position > 0; position--)
271
0
        node = node->prev;
272
0
    }
273
0
  return node->value;
274
0
}
275
276
static gl_list_node_t
277
gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt)
278
0
{
279
0
  size_t count = list->count;
280
0
  gl_list_node_t node;
281
282
0
  if (!(position < count))
283
    /* Invalid argument.  */
284
0
    abort ();
285
  /* Here we know count > 0.  */
286
0
  if (position <= ((count - 1) / 2))
287
0
    {
288
0
      node = list->root.next;
289
0
      for (; position > 0; position--)
290
0
        node = node->next;
291
0
    }
292
0
  else
293
0
    {
294
0
      position = count - 1 - position;
295
0
      node = list->root.prev;
296
0
      for (; position > 0; position--)
297
0
        node = node->prev;
298
0
    }
299
0
#if WITH_HASHTABLE
300
0
  if (elt != node->value)
301
0
    {
302
0
      size_t new_hashcode =
303
0
        (list->base.hashcode_fn != NULL
304
0
         ? list->base.hashcode_fn (elt)
305
0
         : (size_t)(uintptr_t) elt);
306
307
0
      if (new_hashcode != node->h.hashcode)
308
0
        {
309
0
          remove_from_bucket (list, node);
310
0
          node->value = elt;
311
0
          node->h.hashcode = new_hashcode;
312
0
          if (add_to_bucket (list, node) < 0)
313
0
            {
314
              /* Out of memory.  We removed node from a bucket but cannot add
315
                 it to another bucket.  In order to avoid inconsistencies, we
316
                 must remove node entirely from the list.  */
317
0
              gl_list_node_t before_removed = node->prev;
318
0
              gl_list_node_t after_removed = node->next;
319
0
              ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
320
0
              after_removed->prev = before_removed;
321
0
              list->count--;
322
0
              free (node);
323
0
              return NULL;
324
0
            }
325
0
        }
326
0
      else
327
0
        node->value = elt;
328
0
    }
329
#else
330
  node->value = elt;
331
#endif
332
0
  return node;
333
0
}
334
335
static gl_list_node_t _GL_ATTRIBUTE_PURE
336
gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
337
                          const void *elt)
338
0
{
339
0
  size_t count = list->count;
340
341
0
  if (!(start_index <= end_index && end_index <= count))
342
    /* Invalid arguments.  */
343
0
    abort ();
344
0
  {
345
0
#if WITH_HASHTABLE
346
0
    size_t hashcode =
347
0
      (list->base.hashcode_fn != NULL
348
0
       ? list->base.hashcode_fn (elt)
349
0
       : (size_t)(uintptr_t) elt);
350
0
    size_t bucket = hashcode % list->table_size;
351
0
    gl_listelement_equals_fn equals = list->base.equals_fn;
352
353
0
    if (!list->base.allow_duplicates)
354
0
      {
355
        /* Look for the first match in the hash bucket.  */
356
0
        gl_list_node_t found = NULL;
357
0
        gl_list_node_t node;
358
359
0
        for (node = (gl_list_node_t) list->table[bucket];
360
0
             node != NULL;
361
0
             node = (gl_list_node_t) node->h.hash_next)
362
0
          if (node->h.hashcode == hashcode
363
0
              && (equals != NULL
364
0
                  ? equals (elt, node->value)
365
0
                  : elt == node->value))
366
0
            {
367
0
              found = node;
368
0
              break;
369
0
            }
370
0
        if (start_index > 0)
371
          /* Look whether found's index is < start_index.  */
372
0
          for (node = list->root.next; ; node = node->next)
373
0
            {
374
0
              if (node == found)
375
0
                return NULL;
376
0
              if (--start_index == 0)
377
0
                break;
378
0
            }
379
0
        if (end_index < count)
380
          /* Look whether found's index is >= end_index.  */
381
0
          {
382
0
            end_index = count - end_index;
383
0
            for (node = list->root.prev; ; node = node->prev)
384
0
              {
385
0
                if (node == found)
386
0
                  return NULL;
387
0
                if (--end_index == 0)
388
0
                  break;
389
0
              }
390
0
          }
391
0
        return found;
392
0
      }
393
0
    else
394
0
      {
395
        /* Look whether there is more than one match in the hash bucket.  */
396
0
        bool multiple_matches = false;
397
0
        gl_list_node_t first_match = NULL;
398
0
        gl_list_node_t node;
399
400
0
        for (node = (gl_list_node_t) list->table[bucket];
401
0
             node != NULL;
402
0
             node = (gl_list_node_t) node->h.hash_next)
403
0
          if (node->h.hashcode == hashcode
404
0
              && (equals != NULL
405
0
                  ? equals (elt, node->value)
406
0
                  : elt == node->value))
407
0
            {
408
0
              if (first_match == NULL)
409
0
                first_match = node;
410
0
              else
411
0
                {
412
0
                  multiple_matches = true;
413
0
                  break;
414
0
                }
415
0
            }
416
0
        if (multiple_matches)
417
0
          {
418
            /* We need the match with the smallest index.  But we don't have
419
               a fast mapping node -> index.  So we have to walk the list.  */
420
0
            end_index -= start_index;
421
0
            node = list->root.next;
422
0
            for (; start_index > 0; start_index--)
423
0
              node = node->next;
424
425
0
            for (;
426
0
                 end_index > 0;
427
0
                 node = node->next, end_index--)
428
0
              if (node->h.hashcode == hashcode
429
0
                  && (equals != NULL
430
0
                      ? equals (elt, node->value)
431
0
                      : elt == node->value))
432
0
                return node;
433
            /* The matches must have all been at indices < start_index or
434
               >= end_index.  */
435
0
            return NULL;
436
0
          }
437
0
        else
438
0
          {
439
0
            if (start_index > 0)
440
              /* Look whether first_match's index is < start_index.  */
441
0
              for (node = list->root.next; node != &list->root; node = node->next)
442
0
                {
443
0
                  if (node == first_match)
444
0
                    return NULL;
445
0
                  if (--start_index == 0)
446
0
                    break;
447
0
                }
448
0
            if (end_index < list->count)
449
              /* Look whether first_match's index is >= end_index.  */
450
0
              {
451
0
                end_index = list->count - end_index;
452
0
                for (node = list->root.prev; ; node = node->prev)
453
0
                  {
454
0
                    if (node == first_match)
455
0
                      return NULL;
456
0
                    if (--end_index == 0)
457
0
                      break;
458
0
                  }
459
0
              }
460
0
            return first_match;
461
0
          }
462
0
      }
463
#else
464
    gl_listelement_equals_fn equals = list->base.equals_fn;
465
    gl_list_node_t node = list->root.next;
466
467
    end_index -= start_index;
468
    for (; start_index > 0; start_index--)
469
      node = node->next;
470
471
    if (equals != NULL)
472
      {
473
        for (; end_index > 0; node = node->next, end_index--)
474
          if (equals (elt, node->value))
475
            return node;
476
      }
477
    else
478
      {
479
        for (; end_index > 0; node = node->next, end_index--)
480
          if (elt == node->value)
481
            return node;
482
      }
483
    return NULL;
484
#endif
485
0
  }
486
0
}
487
488
static size_t _GL_ATTRIBUTE_PURE
489
gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
490
                           const void *elt)
491
0
{
492
0
  size_t count = list->count;
493
494
0
  if (!(start_index <= end_index && end_index <= count))
495
    /* Invalid arguments.  */
496
0
    abort ();
497
0
  {
498
0
#if WITH_HASHTABLE
499
    /* Here the hash table doesn't help much.  It only allows us to minimize
500
       the number of equals() calls, by looking up first the node and then
501
       its index.  */
502
0
    size_t hashcode =
503
0
      (list->base.hashcode_fn != NULL
504
0
       ? list->base.hashcode_fn (elt)
505
0
       : (size_t)(uintptr_t) elt);
506
0
    size_t bucket = hashcode % list->table_size;
507
0
    gl_listelement_equals_fn equals = list->base.equals_fn;
508
0
    gl_list_node_t node;
509
510
    /* First step: Look up the node.  */
511
0
    if (!list->base.allow_duplicates)
512
0
      {
513
        /* Look for the first match in the hash bucket.  */
514
0
        for (node = (gl_list_node_t) list->table[bucket];
515
0
             node != NULL;
516
0
             node = (gl_list_node_t) node->h.hash_next)
517
0
          if (node->h.hashcode == hashcode
518
0
              && (equals != NULL
519
0
                  ? equals (elt, node->value)
520
0
                  : elt == node->value))
521
0
            break;
522
0
      }
523
0
    else
524
0
      {
525
        /* Look whether there is more than one match in the hash bucket.  */
526
0
        bool multiple_matches = false;
527
0
        gl_list_node_t first_match = NULL;
528
529
0
        for (node = (gl_list_node_t) list->table[bucket];
530
0
             node != NULL;
531
0
             node = (gl_list_node_t) node->h.hash_next)
532
0
          if (node->h.hashcode == hashcode
533
0
              && (equals != NULL
534
0
                  ? equals (elt, node->value)
535
0
                  : elt == node->value))
536
0
            {
537
0
              if (first_match == NULL)
538
0
                first_match = node;
539
0
              else
540
0
                {
541
0
                  multiple_matches = true;
542
0
                  break;
543
0
                }
544
0
            }
545
0
        if (multiple_matches)
546
0
          {
547
            /* We need the match with the smallest index.  But we don't have
548
               a fast mapping node -> index.  So we have to walk the list.  */
549
0
            size_t index;
550
551
0
            index = start_index;
552
0
            node = list->root.next;
553
0
            for (; start_index > 0; start_index--)
554
0
              node = node->next;
555
556
0
            for (;
557
0
                 index < end_index;
558
0
                 node = node->next, index++)
559
0
              if (node->h.hashcode == hashcode
560
0
                  && (equals != NULL
561
0
                      ? equals (elt, node->value)
562
0
                      : elt == node->value))
563
0
                return index;
564
            /* The matches must have all been at indices < start_index or
565
               >= end_index.  */
566
0
            return (size_t)(-1);
567
0
          }
568
0
        node = first_match;
569
0
      }
570
571
    /* Second step: Look up the index of the node.  */
572
0
    if (node == NULL)
573
0
      return (size_t)(-1);
574
0
    else
575
0
      {
576
0
        size_t index = 0;
577
578
0
        for (; node->prev != &list->root; node = node->prev)
579
0
          index++;
580
581
0
        if (index >= start_index && index < end_index)
582
0
          return index;
583
0
        else
584
0
          return (size_t)(-1);
585
0
      }
586
#else
587
    gl_listelement_equals_fn equals = list->base.equals_fn;
588
    size_t index = start_index;
589
    gl_list_node_t node = list->root.next;
590
591
    for (; start_index > 0; start_index--)
592
      node = node->next;
593
594
    if (equals != NULL)
595
      {
596
        for (;
597
             index < end_index;
598
             node = node->next, index++)
599
          if (equals (elt, node->value))
600
            return index;
601
      }
602
    else
603
      {
604
        for (;
605
             index < end_index;
606
             node = node->next, index++)
607
          if (elt == node->value)
608
            return index;
609
      }
610
    return (size_t)(-1);
611
#endif
612
0
  }
613
0
}
614
615
static gl_list_node_t
616
gl_linked_nx_add_first (gl_list_t list, const void *elt)
617
0
{
618
0
  gl_list_node_t node =
619
0
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
620
621
0
  if (node == NULL)
622
0
    return NULL;
623
624
0
  ASYNCSAFE(const void *) node->value = elt;
625
0
#if WITH_HASHTABLE
626
0
  node->h.hashcode =
627
0
    (list->base.hashcode_fn != NULL
628
0
     ? list->base.hashcode_fn (node->value)
629
0
     : (size_t)(uintptr_t) node->value);
630
631
  /* Add node to the hash table.  */
632
0
  if (add_to_bucket (list, node) < 0)
633
0
    {
634
0
      free (node);
635
0
      return NULL;
636
0
    }
637
0
#endif
638
639
  /* Add node to the list.  */
640
0
  node->prev = &list->root;
641
0
  ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
642
0
  node->next->prev = node;
643
0
  ASYNCSAFE(gl_list_node_t) list->root.next = node;
644
0
  list->count++;
645
646
0
#if WITH_HASHTABLE
647
0
  hash_resize_after_add (list);
648
0
#endif
649
650
0
  return node;
651
0
}
652
653
static gl_list_node_t
654
gl_linked_nx_add_last (gl_list_t list, const void *elt)
655
0
{
656
0
  gl_list_node_t node =
657
0
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
658
659
0
  if (node == NULL)
660
0
    return NULL;
661
662
0
  ASYNCSAFE(const void *) node->value = elt;
663
0
#if WITH_HASHTABLE
664
0
  node->h.hashcode =
665
0
    (list->base.hashcode_fn != NULL
666
0
     ? list->base.hashcode_fn (node->value)
667
0
     : (size_t)(uintptr_t) node->value);
668
669
  /* Add node to the hash table.  */
670
0
  if (add_to_bucket (list, node) < 0)
671
0
    {
672
0
      free (node);
673
0
      return NULL;
674
0
    }
675
0
#endif
676
677
  /* Add node to the list.  */
678
0
  ASYNCSAFE(gl_list_node_t) node->next = &list->root;
679
0
  node->prev = list->root.prev;
680
0
  ASYNCSAFE(gl_list_node_t) node->prev->next = node;
681
0
  list->root.prev = node;
682
0
  list->count++;
683
684
0
#if WITH_HASHTABLE
685
0
  hash_resize_after_add (list);
686
0
#endif
687
688
0
  return node;
689
0
}
690
691
static gl_list_node_t
692
gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
693
0
{
694
0
  gl_list_node_t new_node =
695
0
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
696
697
0
  if (new_node == NULL)
698
0
    return NULL;
699
700
0
  ASYNCSAFE(const void *) new_node->value = elt;
701
0
#if WITH_HASHTABLE
702
0
  new_node->h.hashcode =
703
0
    (list->base.hashcode_fn != NULL
704
0
     ? list->base.hashcode_fn (new_node->value)
705
0
     : (size_t)(uintptr_t) new_node->value);
706
707
  /* Add new_node to the hash table.  */
708
0
  if (add_to_bucket (list, new_node) < 0)
709
0
    {
710
0
      free (new_node);
711
0
      return NULL;
712
0
    }
713
0
#endif
714
715
  /* Add new_node to the list.  */
716
0
  ASYNCSAFE(gl_list_node_t) new_node->next = node;
717
0
  new_node->prev = node->prev;
718
0
  ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
719
0
  node->prev = new_node;
720
0
  list->count++;
721
722
0
#if WITH_HASHTABLE
723
0
  hash_resize_after_add (list);
724
0
#endif
725
726
0
  return new_node;
727
0
}
728
729
static gl_list_node_t
730
gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
731
0
{
732
0
  gl_list_node_t new_node =
733
0
    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
734
735
0
  if (new_node == NULL)
736
0
    return NULL;
737
738
0
  ASYNCSAFE(const void *) new_node->value = elt;
739
0
#if WITH_HASHTABLE
740
0
  new_node->h.hashcode =
741
0
    (list->base.hashcode_fn != NULL
742
0
     ? list->base.hashcode_fn (new_node->value)
743
0
     : (size_t)(uintptr_t) new_node->value);
744
745
  /* Add new_node to the hash table.  */
746
0
  if (add_to_bucket (list, new_node) < 0)
747
0
    {
748
0
      free (new_node);
749
0
      return NULL;
750
0
    }
751
0
#endif
752
753
  /* Add new_node to the list.  */
754
0
  new_node->prev = node;
755
0
  ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
756
0
  new_node->next->prev = new_node;
757
0
  ASYNCSAFE(gl_list_node_t) node->next = new_node;
758
0
  list->count++;
759
760
0
#if WITH_HASHTABLE
761
0
  hash_resize_after_add (list);
762
0
#endif
763
764
0
  return new_node;
765
0
}
766
767
static gl_list_node_t
768
gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt)
769
0
{
770
0
  size_t count = list->count;
771
0
  gl_list_node_t new_node;
772
773
0
  if (!(position <= count))
774
    /* Invalid argument.  */
775
0
    abort ();
776
777
0
  new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
778
0
  if (new_node == NULL)
779
0
    return NULL;
780
781
0
  ASYNCSAFE(const void *) new_node->value = elt;
782
0
#if WITH_HASHTABLE
783
0
  new_node->h.hashcode =
784
0
    (list->base.hashcode_fn != NULL
785
0
     ? list->base.hashcode_fn (new_node->value)
786
0
     : (size_t)(uintptr_t) new_node->value);
787
788
  /* Add new_node to the hash table.  */
789
0
  if (add_to_bucket (list, new_node) < 0)
790
0
    {
791
0
      free (new_node);
792
0
      return NULL;
793
0
    }
794
0
#endif
795
796
  /* Add new_node to the list.  */
797
0
  if (position <= (count / 2))
798
0
    {
799
0
      gl_list_node_t node;
800
801
0
      node = &list->root;
802
0
      for (; position > 0; position--)
803
0
        node = node->next;
804
0
      new_node->prev = node;
805
0
      ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
806
0
      new_node->next->prev = new_node;
807
0
      ASYNCSAFE(gl_list_node_t) node->next = new_node;
808
0
    }
809
0
  else
810
0
    {
811
0
      gl_list_node_t node;
812
813
0
      position = count - position;
814
0
      node = &list->root;
815
0
      for (; position > 0; position--)
816
0
        node = node->prev;
817
0
      ASYNCSAFE(gl_list_node_t) new_node->next = node;
818
0
      new_node->prev = node->prev;
819
0
      ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
820
0
      node->prev = new_node;
821
0
    }
822
0
  list->count++;
823
824
0
#if WITH_HASHTABLE
825
0
  hash_resize_after_add (list);
826
0
#endif
827
828
0
  return new_node;
829
0
}
830
831
static bool
832
gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
833
0
{
834
0
  gl_list_node_t prev;
835
0
  gl_list_node_t next;
836
837
0
#if WITH_HASHTABLE
838
  /* Remove node from the hash table.  */
839
0
  remove_from_bucket (list, node);
840
0
#endif
841
842
  /* Remove node from the list.  */
843
0
  prev = node->prev;
844
0
  next = node->next;
845
846
0
  ASYNCSAFE(gl_list_node_t) prev->next = next;
847
0
  next->prev = prev;
848
0
  list->count--;
849
850
0
  if (list->base.dispose_fn != NULL)
851
0
    list->base.dispose_fn (node->value);
852
0
  free (node);
853
0
  return true;
854
0
}
855
856
static bool
857
gl_linked_remove_at (gl_list_t list, size_t position)
858
0
{
859
0
  size_t count = list->count;
860
0
  gl_list_node_t removed_node;
861
862
0
  if (!(position < count))
863
    /* Invalid argument.  */
864
0
    abort ();
865
  /* Here we know count > 0.  */
866
0
  if (position <= ((count - 1) / 2))
867
0
    {
868
0
      gl_list_node_t node;
869
0
      gl_list_node_t after_removed;
870
871
0
      node = &list->root;
872
0
      for (; position > 0; position--)
873
0
        node = node->next;
874
0
      removed_node = node->next;
875
0
      after_removed = node->next->next;
876
0
      ASYNCSAFE(gl_list_node_t) node->next = after_removed;
877
0
      after_removed->prev = node;
878
0
    }
879
0
  else
880
0
    {
881
0
      gl_list_node_t node;
882
0
      gl_list_node_t before_removed;
883
884
0
      position = count - 1 - position;
885
0
      node = &list->root;
886
0
      for (; position > 0; position--)
887
0
        node = node->prev;
888
0
      removed_node = node->prev;
889
0
      before_removed = node->prev->prev;
890
0
      node->prev = before_removed;
891
0
      ASYNCSAFE(gl_list_node_t) before_removed->next = node;
892
0
    }
893
0
#if WITH_HASHTABLE
894
0
  remove_from_bucket (list, removed_node);
895
0
#endif
896
0
  list->count--;
897
898
0
  if (list->base.dispose_fn != NULL)
899
0
    list->base.dispose_fn (removed_node->value);
900
0
  free (removed_node);
901
0
  return true;
902
0
}
903
904
static bool
905
gl_linked_remove (gl_list_t list, const void *elt)
906
0
{
907
0
  gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
908
909
0
  if (node != NULL)
910
0
    return gl_linked_remove_node (list, node);
911
0
  else
912
0
    return false;
913
0
}
914
915
static void
916
gl_linked_list_free (gl_list_t list)
917
0
{
918
0
  gl_listelement_dispose_fn dispose = list->base.dispose_fn;
919
0
  gl_list_node_t node;
920
921
0
  for (node = list->root.next; node != &list->root; )
922
0
    {
923
0
      gl_list_node_t next = node->next;
924
0
      if (dispose != NULL)
925
0
        dispose (node->value);
926
0
      free (node);
927
0
      node = next;
928
0
    }
929
0
#if WITH_HASHTABLE
930
0
  free (list->table);
931
0
#endif
932
0
  free (list);
933
0
}
934
935
/* --------------------- gl_list_iterator_t Data Type --------------------- */
936
937
static gl_list_iterator_t _GL_ATTRIBUTE_PURE
938
gl_linked_iterator (gl_list_t list)
939
0
{
940
0
  gl_list_iterator_t result;
941
942
0
  result.vtable = list->base.vtable;
943
0
  result.list = list;
944
0
  result.p = list->root.next;
945
0
  result.q = &list->root;
946
#if defined GCC_LINT || defined lint
947
  result.i = 0;
948
  result.j = 0;
949
  result.count = 0;
950
#endif
951
952
0
  return result;
953
0
}
954
955
static gl_list_iterator_t _GL_ATTRIBUTE_PURE
956
gl_linked_iterator_from_to (gl_list_t list,
957
                            size_t start_index, size_t end_index)
958
0
{
959
0
  gl_list_iterator_t result;
960
0
  size_t n1, n2, n3;
961
962
0
  if (!(start_index <= end_index && end_index <= list->count))
963
    /* Invalid arguments.  */
964
0
    abort ();
965
0
  result.vtable = list->base.vtable;
966
0
  result.list = list;
967
0
  n1 = start_index;
968
0
  n2 = end_index - start_index;
969
0
  n3 = list->count - end_index;
970
  /* Find the maximum among n1, n2, n3, so as to reduce the number of
971
     loop iterations to n1 + n2 + n3 - max(n1,n2,n3).  */
972
0
  if (n1 > n2 && n1 > n3)
973
0
    {
974
      /* n1 is the maximum, use n2 and n3.  */
975
0
      gl_list_node_t node;
976
0
      size_t i;
977
978
0
      node = &list->root;
979
0
      for (i = n3; i > 0; i--)
980
0
        node = node->prev;
981
0
      result.q = node;
982
0
      for (i = n2; i > 0; i--)
983
0
        node = node->prev;
984
0
      result.p = node;
985
0
    }
986
0
  else if (n2 > n3)
987
0
    {
988
      /* n2 is the maximum, use n1 and n3.  */
989
0
      gl_list_node_t node;
990
0
      size_t i;
991
992
0
      node = list->root.next;
993
0
      for (i = n1; i > 0; i--)
994
0
        node = node->next;
995
0
      result.p = node;
996
997
0
      node = &list->root;
998
0
      for (i = n3; i > 0; i--)
999
0
        node = node->prev;
1000
0
      result.q = node;
1001
0
    }
1002
0
  else
1003
0
    {
1004
      /* n3 is the maximum, use n1 and n2.  */
1005
0
      gl_list_node_t node;
1006
0
      size_t i;
1007
1008
0
      node = list->root.next;
1009
0
      for (i = n1; i > 0; i--)
1010
0
        node = node->next;
1011
0
      result.p = node;
1012
0
      for (i = n2; i > 0; i--)
1013
0
        node = node->next;
1014
0
      result.q = node;
1015
0
    }
1016
1017
#if defined GCC_LINT || defined lint
1018
  result.i = 0;
1019
  result.j = 0;
1020
  result.count = 0;
1021
#endif
1022
1023
0
  return result;
1024
0
}
1025
1026
static bool
1027
gl_linked_iterator_next (gl_list_iterator_t *iterator,
1028
                         const void **eltp, gl_list_node_t *nodep)
1029
0
{
1030
0
  if (iterator->p != iterator->q)
1031
0
    {
1032
0
      gl_list_node_t node = (gl_list_node_t) iterator->p;
1033
0
      *eltp = node->value;
1034
0
      if (nodep != NULL)
1035
0
        *nodep = node;
1036
0
      iterator->p = node->next;
1037
0
      return true;
1038
0
    }
1039
0
  else
1040
0
    return false;
1041
0
}
1042
1043
static void
1044
gl_linked_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_iterator_t *iterator)
1045
0
{
1046
0
}
1047
1048
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
1049
1050
static gl_list_node_t _GL_ATTRIBUTE_PURE
1051
gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
1052
                             const void *elt)
1053
0
{
1054
0
  gl_list_node_t node;
1055
1056
0
  for (node = list->root.next; node != &list->root; node = node->next)
1057
0
    {
1058
0
      int cmp = compar (node->value, elt);
1059
1060
0
      if (cmp > 0)
1061
0
        break;
1062
0
      if (cmp == 0)
1063
0
        return node;
1064
0
    }
1065
0
  return NULL;
1066
0
}
1067
1068
static gl_list_node_t _GL_ATTRIBUTE_PURE
1069
gl_linked_sortedlist_search_from_to (gl_list_t list,
1070
                                     gl_listelement_compar_fn compar,
1071
                                     size_t low, size_t high,
1072
                                     const void *elt)
1073
0
{
1074
0
  size_t count = list->count;
1075
1076
0
  if (!(low <= high && high <= list->count))
1077
    /* Invalid arguments.  */
1078
0
    abort ();
1079
1080
0
  high -= low;
1081
0
  if (high > 0)
1082
0
    {
1083
      /* Here we know low < count.  */
1084
0
      size_t position = low;
1085
0
      gl_list_node_t node;
1086
1087
0
      if (position <= ((count - 1) / 2))
1088
0
        {
1089
0
          node = list->root.next;
1090
0
          for (; position > 0; position--)
1091
0
            node = node->next;
1092
0
        }
1093
0
      else
1094
0
        {
1095
0
          position = count - 1 - position;
1096
0
          node = list->root.prev;
1097
0
          for (; position > 0; position--)
1098
0
            node = node->prev;
1099
0
        }
1100
1101
0
      do
1102
0
        {
1103
0
          int cmp = compar (node->value, elt);
1104
1105
0
          if (cmp > 0)
1106
0
            break;
1107
0
          if (cmp == 0)
1108
0
            return node;
1109
0
          node = node->next;
1110
0
        }
1111
0
      while (--high > 0);
1112
0
    }
1113
0
  return NULL;
1114
0
}
1115
1116
static size_t _GL_ATTRIBUTE_PURE
1117
gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
1118
                              const void *elt)
1119
0
{
1120
0
  gl_list_node_t node;
1121
0
  size_t index;
1122
1123
0
  for (node = list->root.next, index = 0;
1124
0
       node != &list->root;
1125
0
       node = node->next, index++)
1126
0
    {
1127
0
      int cmp = compar (node->value, elt);
1128
1129
0
      if (cmp > 0)
1130
0
        break;
1131
0
      if (cmp == 0)
1132
0
        return index;
1133
0
    }
1134
0
  return (size_t)(-1);
1135
0
}
1136
1137
static size_t _GL_ATTRIBUTE_PURE
1138
gl_linked_sortedlist_indexof_from_to (gl_list_t list,
1139
                                      gl_listelement_compar_fn compar,
1140
                                      size_t low, size_t high,
1141
                                      const void *elt)
1142
0
{
1143
0
  size_t count = list->count;
1144
1145
0
  if (!(low <= high && high <= list->count))
1146
    /* Invalid arguments.  */
1147
0
    abort ();
1148
1149
0
  high -= low;
1150
0
  if (high > 0)
1151
0
    {
1152
      /* Here we know low < count.  */
1153
0
      size_t index = low;
1154
0
      size_t position = low;
1155
0
      gl_list_node_t node;
1156
1157
0
      if (position <= ((count - 1) / 2))
1158
0
        {
1159
0
          node = list->root.next;
1160
0
          for (; position > 0; position--)
1161
0
            node = node->next;
1162
0
        }
1163
0
      else
1164
0
        {
1165
0
          position = count - 1 - position;
1166
0
          node = list->root.prev;
1167
0
          for (; position > 0; position--)
1168
0
            node = node->prev;
1169
0
        }
1170
1171
0
      do
1172
0
        {
1173
0
          int cmp = compar (node->value, elt);
1174
1175
0
          if (cmp > 0)
1176
0
            break;
1177
0
          if (cmp == 0)
1178
0
            return index;
1179
0
          node = node->next;
1180
0
          index++;
1181
0
        }
1182
0
      while (--high > 0);
1183
0
    }
1184
0
  return (size_t)(-1);
1185
0
}
1186
1187
static gl_list_node_t
1188
gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
1189
                             const void *elt)
1190
0
{
1191
0
  gl_list_node_t node;
1192
1193
0
  for (node = list->root.next; node != &list->root; node = node->next)
1194
0
    if (compar (node->value, elt) >= 0)
1195
0
      return gl_linked_nx_add_before (list, node, elt);
1196
0
  return gl_linked_nx_add_last (list, elt);
1197
0
}
1198
1199
static bool
1200
gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1201
                             const void *elt)
1202
0
{
1203
0
  gl_list_node_t node;
1204
1205
0
  for (node = list->root.next; node != &list->root; node = node->next)
1206
0
    {
1207
0
      int cmp = compar (node->value, elt);
1208
1209
0
      if (cmp > 0)
1210
0
        break;
1211
0
      if (cmp == 0)
1212
0
        return gl_linked_remove_node (list, node);
1213
0
    }
1214
0
  return false;
1215
0
}