1 /* Sequential list data type implemented by a hash table with a linked list.
2 Copyright (C) 2006, 2008-2017 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
21 #include "gl_linkedhash_list.h"
23 #include <stdint.h> /* for SIZE_MAX */
29 # define uintptr_t unsigned long
32 #define WITH_HASHTABLE 1
34 /* -------------------------- gl_list_t Data Type -------------------------- */
36 /* Generic hash-table code. */
37 #include "gl_anyhash_list1.h"
39 /* Generic linked list code. */
40 #include "gl_anylinked_list1.h"
42 /* Generic hash-table code. */
43 #include "gl_anyhash_list2.h"
45 /* Resize the hash table if needed, after list->count was incremented. */
47 hash_resize_after_add (gl_list_t list
)
49 size_t count
= list
->count
;
50 size_t estimate
= xsum (count
, count
/ 2); /* 1.5 * count */
51 if (estimate
> list
->table_size
)
52 hash_resize (list
, estimate
);
55 /* Add a node to the hash table structure. */
57 add_to_bucket (gl_list_t list
, gl_list_node_t node
)
59 size_t bucket
= node
->h
.hashcode
% list
->table_size
;
61 node
->h
.hash_next
= list
->table
[bucket
];
62 list
->table
[bucket
] = &node
->h
;
64 /* Tell all compilers that the return value is 0. */
65 #define add_to_bucket(list,node) ((add_to_bucket) (list, node), 0)
67 /* Remove a node from the hash table structure. */
69 remove_from_bucket (gl_list_t list
, gl_list_node_t node
)
71 size_t bucket
= node
->h
.hashcode
% list
->table_size
;
74 for (p
= &list
->table
[bucket
]; ; p
= &(*p
)->hash_next
)
78 *p
= node
->h
.hash_next
;
82 /* node is not in the right bucket. Did the hash codes
83 change inadvertently? */
88 /* Generic linked list code. */
89 #include "gl_anylinked_list2.h"
92 const struct gl_list_implementation gl_linkedhash_list_implementation
=
94 gl_linked_nx_create_empty
,
98 gl_linked_node_nx_set_value
,
100 gl_linked_previous_node
,
103 gl_linked_search_from_to
,
104 gl_linked_indexof_from_to
,
105 gl_linked_nx_add_first
,
106 gl_linked_nx_add_last
,
107 gl_linked_nx_add_before
,
108 gl_linked_nx_add_after
,
110 gl_linked_remove_node
,
115 gl_linked_iterator_from_to
,
116 gl_linked_iterator_next
,
117 gl_linked_iterator_free
,
118 gl_linked_sortedlist_search
,
119 gl_linked_sortedlist_search_from_to
,
120 gl_linked_sortedlist_indexof
,
121 gl_linked_sortedlist_indexof_from_to
,
122 gl_linked_sortedlist_nx_add
,
123 gl_linked_sortedlist_remove