octave-kai/gnulib-hg: lib/gl_anylinked

annotate lib/gl_anylinked_list2.h @ 9364:559ef0e161fe

New module: xprintf * modules/xprintf, lib/xprintf.c, lib/xprintf.h: New files.

author	Jim Meyering <meyering@redhat.com>
date	Fri, 19 Oct 2007 17:09:37 +0200
parents	bbbbbf4cd1c5
children	25f7280c9cf0

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 linked list.
8438 238942284e2f Allow the use of a destructor for the values stored in the list. 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: 8438 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: 8438 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: 8438 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: 8438 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_linked_list.c and gl_linkedhash_list.c. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	20 /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	21 a way that a gl_list_t data structure may be used from within a signal
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	22 handler. The operations allowed in the signal handler are:
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	23 gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	24 The list and node fields that are therefore accessed from the signal handler
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	25 are:
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	26 list->root, node->next, node->value.
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	27 We are careful to make modifications to these fields only in an order
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	28 that maintains the consistency of the list data structure at any moment,
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	29 and we use 'volatile' assignments to prevent the compiler from reordering
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	30 such assignments. */
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	31 #ifdef SIGNAL_SAFE_LIST
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	32 # define ASYNCSAFE(type) (volatile type )&
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	33 #else
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	34 # define ASYNCSAFE(type)
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	35 #endif
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	36
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 /* -------------------------- gl_list_t Data Type -------------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	38
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 static gl_list_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 gl_linked_create_empty (gl_list_implementation_t implementation,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 gl_listelement_equals_fn equals_fn,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 gl_listelement_hashcode_fn hashcode_fn,
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	43 gl_listelement_dispose_fn dispose_fn,
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 bool allow_duplicates)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	46 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	47
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 list->base.hashcode_fn = hashcode_fn;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	51 list->base.dispose_fn = dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 list->base.allow_duplicates = allow_duplicates;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 list->table_size = 11;
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	55 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 list->root.next = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 list->root.prev = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 list->count = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	60
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	61 return list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	63
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 static gl_list_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 gl_linked_create (gl_list_implementation_t implementation,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 gl_listelement_equals_fn equals_fn,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 gl_listelement_hashcode_fn hashcode_fn,
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	68 gl_listelement_dispose_fn dispose_fn,
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 bool allow_duplicates,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 size_t count, const void **contents)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	72 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 gl_list_node_t tail;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	74
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 list->base.hashcode_fn = hashcode_fn;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	78 list->base.dispose_fn = dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	79 list->base.allow_duplicates = allow_duplicates;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	80 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	81 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	82 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	83 if (estimate < 10)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 estimate = 10;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 list->table_size = next_prime (estimate);
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	86 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	89 list->count = count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	90 tail = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 for (; count > 0; contents++, count--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	93 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	94
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 node->value = *contents;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 : (size_t)(uintptr_t) node->value);
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 node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	104 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	105
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	106 /* Add node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 node->prev = tail;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	108 tail->next = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 tail = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 tail->next = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 list->root.prev = tail;
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 return list;
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 static size_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	118 gl_linked_size (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 return list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 }
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 static const void *
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 return node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	127 }
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 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	131 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	132 return (node->next != &list->root ? node->next : NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	133 }
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 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	137 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 return (node->prev != &list->root ? node->prev : NULL);
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 static const void *
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	142 gl_linked_get_at (gl_list_t list, size_t position)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	143 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	144 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	145 gl_list_node_t node;
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 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	148 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	149 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	150 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	151 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	153 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	156 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	157 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	158 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	159 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 node = list->root.prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	162 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	163 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 return node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 }
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 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	168 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
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 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	171 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	172
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	173 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	174 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	175 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	176 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	177 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	178 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	179 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	185 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 node = list->root.prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	187 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 if (elt != node->value)
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 size_t new_hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 ? list->base.hashcode_fn (elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	196 : (size_t)(uintptr_t) elt);
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 (new_hashcode != node->h.hashcode)
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 remove_from_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 node->h.hashcode = new_hashcode;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	207 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 #else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	209 node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	210 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	211 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	212 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	213
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	214 static gl_list_node_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	215 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	216 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	217 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	218 size_t count = list->count;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	219
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	220 if (!(start_index <= end_index && end_index <= count))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	221 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	222 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	223 {
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	224 #if WITH_HASHTABLE
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	225 size_t hashcode =
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	226 (list->base.hashcode_fn != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	227 ? list->base.hashcode_fn (elt)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	228 : (size_t)(uintptr_t) elt);
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	229 size_t bucket = hashcode % list->table_size;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	230 gl_listelement_equals_fn equals = list->base.equals_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	231
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	232 if (!list->base.allow_duplicates)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	233 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	234 /* Look for the first match in the hash bucket. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	235 gl_list_node_t found = NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	236 gl_list_node_t node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	237
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	238 for (node = (gl_list_node_t) list->table[bucket];
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	239 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	240 node = (gl_list_node_t) node->h.hash_next)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	241 if (node->h.hashcode == hashcode
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	242 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	243 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	244 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	245 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	246 found = node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	247 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	248 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	249 if (start_index > 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	250 /* Look whether found's index is < start_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	251 for (node = list->root.next; ; node = node->next)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	252 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	253 if (node == found)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	254 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	255 if (--start_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	256 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	257 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	258 if (end_index < count)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	259 /* Look whether found's index is >= end_index. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	260 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	261 end_index = count - end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	262 for (node = list->root.prev; ; node = node->prev)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	263 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	264 if (node == found)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	265 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	266 if (--end_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	267 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	269 }
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	270 return found;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	271 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	272 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	273 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	274 /* Look whether there is more than one match in the hash bucket. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	275 bool multiple_matches = false;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	276 gl_list_node_t first_match = NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	277 gl_list_node_t node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	278
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	279 for (node = (gl_list_node_t) list->table[bucket];
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	280 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	281 node = (gl_list_node_t) node->h.hash_next)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	282 if (node->h.hashcode == hashcode
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	283 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	284 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	285 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	286 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	287 if (first_match == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	288 first_match = node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	289 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	290 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	291 multiple_matches = true;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	292 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	293 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	294 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	295 if (multiple_matches)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	296 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	297 /* We need the match with the smallest index. But we don't have
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	298 a fast mapping node -> index. So we have to walk the list. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	299 end_index -= start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	300 node = list->root.next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	301 for (; start_index > 0; start_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	302 node = node->next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	303
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	304 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	305 end_index > 0;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	306 node = node->next, end_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	307 if (node->h.hashcode == hashcode
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	308 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	309 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	310 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	311 return node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	312 /* The matches must have all been at indices < start_index or
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	313 >= end_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	314 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	315 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	316 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	317 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	318 if (start_index > 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	319 /* Look whether first_match's index is < start_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	320 for (node = list->root.next; node != &list->root; node = node->next)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	321 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	322 if (node == first_match)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	323 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	324 if (--start_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	325 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	326 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	327 if (end_index < list->count)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	328 /* Look whether first_match's index is >= end_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	329 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	330 end_index = list->count - end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	331 for (node = list->root.prev; ; node = node->prev)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	332 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	333 if (node == first_match)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	334 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	335 if (--end_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	336 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	337 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	338 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	339 return first_match;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	340 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	341 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	342 #else
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	343 gl_listelement_equals_fn equals = list->base.equals_fn;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	344 gl_list_node_t node = list->root.next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	345
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	346 end_index -= start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	347 for (; start_index > 0; start_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	348 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	349
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	350 if (equals != NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	351 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	352 for (; end_index > 0; node = node->next, end_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	353 if (equals (elt, node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	354 return node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	355 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	356 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	357 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	358 for (; end_index > 0; node = node->next, end_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	359 if (elt == node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	360 return node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	361 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	362 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	363 #endif
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	364 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	366
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	367 static size_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	368 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	369 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	371 size_t count = list->count;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	372
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	373 if (!(start_index <= end_index && end_index <= count))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	374 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	375 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	376 {
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	377 #if WITH_HASHTABLE
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	378 /* Here the hash table doesn't help much. It only allows us to minimize
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	379 the number of equals() calls, by looking up first the node and then
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	380 its index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	381 size_t hashcode =
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	382 (list->base.hashcode_fn != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	383 ? list->base.hashcode_fn (elt)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	384 : (size_t)(uintptr_t) elt);
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	385 size_t bucket = hashcode % list->table_size;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	386 gl_listelement_equals_fn equals = list->base.equals_fn;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	387 gl_list_node_t node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	388
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	389 /* First step: Look up the node. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	390 if (!list->base.allow_duplicates)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	391 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	392 /* Look for the first match in the hash bucket. */
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	393 for (node = (gl_list_node_t) list->table[bucket];
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	394 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	395 node = (gl_list_node_t) node->h.hash_next)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	396 if (node->h.hashcode == hashcode
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	397 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	398 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	399 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	400 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	401 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	402 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	403 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	404 /* Look whether there is more than one match in the hash bucket. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	405 bool multiple_matches = false;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	406 gl_list_node_t first_match = NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	407
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	408 for (node = (gl_list_node_t) list->table[bucket];
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	409 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	410 node = (gl_list_node_t) node->h.hash_next)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	411 if (node->h.hashcode == hashcode
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	412 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	413 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	414 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	415 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	416 if (first_match == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	417 first_match = node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	418 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	419 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	420 multiple_matches = true;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	421 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	422 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	423 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	424 if (multiple_matches)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	425 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	426 /* We need the match with the smallest index. But we don't have
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	427 a fast mapping node -> index. So we have to walk the list. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	428 size_t index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	429
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	430 index = start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	431 node = list->root.next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	432 for (; start_index > 0; start_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	433 node = node->next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	434
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	435 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	436 index < end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	437 node = node->next, index++)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	438 if (node->h.hashcode == hashcode
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	439 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	440 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	441 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	442 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	443 /* The matches must have all been at indices < start_index or
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	444 >= end_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	445 return (size_t)(-1);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	446 }
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	447 node = first_match;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	448 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	449
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	450 /* Second step: Look up the index of the node. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	451 if (node == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	452 return (size_t)(-1);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	453 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	454 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	455 size_t index = 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	456
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	457 for (; node->prev != &list->root; node = node->prev)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	458 index++;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	459
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	460 if (index >= start_index && index < end_index)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	461 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	462 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	463 return (size_t)(-1);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	464 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	465 #else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	466 gl_listelement_equals_fn equals = list->base.equals_fn;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	467 size_t index = start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	468 gl_list_node_t node = list->root.next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	469
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	470 for (; start_index > 0; start_index--)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	471 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	472
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	473 if (equals != NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	474 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	475 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	476 index < end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	477 node = node->next, index++)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	478 if (equals (elt, node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	479 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	480 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	481 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	482 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	483 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	484 index < end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	485 node = node->next, index++)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	486 if (elt == node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	487 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	488 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	489 return (size_t)(-1);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	490 #endif
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	491 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	492 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	493
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	494 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	495 gl_linked_add_first (gl_list_t list, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	496 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	497 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	498
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	499 ASYNCSAFE(const void *) node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	500 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	501 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	502 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	503 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	504 : (size_t)(uintptr_t) node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	505
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	506 /* Add node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	507 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	509
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 /* Add node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	511 node->prev = &list->root;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	512 ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	513 node->next->prev = node;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	514 ASYNCSAFE(gl_list_node_t) list->root.next = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	516
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	517 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	518 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	520
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	521 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	522 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	523
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	524 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 gl_linked_add_last (gl_list_t list, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	526 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	527 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	528
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	529 ASYNCSAFE(const void *) node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	530 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	532 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	533 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	534 : (size_t)(uintptr_t) node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	535
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	536 /* Add node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	537 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	539
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	540 /* Add node to the list. */
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	541 ASYNCSAFE(gl_list_node_t) node->next = &list->root;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	542 node->prev = list->root.prev;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	543 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	544 list->root.prev = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	545 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	546
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	547 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	548 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	549 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	550
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	551 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	552 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	553
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	554 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	555 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	556 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	557 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	558
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	559 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	561 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	562 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	564 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	565
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 /* Add new_node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	568 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	569
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 /* Add new_node to the list. */
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	571 ASYNCSAFE(gl_list_node_t) new_node->next = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	572 new_node->prev = node->prev;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	573 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 node->prev = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	576
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	577 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	578 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	579 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	580
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	581 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	582 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	583
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	584 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	585 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	586 {
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	587 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	588
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	589 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	590 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	591 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	592 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	593 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	594 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	595
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	596 /* Add new_node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	597 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	598 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	599
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 /* Add new_node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	601 new_node->prev = node;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	602 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	603 new_node->next->prev = new_node;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	604 ASYNCSAFE(gl_list_node_t) node->next = new_node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	606
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	607 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	608 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	609 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	610
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	611 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	612 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	613
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	614 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	615 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	616 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	617 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	618 gl_list_node_t new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	619
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	620 if (!(position <= count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	621 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	622 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	623
7615 5657275cb755 More uses of XMALLOC, XNMALLOC and XCALLOC. Bruno Haible <bruno@clisp.org> parents: 7466 diff changeset	624 new_node = XMALLOC (struct gl_list_node_impl);
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	625 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	626 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	627 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	628 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	629 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	630 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	631
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	632 /* Add new_node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	633 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	634 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	635
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	636 /* Add new_node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	637 if (position <= (count / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	638 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	639 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	640
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	641 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	642 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	643 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 new_node->prev = node;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	645 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	646 new_node->next->prev = new_node;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	647 ASYNCSAFE(gl_list_node_t) node->next = new_node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	648 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	649 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	650 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	651 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	652
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	653 position = count - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	654 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	655 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	656 node = node->prev;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	657 ASYNCSAFE(gl_list_node_t) new_node->next = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	658 new_node->prev = node->prev;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	659 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	660 node->prev = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	661 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	662 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	663
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	664 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	665 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	666 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	667
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	668 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	669 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	670
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	671 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	672 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	674 gl_list_node_t prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	675 gl_list_node_t next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	676
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	677 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	678 /* Remove node from the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	679 remove_from_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	680 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	681
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	682 /* Remove node from the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	683 prev = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	684 next = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	685
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	686 ASYNCSAFE(gl_list_node_t) prev->next = next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	687 next->prev = prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	688 list->count--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	689
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	690 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	691 list->base.dispose_fn (node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	692 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	693 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	694 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	695
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	696 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	697 gl_linked_remove_at (gl_list_t list, size_t position)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	698 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	699 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	700 gl_list_node_t removed_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	701
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	702 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	703 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	704 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	705 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	706 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	707 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	708 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	709 gl_list_node_t after_removed;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	710
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	711 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	712 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	713 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	714 removed_node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	715 after_removed = node->next->next;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	716 ASYNCSAFE(gl_list_node_t) node->next = after_removed;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	717 after_removed->prev = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	718 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	719 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	720 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	721 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	722 gl_list_node_t before_removed;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	723
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	724 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	725 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	726 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	727 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	728 removed_node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	729 before_removed = node->prev->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	730 node->prev = before_removed;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	731 ASYNCSAFE(gl_list_node_t) before_removed->next = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	732 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	733 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	734 remove_from_bucket (list, removed_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	735 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	736 list->count--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	737
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	738 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	739 list->base.dispose_fn (removed_node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	740 free (removed_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	741 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	742 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	743
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	744 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	745 gl_linked_remove (gl_list_t list, const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	746 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	747 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	748
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	749 if (node != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	750 return gl_linked_remove_node (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	751 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	752 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	753 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	754
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	755 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	756 gl_linked_list_free (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	757 {
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	758 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	759 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	760
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	761 for (node = list->root.next; node != &list->root; )
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	762 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	763 gl_list_node_t next = node->next;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	764 if (dispose != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	765 dispose (node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	766 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	767 node = next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	768 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	769 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	770 free (list->table);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	771 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	772 free (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	773 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	774
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	775 /* --------------------- gl_list_iterator_t Data Type --------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	776
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	777 static gl_list_iterator_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	778 gl_linked_iterator (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	779 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	780 gl_list_iterator_t result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	781
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	782 result.vtable = list->base.vtable;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	783 result.list = list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	784 result.p = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	785 result.q = &list->root;
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	786 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	787 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	788 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	789 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	790 #endif
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	791
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	792 return result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	793 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	794
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	795 static gl_list_iterator_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	796 gl_linked_iterator_from_to (gl_list_t list,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	797 size_t start_index, size_t end_index)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	798 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	799 gl_list_iterator_t result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	800 size_t n1, n2, n3;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	801
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	802 if (!(start_index <= end_index && end_index <= list->count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	803 /* Invalid arguments. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	804 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	805 result.vtable = list->base.vtable;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	806 result.list = list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	807 n1 = start_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	808 n2 = end_index - start_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	809 n3 = list->count - end_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	810 /* Find the maximum among n1, n2, n3, so as to reduce the number of
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	811 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	812 if (n1 > n2 && n1 > n3)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	813 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	814 /* n1 is the maximum, use n2 and n3. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	815 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	816 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	817
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	818 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	819 for (i = n3; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	820 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	821 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	822 for (i = n2; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	823 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	824 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	825 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	826 else if (n2 > n3)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	827 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	828 /* n2 is the maximum, use n1 and n3. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	829 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	830 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	831
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	832 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	833 for (i = n1; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	834 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	835 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	836
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	837 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	838 for (i = n3; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	839 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	840 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	841 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	842 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	843 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	844 /* n3 is the maximum, use n1 and n2. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	845 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	846 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	847
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	848 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	849 for (i = n1; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	850 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	851 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	852 for (i = n2; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	853 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	854 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	855 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	856
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	857 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	858 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	859 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	860 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	861 #endif
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	862
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	863 return result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	864 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	865
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	866 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	867 gl_linked_iterator_next (gl_list_iterator_t *iterator,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	868 const void *eltp, gl_list_node_t nodep)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	869 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	870 if (iterator->p != iterator->q)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	871 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	872 gl_list_node_t node = (gl_list_node_t) iterator->p;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	873 *eltp = node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	874 if (nodep != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	875 *nodep = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	876 iterator->p = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	877 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	878 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	879 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	880 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	881 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	882
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	883 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	884 gl_linked_iterator_free (gl_list_iterator_t *iterator)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	885 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	886 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	887
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	888 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	889
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	890 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	891 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	892 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	893 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	894 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	895
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	896 for (node = list->root.next; node != &list->root; node = node->next)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	897 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	898 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	899
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	900 if (cmp > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	901 break;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	902 if (cmp == 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	903 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	904 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	905 return NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	906 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	907
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	908 static gl_list_node_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	909 gl_linked_sortedlist_search_from_to (gl_list_t list,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	910 gl_listelement_compar_fn compar,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	911 size_t low, size_t high,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	912 const void *elt)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	913 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	914 size_t count = list->count;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	915
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	916 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	917 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	918 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	919
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	920 high -= low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	921 if (high > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	922 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	923 /* Here we know low < count. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	924 size_t position = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	925 gl_list_node_t node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	926
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	927 if (position <= ((count - 1) / 2))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	928 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	929 node = list->root.next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	930 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	931 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	932 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	933 else
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	934 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	935 position = count - 1 - position;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	936 node = list->root.prev;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	937 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	938 node = node->prev;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	939 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	940
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	941 do
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	942 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	943 int cmp = compar (node->value, elt);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	944
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	945 if (cmp > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	946 break;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	947 if (cmp == 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	948 return node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	949 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	950 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	951 while (--high > 0);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	952 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	953 return NULL;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	954 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	955
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	956 static size_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	957 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	958 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	959 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	960 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	961 size_t index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	962
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	963 for (node = list->root.next, index = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	964 node != &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	965 node = node->next, index++)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	966 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	967 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	968
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	969 if (cmp > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	970 break;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	971 if (cmp == 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	972 return index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	973 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	974 return (size_t)(-1);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	975 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	976
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	977 static size_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	978 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	979 gl_listelement_compar_fn compar,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	980 size_t low, size_t high,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	981 const void *elt)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	982 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	983 size_t count = list->count;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	984
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	985 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	986 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	987 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	988
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	989 high -= low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	990 if (high > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	991 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	992 /* Here we know low < count. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	993 size_t index = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	994 size_t position = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	995 gl_list_node_t node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	996
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	997 if (position <= ((count - 1) / 2))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	998 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	999 node = list->root.next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1000 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1001 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1002 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1003 else
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1004 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1005 position = count - 1 - position;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1006 node = list->root.prev;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1007 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1008 node = node->prev;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1009 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1010
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1011 do
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1012 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1013 int cmp = compar (node->value, elt);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1014
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1015 if (cmp > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1016 break;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1017 if (cmp == 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1018 return index;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1019 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1020 index++;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1021 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1022 while (--high > 0);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1023 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1024 return (size_t)(-1);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1025 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1026
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1027 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1028 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1029 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1030 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1031 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1032
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1033 for (node = list->root.next; node != &list->root; node = node->next)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1034 if (compar (node->value, elt) >= 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1035 return gl_linked_add_before (list, node, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1036 return gl_linked_add_last (list, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1037 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1038
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1039 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1040 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1041 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1042 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1043 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1044
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1045 for (node = list->root.next; node != &list->root; node = node->next)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1046 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1047 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1048
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1049 if (cmp > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1050 break;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1051 if (cmp == 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1052 return gl_linked_remove_node (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1053 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1054 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1055 }

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/gl_anylinked_list2.h @ 9364:559ef0e161fe