1 /* Sequential list data type implemented by a hash table with a binary tree.
2 Copyright (C) 2006 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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */
22 gl_tree_search (gl_list_t list, const void *elt)
25 (list->base.hashcode_fn != NULL
26 ? list->base.hashcode_fn (elt)
27 : (size_t)(uintptr_t) elt);
28 size_t index = hashcode % list->table_size;
29 gl_listelement_equals_fn equals = list->base.equals_fn;
30 gl_hash_entry_t entry;
32 if (list->base.allow_duplicates)
34 for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
35 if (entry->hashcode == hashcode)
37 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
39 /* An entry representing multiple nodes. */
40 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
41 /* Only the first node is interesting. */
42 gl_list_node_t node = gl_oset_first (nodes);
43 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
44 /* All nodes in the entry are equal to the given ELT.
45 But we have to return only the one at the minimal position,
46 and this is the first one in the ordered set. */
51 /* An entry representing a single node. */
52 gl_list_node_t node = (struct gl_list_node_impl *) entry;
53 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
60 /* If no duplicates are allowed, multiple nodes are not needed. */
61 for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
62 if (entry->hashcode == hashcode)
64 gl_list_node_t node = (struct gl_list_node_impl *) entry;
65 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
74 gl_tree_indexof (gl_list_t list, const void *elt)
76 gl_list_node_t node = gl_tree_search (list, elt);
79 return node_position (node);
85 gl_tree_list_free (gl_list_t list)
87 if (list->base.allow_duplicates)
89 /* Free the ordered sets in the hash buckets. */
92 for (i = list->table_size; i > 0; )
94 gl_hash_entry_t entry = list->table[--i];
98 gl_hash_entry_t next = entry->hash_next;
100 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
102 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
104 gl_oset_free (nodes);
113 /* Iterate across all elements in post-order. */
115 gl_list_node_t node = list->root;
117 iterstack_item_t *stack_ptr = &stack[0];
121 /* Descend on left branch. */
126 stack_ptr->node = node;
127 stack_ptr->rightp = false;
131 /* Climb up again. */
134 if (stack_ptr == &stack[0])
137 node = stack_ptr->node;
138 if (!stack_ptr->rightp)
140 /* Free the current node. */
143 /* Descend on right branch. */
144 stack_ptr->rightp = true;