octave-jordi/gnulib-hg: lib/gl_anylinked

annotate lib/gl_anylinked_list2.h @ 14379:2330aac2ae54

maint: adjust cpp indentation to reflect nesting depth I.e., in a block of code that begins with an unnested "#if", put one space between the "#" in column 1 and following token. For example, -#include <sys/vfs.h> +# include <sys/vfs.h> Do this only in .c files that are part of a module I maintain. * lib/linkat.c: Filter through cppi. * lib/nanosleep.c: Likewise. * lib/openat.c: Likewise. * lib/openat-die.c: Likewise. * lib/dup3.c: Likewise. * lib/fchownat.c: Likewise. * lib/flock.c: Likewise. * lib/fsync.c: Likewise. * lib/fts.c: Likewise. * lib/getpass.c: Likewise. * lib/gettimeofday.c: Likewise. * lib/userspec.c: Likewise. * Makefile (sc_cpp_indent_check): New rule, to check this.

author	Jim Meyering <meyering@redhat.com>
date	Sun, 20 Feb 2011 23:02:43 +0100
parents	97fc9a21a8fb
children	8250f2777afc

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.
14079 97fc9a21a8fb maint: update almost all copyright ranges to include 2011 Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	2 Copyright (C) 2006-2011 Free Software Foundation, Inc.
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	4
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8438 diff changeset	5 This program is free software: you can redistribute it and/or modify
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	6 it under the terms of the GNU General Public License as published by
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8438 diff changeset	7 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8438 diff changeset	8 (at your option) any later version.
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU General Public License
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8438 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	18 /* Common code of gl_linked_list.c and gl_linkedhash_list.c. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	20 /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	21 a way that a gl_list_t data structure may be used from within a signal
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	22 handler. The operations allowed in the signal handler are:
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	23 gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	24 The list and node fields that are therefore accessed from the signal handler
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	25 are:
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	26 list->root, node->next, node->value.
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	27 We are careful to make modifications to these fields only in an order
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	28 that maintains the consistency of the list data structure at any moment,
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	29 and we use 'volatile' assignments to prevent the compiler from reordering
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	30 such assignments. */
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	31 #ifdef SIGNAL_SAFE_LIST
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	32 # define ASYNCSAFE(type) (volatile type )&
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	33 #else
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	34 # define ASYNCSAFE(type)
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	35 #endif
8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	36
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 /* -------------------------- gl_list_t Data Type -------------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	38
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 static gl_list_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	40 gl_linked_nx_create_empty (gl_list_implementation_t implementation,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	41 gl_listelement_equals_fn equals_fn,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	42 gl_listelement_hashcode_fn hashcode_fn,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	43 gl_listelement_dispose_fn dispose_fn,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	44 bool allow_duplicates)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	46 struct gl_list_impl *list =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	47 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	48
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	49 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	50 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	51
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	54 list->base.hashcode_fn = hashcode_fn;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	55 list->base.dispose_fn = dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 list->base.allow_duplicates = allow_duplicates;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 list->table_size = 11;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	59 list->table =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	60 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	61 if (list->table == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	62 goto fail;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	63 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 list->root.next = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 list->root.prev = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 list->count = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	67
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 return list;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	69
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	70 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	71 fail:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	72 free (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	73 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	74 #endif
6973 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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 static gl_list_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	78 gl_linked_nx_create (gl_list_implementation_t implementation,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	79 gl_listelement_equals_fn equals_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	80 gl_listelement_hashcode_fn hashcode_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	81 gl_listelement_dispose_fn dispose_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	82 bool allow_duplicates,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	83 size_t count, const void **contents)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	85 struct gl_list_impl *list =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	86 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 gl_list_node_t tail;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	88
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	89 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	90 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	91
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 list->base.vtable = implementation;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 list->base.equals_fn = equals_fn;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 list->base.hashcode_fn = hashcode_fn;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	95 list->base.dispose_fn = dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 list->base.allow_duplicates = allow_duplicates;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 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	100 if (estimate < 10)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 estimate = 10;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	102 list->table_size = next_prime (estimate);
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	103 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	104 goto fail1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	105 list->table =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	106 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	107 if (list->table == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	108 goto fail1;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 list->count = count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 tail = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	113 for (; count > 0; contents++, count--)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	115 gl_list_node_t node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	116 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	117
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	118 if (node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	119 goto fail2;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	120
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 node->value = *contents;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	123 node->h.hashcode =
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	124 (list->base.hashcode_fn != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	125 ? list->base.hashcode_fn (node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	126 : (size_t)(uintptr_t) node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	127
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 /* Add node to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	129 if (add_to_bucket (list, node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	130 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	131 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	132 goto fail2;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	133 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	134 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	135
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 /* Add node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	137 node->prev = tail;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 tail->next = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 tail = 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 tail->next = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	142 list->root.prev = tail;
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 return list;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	145
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	146 fail2:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	147 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	148 gl_list_node_t node;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	149
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	150 for (node = tail; node != &list->root; )
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	151 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	152 gl_list_node_t prev = node->prev;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	153
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	154 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	155 node = prev;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	156 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	157 }
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	158 #if WITH_HASHTABLE
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	159 free (list->table);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	160 fail1:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	161 #endif
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	162 free (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	163 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	165
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 static size_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 gl_linked_size (gl_list_t list)
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 return list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	170 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	171
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	172 static const void *
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	173 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	174 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	175 return node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	176 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	177
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	178 static int
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	179 gl_linked_node_nx_set_value (gl_list_t list, gl_list_node_t node,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	180 const void *elt)
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	181 {
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	182 #if WITH_HASHTABLE
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	183 if (elt != node->value)
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	184 {
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	185 size_t new_hashcode =
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	186 (list->base.hashcode_fn != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	187 ? list->base.hashcode_fn (elt)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	188 : (size_t)(uintptr_t) elt);
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	189
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	190 if (new_hashcode != node->h.hashcode)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	191 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	192 remove_from_bucket (list, node);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	193 node->value = elt;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	194 node->h.hashcode = new_hashcode;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	195 if (add_to_bucket (list, node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	196 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	197 /* Out of memory. We removed node from a bucket but cannot add
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	198 it to another bucket. In order to avoid inconsistencies, we
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	199 must remove node entirely from the list. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	200 gl_list_node_t before_removed = node->prev;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	201 gl_list_node_t after_removed = node->next;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	202 ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	203 after_removed->prev = before_removed;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	204 list->count--;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	205 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	206 return -1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	207 }
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	208 }
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	209 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	210 node->value = elt;
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	211 }
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	212 #else
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	213 node->value = elt;
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	214 #endif
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	215 return 0;
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	216 }
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	217
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	218 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	219 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	220 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	221 return (node->next != &list->root ? node->next : NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	222 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	223
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	224 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	225 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	226 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	227 return (node->prev != &list->root ? node->prev : NULL);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	228 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	229
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 static const void *
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	231 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	232 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	233 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	234 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	235
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	236 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	237 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	239 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	240 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	241 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	242 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	243 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	244 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	245 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	246 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	247 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	248 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 node = list->root.prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	250 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	251 node = node->prev;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	253 return node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	254 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	255
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	257 gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	258 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	259 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	260 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	261
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	262 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	263 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	264 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	265 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	266 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	267 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	269 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	270 node = node->next;
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 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	273 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	274 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 node = list->root.prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	276 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	277 node = node->prev;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	278 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	279 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 if (elt != node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	281 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	282 size_t new_hashcode =
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	283 (list->base.hashcode_fn != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	284 ? list->base.hashcode_fn (elt)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	285 : (size_t)(uintptr_t) elt);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	286
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	287 if (new_hashcode != node->h.hashcode)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	288 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	289 remove_from_bucket (list, node);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	290 node->value = elt;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	291 node->h.hashcode = new_hashcode;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	292 if (add_to_bucket (list, node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	293 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	294 /* Out of memory. We removed node from a bucket but cannot add
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	295 it to another bucket. In order to avoid inconsistencies, we
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	296 must remove node entirely from the list. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	297 gl_list_node_t before_removed = node->prev;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	298 gl_list_node_t after_removed = node->next;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	299 ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	300 after_removed->prev = before_removed;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	301 list->count--;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	302 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	303 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	304 }
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	305 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	306 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	307 node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	308 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	309 #else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	310 node->value = elt;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	311 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	312 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	313 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	314
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	315 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	316 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	317 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	318 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	319 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	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 <= 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	322 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	323 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	324 {
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	325 #if WITH_HASHTABLE
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	326 size_t hashcode =
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	327 (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	328 ? 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	329 : (size_t)(uintptr_t) elt);
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	330 size_t bucket = hashcode % list->table_size;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	331 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	332
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	333 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	334 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	335 /* Look for the first match in the hash bucket. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	336 gl_list_node_t found = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	337 gl_list_node_t node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	338
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	339 for (node = (gl_list_node_t) list->table[bucket];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	340 node != NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	341 node = (gl_list_node_t) node->h.hash_next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	342 if (node->h.hashcode == hashcode
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	343 && (equals != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	344 ? equals (elt, node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	345 : elt == node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	346 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	347 found = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	348 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	349 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	350 if (start_index > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	351 /* Look whether found's index is < start_index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	352 for (node = list->root.next; ; node = node->next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	353 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	354 if (node == found)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	355 return NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	356 if (--start_index == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	357 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	358 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	359 if (end_index < count)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	360 /* Look whether found's index is >= end_index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	361 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	362 end_index = count - end_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	363 for (node = list->root.prev; ; node = node->prev)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	364 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	365 if (node == found)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	366 return NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	367 if (--end_index == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	368 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	369 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	370 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	371 return found;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	372 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	373 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	374 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	375 /* Look whether there is more than one match in the hash bucket. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	376 bool multiple_matches = false;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	377 gl_list_node_t first_match = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	378 gl_list_node_t node;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	379
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	380 for (node = (gl_list_node_t) list->table[bucket];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	381 node != NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	382 node = (gl_list_node_t) node->h.hash_next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	383 if (node->h.hashcode == hashcode
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	384 && (equals != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	385 ? equals (elt, node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	386 : elt == node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	387 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	388 if (first_match == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	389 first_match = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	390 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	391 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	392 multiple_matches = true;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	393 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	394 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	395 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	396 if (multiple_matches)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	397 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	398 /* We need the match with the smallest index. But we don't have
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	399 a fast mapping node -> index. So we have to walk the list. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	400 end_index -= start_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	401 node = list->root.next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	402 for (; start_index > 0; start_index--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	403 node = node->next;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	404
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	405 for (;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	406 end_index > 0;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	407 node = node->next, end_index--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	408 if (node->h.hashcode == hashcode
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	409 && (equals != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	410 ? equals (elt, node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	411 : elt == node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	412 return node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	413 /* The matches must have all been at indices < start_index or
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	414 >= end_index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	415 return NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	416 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	417 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	418 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	419 if (start_index > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	420 /* Look whether first_match's index is < start_index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	421 for (node = list->root.next; node != &list->root; node = node->next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	422 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	423 if (node == first_match)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	424 return NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	425 if (--start_index == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	426 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	427 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	428 if (end_index < list->count)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	429 /* Look whether first_match's index is >= end_index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	430 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	431 end_index = list->count - end_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	432 for (node = list->root.prev; ; node = node->prev)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	433 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	434 if (node == first_match)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	435 return NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	436 if (--end_index == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	437 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	438 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	439 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	440 return first_match;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	441 }
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	442 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 #else
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	444 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	445 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	446
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	447 end_index -= start_index;
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	448 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	449 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	450
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	451 if (equals != NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	452 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	453 for (; end_index > 0; node = node->next, end_index--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	454 if (equals (elt, node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	455 return node;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	456 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	457 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	458 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	459 for (; end_index > 0; node = node->next, end_index--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	460 if (elt == node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	461 return node;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	462 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	463 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	464 #endif
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	465 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	466 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	467
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	468 static size_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	469 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	470 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	471 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	472 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	473
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	474 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	475 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	476 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	477 {
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	478 #if WITH_HASHTABLE
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	479 /* 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	480 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	481 its index. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	482 size_t hashcode =
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	483 (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	484 ? 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	485 : (size_t)(uintptr_t) elt);
7466 c9738ed4c499 Avoid using the variable name 'index' for two completely different things. Bruno Haible <bruno@clisp.org> parents: 7410 diff changeset	486 size_t bucket = hashcode % list->table_size;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	487 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	488 gl_list_node_t node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	489
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	490 /* 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	491 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	492 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	493 /* Look for the first match in the hash bucket. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	494 for (node = (gl_list_node_t) list->table[bucket];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	495 node != NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	496 node = (gl_list_node_t) node->h.hash_next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	497 if (node->h.hashcode == hashcode
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	498 && (equals != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	499 ? equals (elt, node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	500 : elt == node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	501 break;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	502 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	503 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	504 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	505 /* Look whether there is more than one match in the hash bucket. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	506 bool multiple_matches = false;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	507 gl_list_node_t first_match = NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	508
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	509 for (node = (gl_list_node_t) list->table[bucket];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	510 node != NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	511 node = (gl_list_node_t) node->h.hash_next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	512 if (node->h.hashcode == hashcode
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	513 && (equals != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	514 ? equals (elt, node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	515 : elt == node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	516 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	517 if (first_match == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	518 first_match = node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	519 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	520 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	521 multiple_matches = true;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	522 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	523 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	524 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	525 if (multiple_matches)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	526 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	527 /* We need the match with the smallest index. But we don't have
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	528 a fast mapping node -> index. So we have to walk the list. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	529 size_t index;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	530
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	531 index = start_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	532 node = list->root.next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	533 for (; start_index > 0; start_index--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	534 node = node->next;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	535
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	536 for (;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	537 index < end_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	538 node = node->next, index++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	539 if (node->h.hashcode == hashcode
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	540 && (equals != NULL
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	541 ? equals (elt, node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	542 : elt == node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	543 return index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	544 /* The matches must have all been at indices < start_index or
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	545 >= end_index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	546 return (size_t)(-1);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	547 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	548 node = first_match;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	549 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	550
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	551 /* 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	552 if (node == NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	553 return (size_t)(-1);
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	554 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	555 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	556 size_t index = 0;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	557
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	558 for (; node->prev != &list->root; node = node->prev)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	559 index++;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	560
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	561 if (index >= start_index && index < end_index)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	562 return index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	563 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	564 return (size_t)(-1);
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	565 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	566 #else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	567 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	568 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	569 gl_list_node_t node = list->root.next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	570
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	571 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	572 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	573
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	574 if (equals != NULL)
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	575 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	576 for (;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	577 index < end_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	578 node = node->next, index++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	579 if (equals (elt, node->value))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	580 return index;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	581 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	582 else
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	583 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	584 for (;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	585 index < end_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	586 node = node->next, index++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	587 if (elt == node->value)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	588 return index;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	589 }
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	590 return (size_t)(-1);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	591 #endif
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	592 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	593 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	594
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	595 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	596 gl_linked_nx_add_first (gl_list_t list, const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	597 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	598 gl_list_node_t node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	599 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	600
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	601 if (node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	602 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	603
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	604 ASYNCSAFE(const void *) node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	606 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	607 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	608 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	609 : (size_t)(uintptr_t) node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	610
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	611 /* Add node to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	612 if (add_to_bucket (list, node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	613 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	614 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	615 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	616 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	617 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	618
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	619 /* Add node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	620 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	621 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	622 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	623 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	624 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	625
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	626 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	627 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	628 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	629
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	630 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	631 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	632
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	633 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	634 gl_linked_nx_add_last (gl_list_t list, const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	635 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	636 gl_list_node_t node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	637 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	638
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	639 if (node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	640 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	641
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	642 ASYNCSAFE(const void *) node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	643 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	645 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	646 ? list->base.hashcode_fn (node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	647 : (size_t)(uintptr_t) node->value);
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 /* Add node to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	650 if (add_to_bucket (list, node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	651 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	652 free (node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	653 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	654 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	655 #endif
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 /* 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	658 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	659 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	660 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	661 list->root.prev = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	662 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	663
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	664 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	665 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	666 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	667
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	668 return node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	669 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	670
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	671 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	672 gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	674 gl_list_node_t new_node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	675 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	676
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	677 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	678 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	679
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	680 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	681 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	682 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	683 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	684 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	685 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	686
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	687 /* Add new_node to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	688 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	689 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	690 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	691 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	692 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	693 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	694
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	695 /* 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	696 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	697 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	698 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	699 node->prev = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	700 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	701
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	702 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	703 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	704 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	705
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	706 return new_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
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	709 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	710 gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	711 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	712 gl_list_node_t new_node =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	713 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	714
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	715 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	716 return NULL;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	717
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	718 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	719 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	720 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	721 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	722 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	723 : (size_t)(uintptr_t) new_node->value);
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 /* Add new_node to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	726 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	727 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	728 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	729 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	730 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	731 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	732
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	733 /* Add new_node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	734 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	735 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	736 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	737 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	738 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	739
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	740 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	741 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	742 #endif
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 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	745 }
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 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	748 gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	749 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	750 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	751 gl_list_node_t new_node;
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 (!(position <= count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	754 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	755 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	756
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	757 new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	758 if (new_node == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	759 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	760
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	761 ASYNCSAFE(const void *) new_node->value = elt;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	762 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	763 new_node->h.hashcode =
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	764 (list->base.hashcode_fn != NULL
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	765 ? list->base.hashcode_fn (new_node->value)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	766 : (size_t)(uintptr_t) new_node->value);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	767
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	768 /* Add new_node to the hash table. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	769 if (add_to_bucket (list, new_node) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	770 {
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	771 free (new_node);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	772 return NULL;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	773 }
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	774 #endif
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 /* Add new_node to the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	777 if (position <= (count / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	778 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	779 gl_list_node_t node;
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 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	782 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	783 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	784 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	785 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	786 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	787 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	788 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	789 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	790 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	791 gl_list_node_t node;
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 position = count - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	794 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	795 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	796 node = node->prev;
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	797 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	798 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	799 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	800 node->prev = new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	801 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	802 list->count++;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	803
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	804 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	805 hash_resize_after_add (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	806 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	807
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	808 return new_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	809 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	810
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	811 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	812 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	813 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	814 gl_list_node_t prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	815 gl_list_node_t next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	816
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	817 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	818 /* Remove node from the hash table. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	819 remove_from_bucket (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	820 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	821
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	822 /* Remove node from the list. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	823 prev = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	824 next = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	825
7042 8da38783b9e0 Make it possible to use the list in signal-handlers. Bruno Haible <bruno@clisp.org> parents: 6973 diff changeset	826 ASYNCSAFE(gl_list_node_t) prev->next = next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	827 next->prev = prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	828 list->count--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	829
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	830 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	831 list->base.dispose_fn (node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	832 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	833 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	834 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	835
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	836 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	837 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	838 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	839 size_t count = list->count;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	840 gl_list_node_t removed_node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	841
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	842 if (!(position < count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	843 /* Invalid argument. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	844 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	845 /* Here we know count > 0. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	846 if (position <= ((count - 1) / 2))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	847 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	848 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	849 gl_list_node_t after_removed;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	850
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	851 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	852 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	853 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	854 removed_node = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	855 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	856 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	857 after_removed->prev = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	858 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	859 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	860 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	861 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	862 gl_list_node_t before_removed;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	863
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	864 position = count - 1 - position;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	865 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	866 for (; position > 0; position--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	867 node = node->prev;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	868 removed_node = node->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	869 before_removed = node->prev->prev;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	870 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	871 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	872 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	873 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	874 remove_from_bucket (list, removed_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	875 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	876 list->count--;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	877
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	878 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	879 list->base.dispose_fn (removed_node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	880 free (removed_node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	881 return true;
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 bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	885 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	886 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	887 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	888
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	889 if (node != NULL)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	890 return gl_linked_remove_node (list, node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	891 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	892 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	893 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	894
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	895 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	896 gl_linked_list_free (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	897 {
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	898 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	899 gl_list_node_t node;
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 for (node = list->root.next; node != &list->root; )
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	902 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	903 gl_list_node_t next = node->next;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7615 diff changeset	904 if (dispose != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	905 dispose (node->value);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	906 free (node);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	907 node = next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	908 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	909 #if WITH_HASHTABLE
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	910 free (list->table);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	911 #endif
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	912 free (list);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	913 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	914
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	915 /* --------------------- gl_list_iterator_t Data Type --------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	916
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	917 static gl_list_iterator_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	918 gl_linked_iterator (gl_list_t list)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	919 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	920 gl_list_iterator_t result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	921
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	922 result.vtable = list->base.vtable;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	923 result.list = list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	924 result.p = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	925 result.q = &list->root;
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	926 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	927 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	928 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	929 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	930 #endif
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	931
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	932 return result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	933 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	934
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	935 static gl_list_iterator_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	936 gl_linked_iterator_from_to (gl_list_t list,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	937 size_t start_index, size_t end_index)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	938 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	939 gl_list_iterator_t result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	940 size_t n1, n2, n3;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	941
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	942 if (!(start_index <= end_index && end_index <= list->count))
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	943 /* Invalid arguments. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	944 abort ();
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	945 result.vtable = list->base.vtable;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	946 result.list = list;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	947 n1 = start_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	948 n2 = end_index - start_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	949 n3 = list->count - end_index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	950 /* 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	951 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	952 if (n1 > n2 && n1 > n3)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	953 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	954 /* n1 is the maximum, use n2 and n3. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	955 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	956 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	957
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	958 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	959 for (i = n3; i > 0; i--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	960 node = node->prev;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	961 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	962 for (i = n2; i > 0; i--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	963 node = node->prev;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	964 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	965 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	966 else if (n2 > n3)
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 /* n2 is the maximum, use n1 and n3. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	969 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	970 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	971
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	972 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	973 for (i = n1; i > 0; i--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	974 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	975 result.p = node;
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 node = &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	978 for (i = n3; i > 0; i--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	979 node = node->prev;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	980 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	981 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	982 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	983 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	984 /* n3 is the maximum, use n1 and n2. */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	985 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	986 size_t i;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	987
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	988 node = list->root.next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	989 for (i = n1; i > 0; i--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	990 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	991 result.p = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	992 for (i = n2; i > 0; i--)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	993 node = node->next;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	994 result.q = node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	995 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	996
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	997 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	998 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	999 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	1000 result.count = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	1001 #endif
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7042 diff changeset	1002
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1003 return result;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1004 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1005
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1006 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1007 gl_linked_iterator_next (gl_list_iterator_t *iterator,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1008 const void *eltp, gl_list_node_t nodep)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1009 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1010 if (iterator->p != iterator->q)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1011 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1012 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	1013 *eltp = node->value;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1014 if (nodep != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1015 *nodep = node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1016 iterator->p = node->next;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1017 return true;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1018 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1019 else
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1020 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1021 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1022
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1023 static void
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1024 gl_linked_iterator_free (gl_list_iterator_t *iterator)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1025 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1026 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1027
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1028 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1029
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1030 static gl_list_node_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1031 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1032 const void *elt)
6973 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 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1035
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1036 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	1037 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1038 int cmp = compar (node->value, elt);
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 if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1041 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1042 if (cmp == 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1043 return node;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1044 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1045 return NULL;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1046 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1047
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1048 static gl_list_node_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1049 gl_linked_sortedlist_search_from_to (gl_list_t list,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1050 gl_listelement_compar_fn compar,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1051 size_t low, size_t high,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1052 const void *elt)
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1053 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1054 size_t count = list->count;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1055
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1056 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1057 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1058 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1059
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1060 high -= low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1061 if (high > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1062 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1063 /* Here we know low < count. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1064 size_t position = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1065 gl_list_node_t node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1066
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1067 if (position <= ((count - 1) / 2))
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1068 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1069 node = list->root.next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1070 for (; position > 0; position--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1071 node = node->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1072 }
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1073 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1074 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1075 position = count - 1 - position;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1076 node = list->root.prev;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1077 for (; position > 0; position--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1078 node = node->prev;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1079 }
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1080
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1081 do
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1082 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1083 int cmp = compar (node->value, elt);
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1084
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1085 if (cmp > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1086 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1087 if (cmp == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1088 return node;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1089 node = node->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1090 }
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1091 while (--high > 0);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1092 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1093 return NULL;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1094 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1095
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1096 static size_t
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1097 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1098 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1099 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1100 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1101 size_t index;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1102
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1103 for (node = list->root.next, index = 0;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1104 node != &list->root;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1105 node = node->next, index++)
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1106 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1107 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1108
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1109 if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1110 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1111 if (cmp == 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1112 return index;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1113 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1114 return (size_t)(-1);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1115 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1116
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1117 static size_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1118 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1119 gl_listelement_compar_fn compar,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1120 size_t low, size_t high,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1121 const void *elt)
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1122 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1123 size_t count = list->count;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1124
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1125 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1126 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1127 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1128
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1129 high -= low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1130 if (high > 0)
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1131 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1132 /* Here we know low < count. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1133 size_t index = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1134 size_t position = low;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1135 gl_list_node_t node;
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1136
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1137 if (position <= ((count - 1) / 2))
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1138 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1139 node = list->root.next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1140 for (; position > 0; position--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1141 node = node->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1142 }
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1143 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1144 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1145 position = count - 1 - position;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1146 node = list->root.prev;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1147 for (; position > 0; position--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1148 node = node->prev;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1149 }
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1150
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1151 do
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1152 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1153 int cmp = compar (node->value, elt);
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1154
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1155 if (cmp > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1156 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1157 if (cmp == 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1158 return index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1159 node = node->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1160 index++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1161 }
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1162 while (--high > 0);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1163 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1164 return (size_t)(-1);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1165 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	1166
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1167 static gl_list_node_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	1168 gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	1169 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1170 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1171 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1172
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1173 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	1174 if (compar (node->value, elt) >= 0)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	1175 return gl_linked_nx_add_before (list, node, elt);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	1176 return gl_linked_nx_add_last (list, elt);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1177 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1178
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1179 static bool
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1180 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1181 const void *elt)
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1182 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1183 gl_list_node_t node;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1184
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1185 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	1186 {
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1187 int cmp = compar (node->value, elt);
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1188
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1189 if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1190 break;
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1191 if (cmp == 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	1192 return gl_linked_remove_node (list, node);
6973 de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1193 }
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1194 return false;
de9a21fc207a Common code several concrete list implementations. Bruno Haible <bruno@clisp.org> parents: diff changeset	1195 }

Mercurial > hg > octave-jordi > gnulib-hg

annotate lib/gl_anylinked_list2.h @ 14379:2330aac2ae54