1  /* Sequential list data type implemented by a hash table with a linked list.
       2     Copyright (C) 2006, 2008-2023 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  #include <config.h>
      19  
      20  /* Specification.  */
      21  #include "gl_linkedhash_list.h"
      22  
      23  #include <stdint.h> /* for uintptr_t, SIZE_MAX */
      24  #include <stdlib.h>
      25  
      26  #include "xsize.h"
      27  
      28  #define WITH_HASHTABLE 1
      29  
      30  /* -------------------------- gl_list_t Data Type -------------------------- */
      31  
      32  /* Generic hash-table code.  */
      33  #include "gl_anyhash1.h"
      34  
      35  /* Generic linked list code.  */
      36  #include "gl_anylinked_list1.h"
      37  
      38  /* Generic hash-table code.  */
      39  #define CONTAINER_T gl_list_t
      40  #define CONTAINER_COUNT(list) (list)->count
      41  #include "gl_anyhash2.h"
      42  
      43  /* Add a node to the hash table structure.  */
      44  static void
      45  add_to_bucket (gl_list_t list, gl_list_node_t node)
      46  {
      47    size_t bucket = node->h.hashcode % list->table_size;
      48  
      49    node->h.hash_next = list->table[bucket];
      50    list->table[bucket] = &node->h;
      51  }
      52  /* Tell all compilers that the return value is 0.  */
      53  #define add_to_bucket(list,node)  ((add_to_bucket) (list, node), 0)
      54  
      55  /* Remove a node from the hash table structure.  */
      56  static void
      57  remove_from_bucket (gl_list_t list, gl_list_node_t node)
      58  {
      59    size_t bucket = node->h.hashcode % list->table_size;
      60    gl_hash_entry_t *p;
      61  
      62    for (p = &list->table[bucket]; ; p = &(*p)->hash_next)
      63      {
      64        if (*p == &node->h)
      65          {
      66            *p = node->h.hash_next;
      67            break;
      68          }
      69        if (*p == NULL)
      70          /* node is not in the right bucket.  Did the hash codes
      71             change inadvertently?  */
      72          abort ();
      73      }
      74  }
      75  
      76  /* Generic linked list code.  */
      77  #include "gl_anylinked_list2.h"
      78  
      79  
      80  const struct gl_list_implementation gl_linkedhash_list_implementation =
      81    {
      82      gl_linked_nx_create_empty,
      83      gl_linked_nx_create,
      84      gl_linked_size,
      85      gl_linked_node_value,
      86      gl_linked_node_nx_set_value,
      87      gl_linked_next_node,
      88      gl_linked_previous_node,
      89      gl_linked_first_node,
      90      gl_linked_last_node,
      91      gl_linked_get_at,
      92      gl_linked_nx_set_at,
      93      gl_linked_search_from_to,
      94      gl_linked_indexof_from_to,
      95      gl_linked_nx_add_first,
      96      gl_linked_nx_add_last,
      97      gl_linked_nx_add_before,
      98      gl_linked_nx_add_after,
      99      gl_linked_nx_add_at,
     100      gl_linked_remove_node,
     101      gl_linked_remove_at,
     102      gl_linked_remove,
     103      gl_linked_list_free,
     104      gl_linked_iterator,
     105      gl_linked_iterator_from_to,
     106      gl_linked_iterator_next,
     107      gl_linked_iterator_free,
     108      gl_linked_sortedlist_search,
     109      gl_linked_sortedlist_search_from_to,
     110      gl_linked_sortedlist_indexof,
     111      gl_linked_sortedlist_indexof_from_to,
     112      gl_linked_sortedlist_nx_add,
     113      gl_linked_sortedlist_remove
     114    };