Mercurial > hg > octave-kai > gnulib-hg

annotate lib/gl_anytreehash_list1.h @ 10667:678640901735

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move the isnanf(), isnand(), isnanl() declarations to <math.h>.
author Bruno Haible <bruno@clisp.org>
date Sun, 19 Oct 2008 14:05:30 +0200
parents bbbbbf4cd1c5
children e8d2c6fc33ad
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
1 /* Sequential list data type implemented by a hash table with a binary tree.
8436
36bbb949160c Add an element disposal function.
Bruno Haible <bruno@clisp.org>
parents: 7615
diff changeset
2 Copyright (C) 2006-2007 Free Software Foundation, Inc.
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
4
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
5 This program is free software: you can redistribute it and/or modify
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
6 it under the terms of the GNU General Public License as published by
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
8 (at your option) any later version.
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
9
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
10 This program is distributed in the hope that it will be useful,
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
13 GNU General Public License for more details.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
14
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
15 You should have received a copy of the GNU General Public License
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 8436
diff changeset
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
17
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
18 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
19
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
20 /* Hash table entry representing the same value at more than one position. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
21 struct gl_multiple_nodes
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
22 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
23 struct gl_hash_entry h; /* hash table entry fields; must be first */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
24 void *magic; /* used to distinguish from single node */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
25 gl_oset_t nodes; /* set of nodes, sorted by position */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
26 };
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
27 /* A value that cannot occur at the corresponding field (->left) in
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
28 gl_list_node_impl. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
29 #define MULTIPLE_NODES_MAGIC (void *) -1
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
30
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
31 /* Resize the hash table if needed, after list->count was incremented. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
32 static inline void
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
33 hash_resize_after_add (gl_list_t list)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
34 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
35 size_t count = (list->root != 0 ? list->root->branch_size : 0);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
36 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
37 if (estimate > list->table_size)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
38 hash_resize (list, estimate);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
39 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
40
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
41 /* Return the position of the given node in the tree. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
42 static size_t
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
43 node_position (gl_list_node_t node)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
44 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
45 size_t position = 0;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
46
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
47 if (node->left != NULL)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
48 position += node->left->branch_size;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
49 for (;;)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
50 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
51 gl_list_node_t parent = node->parent;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
52
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
53 if (parent == NULL)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
54 return position;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
55 /* position is now relative to the subtree of node. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
56 if (parent->right == node)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
57 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
58 position += 1;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
59 if (parent->left != NULL)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
60 position += parent->left->branch_size;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
61 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
62 /* position is now relative to the subtree of parent. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
63 node = parent;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
64 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
65 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
66
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
67 /* Compares two nodes by their position in the tree. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
68 static int
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
69 compare_by_position (const void *x1, const void *x2)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
70 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
71 gl_list_node_t node1 = (gl_list_node_t) x1;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
72 gl_list_node_t node2 = (gl_list_node_t) x2;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
73 size_t position1 = node_position (node1);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
74 size_t position2 = node_position (node2);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
75
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
76 return (position1 > position2 ? 1 :
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
77 position1 < position2 ? -1 : 0);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
78 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
79
7405
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
80 /* Compares a node's position in the tree with a given threshold. */
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
81 static bool
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
82 compare_position_threshold (const void *x, const void *threshold)
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
83 {
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
84 gl_list_node_t node = (gl_list_node_t) x;
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
85 size_t position = node_position (node);
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
86 return (position >= (uintptr_t)threshold);
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
87 }
0de49c40e105 Add searching operations, limited to a subsequence of the list.
Bruno Haible <bruno@clisp.org>
parents: 6973
diff changeset
88
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
89 /* Return the first element of a non-empty ordered set of nodes. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
90 static inline gl_list_node_t
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
91 gl_oset_first (gl_oset_t set)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
92 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
93 gl_oset_iterator_t iter = gl_oset_iterator (set);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
94 const void *first;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
95
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
96 if (!gl_oset_iterator_next (&iter, &first))
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
97 abort ();
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
98 gl_oset_iterator_free (&iter);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
99 return (gl_list_node_t) first;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
100 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
101
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
102 /* Add a node to the hash table structure.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
103 If duplicates are allowed, this function performs in average time
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
104 O((log n)^2): gl_oset_add may need to add an element to an ordered set of
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
105 size O(n), needing O(log n) comparison function calls. The comparison
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
106 function is compare_by_position, which is O(log n) worst-case.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
107 If duplicates are forbidden, this function is O(1). */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
108 static void
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
109 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
110 {
7466
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
111 size_t bucket = new_node->h.hashcode % list->table_size;
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
112
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
113 /* If no duplicates are allowed, multiple nodes are not needed. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
114 if (list->base.allow_duplicates)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
115 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
116 size_t hashcode = new_node->h.hashcode;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
117 const void *value = new_node->value;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
118 gl_listelement_equals_fn equals = list->base.equals_fn;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
119 gl_hash_entry_t *entryp;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
120
7466
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
121 for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next)
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
122 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
123 gl_hash_entry_t entry = *entryp;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
124
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
125 if (entry->hashcode == hashcode)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
126 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
127 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
128 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
129 /* An entry representing multiple nodes. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
130 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
131 /* Only the first node is interesting. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
132 gl_list_node_t node = gl_oset_first (nodes);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
133 if (equals != NULL ? equals (value, node->value) : value == node->value)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
134 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
135 /* Found already multiple nodes with the same value.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
136 Add the new_node to it. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
137 gl_oset_add (nodes, new_node);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
138 return;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
139 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
140 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
141 else
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
142 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
143 /* An entry representing a single node. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
144 gl_list_node_t node = (struct gl_list_node_impl *) entry;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
145 if (equals != NULL ? equals (value, node->value) : value == node->value)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
146 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
147 /* Found already a node with the same value. Turn it
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
148 into an ordered set, and add new_node to it. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
149 gl_oset_t nodes;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
150 struct gl_multiple_nodes *multi_entry;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
151
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
152 nodes =
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
153 gl_oset_create_empty (OSET_TREE_FLAVOR,
8436
36bbb949160c Add an element disposal function.
Bruno Haible <bruno@clisp.org>
parents: 7615
diff changeset
154 compare_by_position, NULL);
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
155
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
156 gl_oset_add (nodes, node);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
157 gl_oset_add (nodes, new_node);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
158
7615
5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC.
Bruno Haible <bruno@clisp.org>
parents: 7466
diff changeset
159 multi_entry = XMALLOC (struct gl_multiple_nodes);
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
160 multi_entry->h.hash_next = entry->hash_next;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
161 multi_entry->h.hashcode = entry->hashcode;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
162 multi_entry->magic = MULTIPLE_NODES_MAGIC;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
163 multi_entry->nodes = nodes;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
164 *entryp = &multi_entry->h;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
165 return;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
166 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
167 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
168 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
169 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
170 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
171 /* If no duplicates are allowed, multiple nodes are not needed. */
7466
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
172 new_node->h.hash_next = list->table[bucket];
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
173 list->table[bucket] = &new_node->h;
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
174 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
175
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
176 /* Remove a node from the hash table structure.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
177 If duplicates are allowed, this function performs in average time
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
178 O((log n)^2): gl_oset_remove may need to remove an element from an ordered
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
179 set of size O(n), needing O(log n) comparison function calls. The
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
180 comparison function is compare_by_position, which is O(log n) worst-case.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
181 If duplicates are forbidden, this function is O(1) on average. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
182 static void
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
183 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
184 {
7466
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
185 size_t bucket = old_node->h.hashcode % list->table_size;
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
186
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
187 if (list->base.allow_duplicates)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
188 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
189 size_t hashcode = old_node->h.hashcode;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
190 const void *value = old_node->value;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
191 gl_listelement_equals_fn equals = list->base.equals_fn;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
192 gl_hash_entry_t *entryp;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
193
7466
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
194 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
195 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
196 gl_hash_entry_t entry = *entryp;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
197
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
198 if (entry == &old_node->h)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
199 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
200 /* Found old_node as a single node in the bucket. Remove it. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
201 *entryp = old_node->h.hash_next;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
202 break;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
203 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
204 if (entry == NULL)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
205 /* node is not in the right bucket. Did the hash codes
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
206 change inadvertently? */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
207 abort ();
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
208 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
209 && entry->hashcode == hashcode)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
210 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
211 /* An entry representing multiple nodes. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
212 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
213 /* Only the first node is interesting. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
214 gl_list_node_t node = gl_oset_first (nodes);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
215 if (equals != NULL ? equals (value, node->value) : value == node->value)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
216 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
217 /* Found multiple nodes with the same value.
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
218 old_node must be one of them. Remove it. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
219 if (!gl_oset_remove (nodes, old_node))
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
220 abort ();
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
221 if (gl_oset_size (nodes) == 1)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
222 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
223 /* Replace a one-element set with a single node. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
224 node = gl_oset_first (nodes);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
225 node->h.hash_next = entry->hash_next;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
226 *entryp = &node->h;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
227 gl_oset_free (nodes);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
228 free (entry);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
229 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
230 break;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
231 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
232 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
233 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
234 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
235 else
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
236 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
237 /* If no duplicates are allowed, multiple nodes are not needed. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
238 gl_hash_entry_t *entryp;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
239
7466
c9738ed4c499 Avoid using the variable name 'index' for two completely different things.
Bruno Haible <bruno@clisp.org>
parents: 7405
diff changeset
240 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
6973
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
241 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
242 if (*entryp == &old_node->h)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
243 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
244 *entryp = old_node->h.hash_next;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
245 break;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
246 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
247 if (*entryp == NULL)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
248 /* node is not in the right bucket. Did the hash codes
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
249 change inadvertently? */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
250 abort ();
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
251 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
252 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
253 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
254
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
255 /* Build up the hash table during initialization: Store all the nodes of
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
256 list->root in the hash table. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
257 static inline void
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
258 add_nodes_to_buckets (gl_list_t list)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
259 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
260 /* Iterate across all nodes. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
261 gl_list_node_t node = list->root;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
262 iterstack_t stack;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
263 iterstack_item_t *stack_ptr = &stack[0];
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
264
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
265 for (;;)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
266 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
267 /* Descend on left branch. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
268 for (;;)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
269 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
270 if (node == NULL)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
271 break;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
272 stack_ptr->node = node;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
273 stack_ptr->rightp = false;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
274 node = node->left;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
275 stack_ptr++;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
276 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
277 /* Climb up again. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
278 for (;;)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
279 {
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
280 if (stack_ptr == &stack[0])
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
281 return;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
282 stack_ptr--;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
283 if (!stack_ptr->rightp)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
284 break;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
285 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
286 node = stack_ptr->node;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
287 /* Add the current node to the hash table. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
288 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
289 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
290 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
291 : (size_t)(uintptr_t) node->value);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
292 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
293 /* Descend on right branch. */
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
294 stack_ptr->rightp = true;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
295 node = node->right;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
296 stack_ptr++;
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
297 }
de9a21fc207a Common code several concrete list implementations.
Bruno Haible <bruno@clisp.org>
parents:
diff changeset
298 }