octave-jordi/gnulib-hg: lib/gl_anytreehash

annotate lib/gl_anytreehash_list1.h @ 18070:d460ec17f09f

autoupdate

author	Karl Berry <karl@freefriends.org>
date	Tue, 28 Jul 2015 13:57:32 -0700
parents	ab58d4870664
children

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.
17848 ab58d4870664 version-etc: new year Paul Eggert <eggert@cs.ucla.edu> parents: 17587 diff changeset	2 Copyright (C) 2006-2007, 2009-2015 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. */
17193 52867afa3702 rbtree-list, rbtreehash-list: no 'static inline' Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	32 static void
6973 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)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	54 return position;
6973 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)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	57 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	58 position += 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	59 if (parent->left != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	60 position += parent->left->branch_size;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	61 }
6973 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 :
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	77 position1 < position2 ? -1 : 0);
6973 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. */
17193 52867afa3702 rbtree-list, rbtreehash-list: no 'static inline' Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	90 static gl_list_node_t
6973 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
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	104 O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	105 of size O(n), needing O(log n) comparison function calls. The comparison
6973 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.
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	107 If duplicates are forbidden, this function is O(1).
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	108 Return 0 upon success, -1 upon out-of-memory. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	109 static int
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 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	111 {
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	112 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	113
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 /* 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	115 if (list->base.allow_duplicates)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 size_t hashcode = new_node->h.hashcode;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	118 const void *value = new_node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 gl_listelement_equals_fn equals = list->base.equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 gl_hash_entry_t *entryp;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	122 for (entryp = &list->table[bucket]; entryp != NULL; entryp = &(entryp)->hash_next)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	123 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	124 gl_hash_entry_t entry = *entryp;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	125
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	126 if (entry->hashcode == hashcode)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	127 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	128 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	129 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	130 /* An entry representing multiple nodes. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	131 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	132 /* Only the first node is interesting. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	133 gl_list_node_t node = gl_oset_first (nodes);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	134 if (equals != NULL ? equals (value, node->value) : value == node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	135 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	136 /* Found already multiple nodes with the same value.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	137 Add the new_node to it. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	138 return gl_oset_nx_add (nodes, new_node);
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	139 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	140 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	141 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	142 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	143 /* An entry representing a single node. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	144 gl_list_node_t node = (struct gl_list_node_impl *) entry;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	145 if (equals != NULL ? equals (value, node->value) : value == node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	146 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	147 /* Found already a node with the same value. Turn it
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	148 into an ordered set, and add new_node to it. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	149 gl_oset_t nodes;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	150 struct gl_multiple_nodes *multi_entry;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	151
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	152 nodes =
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	153 gl_oset_nx_create_empty (OSET_TREE_FLAVOR,
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	154 compare_by_position, NULL);
29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	155 if (nodes == NULL)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	156 return -1;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	157
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	158 if (gl_oset_nx_add (nodes, node) < 0)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	159 goto fail;
12444 29d240cb21b2 Move the malloc checking from module 'oset' to new module 'xoset'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	160 if (gl_oset_nx_add (nodes, new_node) < 0)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	161 goto fail;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	162
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	163 multi_entry =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	164 (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	165 if (multi_entry == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	166 goto fail;
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	167 multi_entry->h.hash_next = entry->hash_next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	168 multi_entry->h.hashcode = entry->hashcode;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	169 multi_entry->magic = MULTIPLE_NODES_MAGIC;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	170 multi_entry->nodes = nodes;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	171 *entryp = &multi_entry->h;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	172 return 0;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	173
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	174 fail:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	175 gl_oset_free (nodes);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	176 return -1;
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	177 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	178 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	179 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	180 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 /* 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	183 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	184 list->table[bucket] = &new_node->h;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	185 return 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	187 /* Tell GCC that the likely return value is 0. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	188 #if __GNUC__ >= 3
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	189 # define add_to_bucket(list,node) \
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	190 __builtin_expect ((add_to_bucket) (list, node), 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	191 #endif
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	192
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 /* Remove a node from the hash table structure.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 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	195 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	196 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	197 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	198 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	199 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	200 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	201 {
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	202 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	203
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 if (list->base.allow_duplicates)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 size_t hashcode = old_node->h.hashcode;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	207 const void *value = old_node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 gl_listelement_equals_fn equals = list->base.equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	209 gl_hash_entry_t *entryp;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	210
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	211 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	212 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	213 gl_hash_entry_t entry = *entryp;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	214
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	215 if (entry == &old_node->h)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	217 /* Found old_node as a single node in the bucket. Remove it. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	218 *entryp = old_node->h.hash_next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	219 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	220 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	221 if (entry == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	222 /* node is not in the right bucket. Did the hash codes
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	223 change inadvertently? */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	224 abort ();
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	225 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	226 && entry->hashcode == hashcode)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	227 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	228 /* An entry representing multiple nodes. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	229 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	230 /* Only the first node is interesting. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	231 gl_list_node_t node = gl_oset_first (nodes);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	232 if (equals != NULL ? equals (value, node->value) : value == node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	233 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	234 /* Found multiple nodes with the same value.
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	235 old_node must be one of them. Remove it. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	236 if (!gl_oset_remove (nodes, old_node))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	237 abort ();
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	238 if (gl_oset_size (nodes) == 1)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	239 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	240 /* Replace a one-element set with a single node. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	241 node = gl_oset_first (nodes);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	242 node->h.hash_next = entry->hash_next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	243 *entryp = &node->h;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	244 gl_oset_free (nodes);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	245 free (entry);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	246 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	247 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	248 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	249 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	250 }
6973 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 else
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 /* 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	255 gl_hash_entry_t *entryp;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	256
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	257 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	258 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	259 if (*entryp == &old_node->h)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	260 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	261 *entryp = old_node->h.hash_next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	262 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	263 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	264 if (*entryp == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	265 /* node is not in the right bucket. Did the hash codes
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	266 change inadvertently? */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	267 abort ();
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	268 }
6973 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 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	271
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 /* Build up the hash table during initialization: Store all the nodes of
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	273 list->root in the hash table.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	274 Return 0 upon success, -1 upon out-of-memory. */
17193 52867afa3702 rbtree-list, rbtreehash-list: no 'static inline' Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	275 static int
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	276 add_nodes_to_buckets (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	277 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	278 /* Iterate across all nodes. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	279 gl_list_node_t node = list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 iterstack_t stack;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	281 iterstack_item_t *stack_ptr = &stack[0];
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	282
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	283 for (;;)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	284 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	285 /* Descend on left branch. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	286 for (;;)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	287 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	288 if (node == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	289 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	290 stack_ptr->node = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	291 stack_ptr->rightp = false;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	292 node = node->left;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	293 stack_ptr++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	294 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	295 /* Climb up again. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	296 for (;;)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	297 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	298 if (stack_ptr == &stack[0])
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	299 goto done;
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	300 stack_ptr--;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	301 if (!stack_ptr->rightp)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	302 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	303 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	304 node = stack_ptr->node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	305 /* Add the current node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	306 node->h.hashcode =
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	307 (list->base.hashcode_fn != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	308 ? list->base.hashcode_fn (node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	309 : (size_t)(uintptr_t) node->value);
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	310 if (add_to_bucket (list, node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	311 goto fail;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	312 /* Descend on right branch. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	313 stack_ptr->rightp = true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	314 node = node->right;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	315 stack_ptr++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	316 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	317 done:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	318 return 0;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	319
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	320 fail:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	321 /* Undo everything. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	322 for (;;)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	323 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	324 /* Descend on left branch. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	325 stack_ptr->rightp = false;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	326 node = node->left;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	327 stack_ptr++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	328 /* Descend on right branch. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	329 for (;;)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	330 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	331 if (node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	332 break;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	333 stack_ptr->node = node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	334 stack_ptr->rightp = true;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	335 node = node->right;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	336 stack_ptr++;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	337 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	338 /* Climb up again. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	339 for (;;)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	340 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	341 if (stack_ptr == &stack[0])
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	342 goto fail_done;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	343 stack_ptr--;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	344 if (stack_ptr->rightp)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	345 break;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	346 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	347 node = stack_ptr->node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	348 /* Remove the current node from the hash table. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	349 remove_from_bucket (list, node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	350 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	351 fail_done:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	352 return -1;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	354 /* Tell GCC that the likely return value is 0. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	355 #if __GNUC__ >= 3
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	356 # define add_nodes_to_buckets(list) \
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	357 __builtin_expect ((add_nodes_to_buckets) (list), 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12444 diff changeset	358 #endif

Mercurial > hg > octave-jordi > gnulib-hg

annotate lib/gl_anytreehash_list1.h @ 18070:d460ec17f09f