octave-jordi/gnulib-hg: lib/gl_anylinked

annotate lib/gl_anylinked_list2.h @ 7410:9704ff2cbdfe

Add bounded list search operations.

author	Bruno Haible <bruno@clisp.org>
date	Fri, 06 Oct 2006 12:06:07 +0000
parents	0de49c40e105
children	c9738ed4c499

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.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	2 Copyright (C) 2006 Free Software Foundation, Inc.
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	5 This program is free software; you can redistribute it and/or modify
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	7 the Free Software Foundation; either version 2, or (at your option)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	8 any later version.
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	16 along with this program; if not, write to the Free Software Foundation,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	18
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	19 /* 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	20
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	21 /* 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	22 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	23 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	24 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	25 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	26 are:
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	27 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	28 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	29 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	30 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	31 such assignments. */
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	32 #ifdef SIGNAL_SAFE_LIST
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	33 # 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	34 #else
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	35 # define ASYNCSAFE(type)
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	36 #endif
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	37
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 /* -------------------------- gl_list_t Data Type -------------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	39
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 static gl_list_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 gl_linked_create_empty (gl_list_implementation_t implementation,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 gl_listelement_equals_fn equals_fn,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 gl_listelement_hashcode_fn hashcode_fn,
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 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 struct gl_list_impl *list =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	48
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 list->base.hashcode_fn = hashcode_fn;
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;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 list->table =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 (gl_hash_entry_t ) xzalloc (list->table_size sizeof (gl_hash_entry_t));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 list->root.next = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 list->root.prev = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 list->count = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	61
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 return list;
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 static gl_list_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 gl_linked_create (gl_list_implementation_t implementation,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 gl_listelement_equals_fn equals_fn,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 gl_listelement_hashcode_fn hashcode_fn,
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 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 struct gl_list_impl *list =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 gl_list_node_t tail;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	75
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 list->base.hashcode_fn = hashcode_fn;
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);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 list->table =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 (gl_hash_entry_t ) xzalloc (list->table_size sizeof (gl_hash_entry_t));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	89 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	90 list->count = count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 tail = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 for (; count > 0; contents++, count--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 gl_list_node_t node =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 (struct gl_list_node_impl *)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 xmalloc (sizeof (struct gl_list_node_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	97
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 node->value = *contents;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	102 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 : (size_t)(uintptr_t) node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	104
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	105 /* Add node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	106 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	108
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 /* Add node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 node->prev = tail;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 tail->next = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 tail = node;
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 tail->next = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 list->root.prev = tail;
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 return list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	118 }
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 static size_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 gl_linked_size (gl_list_t list)
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 return list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	125
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 static const void *
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	127 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	128 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 return node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 }
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 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	133 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	134 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	135 return (node->next != &list->root ? node->next : NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 }
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 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 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	140 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 return (node->prev != &list->root ? node->prev : NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	142 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	143
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	144 static const void *
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	145 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	146 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	147 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	148 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	149
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	150 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	151 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	153 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	156 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	157 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	158 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	159 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	162 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	163 node = list->root.prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 node = node->prev;
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 return node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	168 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	169
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	170 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	171 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	172 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	173 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	174 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	175
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	176 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	177 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	178 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	179 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	185 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	187 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 node = list->root.prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 node = node->prev;
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 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 if (elt != node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	196 size_t new_hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	197 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	198 ? list->base.hashcode_fn (elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	199 : (size_t)(uintptr_t) elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	200
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 if (new_hashcode != node->h.hashcode)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 remove_from_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 node->h.hashcode = new_hashcode;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 add_to_bucket (list, node);
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 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	211 #else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	212 node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	213 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	214 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	215 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	216
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	217 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	218 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	219 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	220 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	221 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	222
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	223 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	224 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	225 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	226 {
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	227 #if WITH_HASHTABLE
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	228 size_t hashcode =
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	229 (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	230 ? 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	231 : (size_t)(uintptr_t) elt);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	232 size_t index = hashcode % list->table_size;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	233 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	234
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	235 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	236 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	237 /* 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	238 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	239 gl_list_node_t node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	240
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	241 for (node = (gl_list_node_t) list->table[index];
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	242 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	243 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	244 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	245 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	246 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	247 : elt == node->value))
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 found = node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	250 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	251 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	252 if (start_index > 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	253 /* 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	254 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	255 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	256 if (node == found)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	257 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	258 if (--start_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	259 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	260 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	261 if (end_index < count)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	262 /* Look whether found's index is >= end_index. */
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 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	265 for (node = list->root.prev; ; node = node->prev)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	266 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	267 if (node == found)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	268 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	269 if (--end_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	270 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	271 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 }
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	273 return found;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	274 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	275 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	276 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	277 /* 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	278 bool multiple_matches = false;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	279 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	280 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	281
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	282 for (node = (gl_list_node_t) list->table[index];
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	283 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	284 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	285 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	286 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	287 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	288 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	289 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	290 if (first_match == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	291 first_match = node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	292 else
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 multiple_matches = true;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	295 break;
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 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	298 if (multiple_matches)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	299 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	300 /* 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	301 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	302 end_index -= start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	303 node = list->root.next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	304 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	305 node = node->next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	306
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	307 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	308 end_index > 0;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	309 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	310 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	311 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	312 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	313 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	314 return node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	315 /* 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	316 >= end_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	317 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	318 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	319 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	320 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	321 if (start_index > 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	322 /* 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	323 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	324 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	325 if (node == first_match)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	326 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	327 if (--start_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	328 break;
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 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	331 /* 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	332 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	333 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	334 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	335 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	336 if (node == first_match)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	337 return NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	338 if (--end_index == 0)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	339 break;
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 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	342 return first_match;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	343 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	344 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	345 #else
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	346 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	347 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	348
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	349 end_index -= start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	350 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	351 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	352
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	353 if (equals != NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	354 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	355 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	356 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	357 return node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	358 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	359 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	360 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	361 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	362 if (elt == node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	363 return node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	364 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	365 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 #endif
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	367 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	369
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 static size_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	371 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	372 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	373 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	374 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	375
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	376 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	377 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	378 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	379 {
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 #if WITH_HASHTABLE
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	381 /* 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	382 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	383 its index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	384 size_t hashcode =
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	385 (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	386 ? 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	387 : (size_t)(uintptr_t) elt);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	388 size_t index = hashcode % list->table_size;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	389 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	390 gl_list_node_t node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	391
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	392 /* 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	393 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	394 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	395 /* 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	396 for (node = (gl_list_node_t) list->table[index];
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	397 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	398 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	399 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	400 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	401 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	402 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	403 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	404 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	405 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	406 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	407 /* 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	408 bool multiple_matches = false;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	409 gl_list_node_t first_match = NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	410
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	411 for (node = (gl_list_node_t) list->table[index];
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	412 node != NULL;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	413 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	414 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	415 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	416 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	417 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	418 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	419 if (first_match == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	420 first_match = node;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	421 else
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 multiple_matches = true;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	424 break;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	425 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	426 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	427 if (multiple_matches)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	428 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	429 /* 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	430 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	431 size_t index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	432
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	433 index = start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	434 node = list->root.next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	435 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	436 node = node->next;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	437
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	438 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	439 index < end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	440 node = node->next, index++)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	441 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	442 && (equals != NULL
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	443 ? equals (elt, node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	444 : elt == node->value))
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	445 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	446 /* 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	447 >= end_index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	448 return (size_t)(-1);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	449 }
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	450 node = first_match;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	451 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	452
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	453 /* 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	454 if (node == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	455 return (size_t)(-1);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	456 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	457 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	458 size_t index = 0;
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 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	461 index++;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	462
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	463 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	464 return index;
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 return (size_t)(-1);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	467 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	468 #else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	469 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	470 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	471 gl_list_node_t node = list->root.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 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	474 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	475
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	476 if (equals != NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	477 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	478 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	479 index < end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	480 node = node->next, index++)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	481 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	482 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	483 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	484 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	485 {
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	486 for (;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	487 index < end_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	488 node = node->next, index++)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	489 if (elt == node->value)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	490 return index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	491 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	492 return (size_t)(-1);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	493 #endif
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	494 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	495 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	496
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	497 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	498 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	499 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	500 gl_list_node_t node =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	501 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	502
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	503 ASYNCSAFE(const void *) node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	504 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	505 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	506 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	507 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 : (size_t)(uintptr_t) node->value);
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 hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	511 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	512 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	513
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 /* Add node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 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	516 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	517 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	518 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	519 list->count++;
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 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	522 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	523 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	524
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	526 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	527
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	528 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	529 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	530 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 gl_list_node_t node =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	532 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	533
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	534 ASYNCSAFE(const void *) node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	535 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	536 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	537 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	539 : (size_t)(uintptr_t) node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	540
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	541 /* Add node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	542 add_to_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	543 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	544
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	545 /* 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	546 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	547 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	548 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	549 list->root.prev = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	550 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	551
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	552 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	553 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	554 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	555
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	556 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	557 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	558
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 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	561 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	562 gl_list_node_t new_node =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	564
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	565 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	568 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	571
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	572 /* Add new_node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	573 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	575
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	576 /* 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	577 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	578 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	579 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	580 node->prev = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	581 list->count++;
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 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	584 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	585 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	586
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	587 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	588 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	589
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	590 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	591 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	592 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	593 gl_list_node_t new_node =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	594 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	595
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	596 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	597 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	598 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	599 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	601 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	602
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	603 /* Add new_node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	604 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 #endif
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 /* Add new_node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	608 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	609 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	610 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	611 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	612 list->count++;
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 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	615 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	616 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	617
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	618 return 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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	621 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	622 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	623 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	624 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	625 gl_list_node_t new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	626
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	627 if (!(position <= count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	628 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	629 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	630
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	631 new_node =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	632 (struct gl_list_node_impl *) xmalloc (sizeof (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	633 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	634 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	635 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	636 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	637 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	638 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	639
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	640 /* Add new_node to the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	641 add_to_bucket (list, new_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	642 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	643
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 /* Add new_node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	645 if (position <= (count / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	646 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	647 gl_list_node_t node;
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 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	650 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	651 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	652 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	653 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	654 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	655 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	656 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	657 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	658 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	659 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	660
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	661 position = count - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	662 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	663 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	664 node = node->prev;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	665 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	666 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	667 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	668 node->prev = 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 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	671
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	672 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	674 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	675
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	676 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	677 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	678
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	679 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	680 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	681 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	682 gl_list_node_t prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	683 gl_list_node_t next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	684
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	685 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	686 /* Remove node from the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	687 remove_from_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	688 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	689
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	690 /* Remove node from the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	691 prev = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	692 next = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	693
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	694 ASYNCSAFE(gl_list_node_t) prev->next = next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	695 next->prev = prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	696 list->count--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	697
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	698 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	699 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	700 }
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 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	703 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	704 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	705 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	706 gl_list_node_t removed_node;
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 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	709 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	710 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	711 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	712 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	713 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	714 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	715 gl_list_node_t after_removed;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	716
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	717 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	718 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	719 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	720 removed_node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	721 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	722 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	723 after_removed->prev = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	724 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	725 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	726 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	727 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	728 gl_list_node_t before_removed;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	729
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	730 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	731 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	732 for (; position > 0; position--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	733 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	734 removed_node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	735 before_removed = node->prev->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	736 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	737 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	738 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	739 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	740 remove_from_bucket (list, removed_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	741 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	742 list->count--;
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 free (removed_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	745 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	746 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	747
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	748 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	749 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	750 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	751 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	752
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	753 if (node != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	754 return gl_linked_remove_node (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	755 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	756 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	757 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	758
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	759 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	760 gl_linked_list_free (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	761 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	762 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	763
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	764 for (node = list->root.next; node != &list->root; )
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	765 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	766 gl_list_node_t next = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	767 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	768 node = next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	769 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	770 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	771 free (list->table);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	772 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	773 free (list);
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	776 /* --------------------- gl_list_iterator_t Data Type --------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	777
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	778 static gl_list_iterator_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	779 gl_linked_iterator (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	780 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	781 gl_list_iterator_t result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	782
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	783 result.vtable = list->base.vtable;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	784 result.list = list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	785 result.p = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	786 result.q = &list->root;
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	787 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	788 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	789 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	790 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	791 #endif
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	792
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	793 return result;
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	796 static gl_list_iterator_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	797 gl_linked_iterator_from_to (gl_list_t list,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	798 size_t start_index, size_t end_index)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	799 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	800 gl_list_iterator_t result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	801 size_t n1, n2, n3;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	802
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	803 if (!(start_index <= end_index && end_index <= list->count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	804 /* Invalid arguments. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	805 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	806 result.vtable = list->base.vtable;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	807 result.list = list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	808 n1 = start_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	809 n2 = end_index - start_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	810 n3 = list->count - end_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	811 /* 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	812 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	813 if (n1 > n2 && n1 > n3)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	814 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	815 /* n1 is the maximum, use n2 and n3. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	816 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	817 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	818
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	819 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	820 for (i = n3; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	821 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	822 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	823 for (i = n2; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	824 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	825 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	826 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	827 else if (n2 > n3)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	828 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	829 /* n2 is the maximum, use n1 and n3. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	830 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	831 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	832
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	833 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	834 for (i = n1; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	835 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	836 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	837
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	838 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	839 for (i = n3; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	840 node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	841 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	842 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	843 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	844 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	845 /* n3 is the maximum, use n1 and n2. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	846 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	847 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	848
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	849 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	850 for (i = n1; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	851 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	852 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	853 for (i = n2; i > 0; i--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	854 node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	855 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	856 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	857
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	858 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	859 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	860 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	861 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	862 #endif
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	863
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	864 return result;
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	867 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	868 gl_linked_iterator_next (gl_list_iterator_t *iterator,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	869 const void *eltp, gl_list_node_t nodep)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	870 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	871 if (iterator->p != iterator->q)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	872 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	873 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	874 *eltp = node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	875 if (nodep != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	876 *nodep = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	877 iterator->p = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	878 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	879 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	880 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	881 return false;
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	884 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	885 gl_linked_iterator_free (gl_list_iterator_t *iterator)
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	889 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	890
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	891 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	892 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	893 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	894 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	895 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	896
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	897 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	898 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	899 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	900
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	901 if (cmp > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	902 break;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	903 if (cmp == 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	904 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	905 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	906 return NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	907 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	908
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	909 static gl_list_node_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	910 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	911 gl_listelement_compar_fn compar,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	912 size_t low, size_t high,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	913 const void *elt)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	914 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	915 size_t count = list->count;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	916
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	917 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	918 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	919 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	920
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	921 high -= low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	922 if (high > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	923 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	924 /* Here we know low < count. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	925 size_t position = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	926 gl_list_node_t node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	927
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	928 if (position <= ((count - 1) / 2))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	929 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	930 node = list->root.next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	931 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	932 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	933 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	934 else
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	935 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	936 position = count - 1 - position;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	937 node = list->root.prev;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	938 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	939 node = node->prev;
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
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	942 do
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	943 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	944 int cmp = compar (node->value, elt);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	945
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	946 if (cmp > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	947 break;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	948 if (cmp == 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	949 return node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	950 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	951 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	952 while (--high > 0);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	953 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	954 return NULL;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	955 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	956
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	957 static size_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	958 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	959 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	960 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	961 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	962 size_t index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	963
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	964 for (node = list->root.next, index = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	965 node != &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	966 node = node->next, index++)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	967 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	968 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	969
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	970 if (cmp > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	971 break;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	972 if (cmp == 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	973 return index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	974 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	975 return (size_t)(-1);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	976 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	977
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	978 static size_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	979 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	980 gl_listelement_compar_fn compar,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	981 size_t low, size_t high,
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	982 const void *elt)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	983 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	984 size_t count = list->count;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	985
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	986 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	987 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	988 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	989
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	990 high -= low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	991 if (high > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	992 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	993 /* Here we know low < count. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	994 size_t index = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	995 size_t position = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	996 gl_list_node_t node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	997
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	998 if (position <= ((count - 1) / 2))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	999 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1000 node = list->root.next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1001 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1002 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1003 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1004 else
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1005 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1006 position = count - 1 - position;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1007 node = list->root.prev;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1008 for (; position > 0; position--)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1009 node = node->prev;
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
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1012 do
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1013 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1014 int cmp = compar (node->value, elt);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1015
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1016 if (cmp > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1017 break;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1018 if (cmp == 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1019 return index;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1020 node = node->next;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1021 index++;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1022 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1023 while (--high > 0);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1024 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1025 return (size_t)(-1);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1026 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1027
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1028 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1029 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	1030 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1031 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1032 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1033
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1034 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	1035 if (compar (node->value, elt) >= 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1036 return gl_linked_add_before (list, node, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1037 return gl_linked_add_last (list, elt);
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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1040 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1041 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	1042 const void *elt)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1043 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1044 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1045
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1046 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	1047 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1048 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1049
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1050 if (cmp > 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1051 break;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1052 if (cmp == 0)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1053 return gl_linked_remove_node (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1054 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1055 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1056 }

Mercurial > hg > octave-jordi > gnulib-hg

annotate lib/gl_anylinked_list2.h @ 7410:9704ff2cbdfe