gnulib: lib/gl_carray_list.c annotate

annotate lib/gl_carray_list.c @ 40186:8964917f9574

autoupdate

author	Karl Berry <karl@freefriends.org>
date	Mon, 18 Feb 2019 08:02:49 -0800
parents	b06060465f09
children

rev	line source
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Sequential list data type implemented by a circular array.
40057 b06060465f09 maint: Run 'make update-copyright' Paul Eggert <eggert@cs.ucla.edu> parents: 19484 diff changeset	2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
e6c62f234610 Sequential list data type implemented by a circular array. 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
6977 e6c62f234610 Sequential list data type implemented by a circular array. 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.
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU General Public License
19190 9759915b2aca all: prefer https: URLs Paul Eggert <eggert@cs.ucla.edu> parents: 18626 diff changeset	16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
7304 1c4ed7637c24 Include <config.h> unconditionally. Bruno Haible <bruno@clisp.org> parents: 6977 diff changeset	18 #include <config.h>
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 /* Specification. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 #include "gl_carray_list.h"
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	22
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 #include <stdlib.h>
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 /* Get memcpy. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 #include <string.h>
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	26
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 /* Checked size_t computations. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 #include "xsize.h"
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	29
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 #ifndef uintptr_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	31 # define uintptr_t unsigned long
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 #endif
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	33
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 /* -------------------------- gl_list_t Data Type -------------------------- */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	35
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 /* Concrete gl_list_impl type, valid for this file only. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 struct gl_list_impl
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 struct gl_list_impl_base base;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 /* An array of ALLOCATED elements, of which the elements
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 OFFSET, (OFFSET + 1) % ALLOCATED, ..., (OFFSET + COUNT - 1) % ALLOCATED
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 are used. 0 <= COUNT <= ALLOCATED. Either OFFSET = ALLOCATED = 0 or
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 0 <= OFFSET < ALLOCATED. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 const void **elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 size_t offset;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 size_t count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 size_t allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 };
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	49
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 indices + 1. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	54
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 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	56 gl_carray_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	57 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	58 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	59 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	60 bool allow_duplicates)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	61 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	62 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	63 (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	64
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	65 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	66 return NULL;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	67
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 list->base.vtable = implementation;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 list->base.equals_fn = equals_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 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: 7603 diff changeset	71 list->base.dispose_fn = dispose_fn;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 list->base.allow_duplicates = allow_duplicates;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 list->elements = NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 list->offset = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 list->count = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 list->allocated = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	77
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 return list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	79 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	80
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	81 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	82 gl_carray_nx_create (gl_list_implementation_t implementation,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	83 gl_listelement_equals_fn equals_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	84 gl_listelement_hashcode_fn hashcode_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	85 gl_listelement_dispose_fn dispose_fn,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	86 bool allow_duplicates,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	87 size_t count, const void **contents)
6977 e6c62f234610 Sequential list data type implemented by a circular array. 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 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	90 (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	91
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	92 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	93 return NULL;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	94
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 list->base.vtable = implementation;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 list->base.equals_fn = equals_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 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: 7603 diff changeset	98 list->base.dispose_fn = dispose_fn;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	99 list->base.allow_duplicates = allow_duplicates;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 if (count > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	102 if (size_overflow_p (xtimes (count, sizeof (const void *))))
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	103 goto fail;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	104 list->elements = (const void *) malloc (count sizeof (const void *));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	105 if (list->elements == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	106 goto fail;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 memcpy (list->elements, contents, count * sizeof (const void *));
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	108 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 list->elements = NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 list->offset = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 list->count = count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	113 list->allocated = count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	114
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 return list;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	116
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	117 fail:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	118 free (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	119 return NULL;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	121
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 static size_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	123 gl_carray_size (gl_list_t list)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 return list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	127
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 static const void *
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 gl_carray_node_value (gl_list_t list, gl_list_node_t node)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	131 uintptr_t index = NODE_TO_INDEX (node);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	132 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	133
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	134 if (!(index < list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	135 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	137 i = list->offset + index;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	140 return list->elements[i];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	142
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	143 static int
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	144 gl_carray_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	145 const void *elt)
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	146 {
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	147 uintptr_t index = NODE_TO_INDEX (node);
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	148 size_t i;
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	149
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	150 if (!(index < list->count))
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	151 /* Invalid argument. */
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	152 abort ();
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	153 i = list->offset + index;
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	154 if (i >= list->allocated)
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	155 i -= list->allocated;
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	156 list->elements[i] = elt;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	157 return 0;
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	158 }
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	159
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 gl_carray_next_node (gl_list_t list, gl_list_node_t node)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	162 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	163 uintptr_t index = NODE_TO_INDEX (node);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 if (!(index < list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 index++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	168 if (index < list->count)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	169 return INDEX_TO_NODE (index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	170 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	171 return NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	172 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	173
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	174 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	175 gl_carray_previous_node (gl_list_t list, gl_list_node_t node)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	176 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	177 uintptr_t index = NODE_TO_INDEX (node);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	178 if (!(index < list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	179 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 if (index > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 return INDEX_TO_NODE (index - 1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 return NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	185 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	186
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	187 static const void *
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 gl_carray_get_at (gl_list_t list, size_t position)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	192
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 if (!(position < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	196 i = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	197 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	198 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	199 return list->elements[i];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	200 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	201
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 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	203 gl_carray_nx_set_at (gl_list_t list, size_t position, const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	207
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 if (!(position < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	209 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	210 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	211 i = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	212 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	213 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	214 list->elements[i] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	215 return INDEX_TO_NODE (position);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	216 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	217
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	218 static size_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	219 gl_carray_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	220 const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	221 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	222 size_t count = list->count;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	223
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	224 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: 7398 diff changeset	225 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	226 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	227
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	228 if (start_index < end_index)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	229 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 gl_listelement_equals_fn equals = list->base.equals_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	231 size_t allocated = list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	232 size_t i_end;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	233
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	234 i_end = list->offset + end_index;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	235 if (i_end >= allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	236 i_end -= allocated;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	237
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 if (equals != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	239 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	240 size_t i;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	241
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	242 i = list->offset + start_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	243 if (i >= allocated) /* can only happen if start_index > 0 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	244 i -= allocated;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	245
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	246 for (;;)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	247 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	248 if (equals (elt, list->elements[i]))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	249 return (i >= list->offset ? i : i + allocated) - list->offset;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	250 i++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	251 if (i == allocated)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	252 i = 0;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	253 if (i == i_end)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	254 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	255 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	256 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	257 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	258 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	259 size_t i;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	260
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	261 i = list->offset + start_index;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	262 if (i >= allocated) /* can only happen if start_index > 0 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	263 i -= allocated;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	264
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	265 for (;;)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	266 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	267 if (elt == list->elements[i])
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	268 return (i >= list->offset ? i : i + allocated) - list->offset;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	269 i++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	270 if (i == allocated)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	271 i = 0;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	272 if (i == i_end)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	273 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	274 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	275 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	276 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	277 return (size_t)(-1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	278 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	279
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 static gl_list_node_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	281 gl_carray_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	282 const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	283 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	284 size_t index = gl_carray_indexof_from_to (list, start_index, end_index, elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	285 return INDEX_TO_NODE (index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	286 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	287
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	288 /* Ensure that list->allocated > list->count.
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	289 Return 0 upon success, -1 upon out-of-memory. */
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	290 static int
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	291 grow (gl_list_t list)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	292 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	293 size_t new_allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	294 size_t memory_size;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	295 const void **memory;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	296
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 new_allocated = xtimes (list->allocated, 2);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	298 new_allocated = xsum (new_allocated, 1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	299 memory_size = xtimes (new_allocated, sizeof (const void *));
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	300 if (size_overflow_p (memory_size))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	301 /* Overflow, would lead to out of memory. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	302 return -1;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	303 if (list->offset > 0 && list->count > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	304 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	305 memory = (const void **) malloc (memory_size);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	306 if (memory == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	307 /* Out of memory. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	308 return -1;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	309 if (list->offset + list->count > list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	310 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	311 memcpy (memory, &list->elements[list->offset],
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	312 (list->allocated - list->offset) * sizeof (const void *));
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	313 memcpy (memory + (list->allocated - list->offset), list->elements,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	314 (list->offset + list->count - list->allocated)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	315 * sizeof (const void *));
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	316
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	317 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	318 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	319 memcpy (memory, &list->elements[list->offset],
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	320 list->count * sizeof (const void *));
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	321 if (list->elements != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	322 free (list->elements);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	323 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	324 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	325 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	326 memory = (const void **) realloc (list->elements, memory_size);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	327 if (memory == NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	328 /* Out of memory. */
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	329 return -1;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	330 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	331 list->elements = memory;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	332 list->offset = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	333 list->allocated = new_allocated;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	334 return 0;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	335 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	336
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	337 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	338 gl_carray_nx_add_first (gl_list_t list, const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	339 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	340 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	341
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	342 if (count == list->allocated)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	343 if (grow (list) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	344 return NULL;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	345 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	346 list->elements[list->offset] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	347 list->count = count + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	348 return INDEX_TO_NODE (0);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	349 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	350
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	351 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	352 gl_carray_nx_add_last (gl_list_t list, const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	354 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	355 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	356
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	357 if (count == list->allocated)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	358 if (grow (list) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	359 return NULL;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	360 i = list->offset + count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	361 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	362 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	363 list->elements[i] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	364 list->count = count + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 return INDEX_TO_NODE (count);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	367
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 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	369 gl_carray_nx_add_at (gl_list_t list, size_t position, const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	372 const void **elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	373
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 if (!(position <= count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	375 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	376 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	377 if (count == list->allocated)
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	378 if (grow (list) < 0)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	379 return NULL;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 elements = list->elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	381 if (position <= (count / 2))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	382 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	383 /* Shift at most count/2 elements to the left. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	384 size_t i2, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	385
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	386 list->offset = (list->offset == 0 ? list->allocated : list->offset) - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	387
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	388 i2 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	389 if (i2 >= list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	390 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	391 /* Here we must have list->offset > 0, hence list->allocated > 0. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	392 size_t i1 = list->allocated - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	393 i2 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	394 for (i = list->offset; i < i1; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	395 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	396 elements[i1] = elements[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	397 for (i = 0; i < i2; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	398 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	399 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	400 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	401 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	402 for (i = list->offset; i < i2; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	403 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	404 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	405 elements[i2] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	406 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	408 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	409 /* Shift at most (count+1)/2 elements to the right. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	410 size_t i1, i3, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	411
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 i1 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	413 i3 = list->offset + count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	414 if (i1 >= list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	415 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	416 i1 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	417 i3 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	418 for (i = i3; i > i1; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	419 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	420 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	421 else if (i3 >= list->allocated)
12421 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 /* Here we must have list->offset > 0, hence list->allocated > 0. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	424 size_t i2 = list->allocated - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	425 i3 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	426 for (i = i3; i > 0; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	427 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	428 elements[0] = elements[i2];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	429 for (i = i2; i > i1; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	430 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	431 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	432 else
12421 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 for (i = i3; i > i1; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	435 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	436 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	437 elements[i1] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	438 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	439 list->count = count + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	440 return INDEX_TO_NODE (position);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	441 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	442
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 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	444 gl_carray_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	445 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	446 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	447 uintptr_t index = NODE_TO_INDEX (node);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	448
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	449 if (!(index < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	450 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	451 abort ();
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	452 return gl_carray_nx_add_at (list, index, elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	454
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	455 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	456 gl_carray_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	457 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	458 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	459 uintptr_t index = NODE_TO_INDEX (node);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	460
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	461 if (!(index < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	462 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	463 abort ();
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	464 return gl_carray_nx_add_at (list, index + 1, elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	465 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	466
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	467 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	468 gl_carray_remove_at (gl_list_t list, size_t position)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	469 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	470 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	471 const void **elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	472
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	473 if (!(position < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	475 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	476 /* Here we know count > 0. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	477 elements = list->elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	478 if (position <= ((count - 1) / 2))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	479 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	480 /* Shift at most (count-1)/2 elements to the right. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	481 size_t i0, i2, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	482
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	483 i0 = list->offset;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	484 i2 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	485 if (i2 >= list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	486 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	487 /* Here we must have list->offset > 0, hence list->allocated > 0. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	488 size_t i1 = list->allocated - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	489 i2 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	490 if (list->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	491 list->base.dispose_fn (elements[i2]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	492 for (i = i2; i > 0; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	493 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	494 elements[0] = elements[i1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	495 for (i = i1; i > i0; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	496 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	497 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	498 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	499 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	500 if (list->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	501 list->base.dispose_fn (elements[i2]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	502 for (i = i2; i > i0; i--)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	503 elements[i] = elements[i - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	504 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	505
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	506 i0++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	507 list->offset = (i0 == list->allocated ? 0 : i0);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	509 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	511 /* Shift at most count/2 elements to the left. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	512 size_t i1, i3, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	513
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 i1 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 i3 = list->offset + count - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	516 if (i1 >= list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	517 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	518 i1 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	519 i3 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	520 if (list->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	521 list->base.dispose_fn (elements[i1]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	522 for (i = i1; i < i3; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	523 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	524 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 else if (i3 >= list->allocated)
12421 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 /* Here we must have list->offset > 0, hence list->allocated > 0. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	528 size_t i2 = list->allocated - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	529 i3 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	530 if (list->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	531 list->base.dispose_fn (elements[i1]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	532 for (i = i1; i < i2; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	533 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	534 elements[i2] = elements[0];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	535 for (i = 0; i < i3; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	536 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	537 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	539 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	540 if (list->base.dispose_fn != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	541 list->base.dispose_fn (elements[i1]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	542 for (i = i1; i < i3; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	543 elements[i] = elements[i + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	544 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	545 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	546 list->count = count - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	547 return true;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	548 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	549
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	550 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	551 gl_carray_remove_node (gl_list_t list, gl_list_node_t node)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	552 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	553 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	554 uintptr_t index = NODE_TO_INDEX (node);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	555
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	556 if (!(index < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	557 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	558 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 return gl_carray_remove_at (list, index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	561
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	562 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 gl_carray_remove (gl_list_t list, const void *elt)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	564 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	565 size_t position = gl_carray_indexof_from_to (list, 0, list->count, elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 if (position == (size_t)(-1))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 return false;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	568 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 return gl_carray_remove_at (list, position);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	571
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	572 static void
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	573 gl_carray_list_free (gl_list_t list)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 if (list->elements != NULL)
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	576 {
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	577 if (list->base.dispose_fn != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	578 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	579 size_t count = list->count;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	580
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	581 if (count > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	582 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	583 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	584 const void **elements = list->elements;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	585 size_t i1 = list->offset;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	586 size_t i3 = list->offset + count - 1;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	587
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	588 if (i3 >= list->allocated)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	589 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	590 /* Here we must have list->offset > 0, hence
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	591 list->allocated > 0. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	592 size_t i2 = list->allocated - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	593 size_t i;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	594
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	595 i3 -= list->allocated;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	596 for (i = i1; i <= i2; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	597 dispose (elements[i]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	598 for (i = 0; i <= i3; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	599 dispose (elements[i]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	600 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	601 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	602 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	603 size_t i;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	604
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	605 for (i = i1; i <= i3; i++)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	606 dispose (elements[i]);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	607 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	608 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	609 }
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	610 free (list->elements);
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	611 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	612 free (list);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	613 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	614
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	615 /* --------------------- gl_list_iterator_t Data Type --------------------- */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	616
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	617 static gl_list_iterator_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	618 gl_carray_iterator (gl_list_t list)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	619 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	620 gl_list_iterator_t result;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	621
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	622 result.vtable = list->base.vtable;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	623 result.list = list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	624 result.count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	625 result.i = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	626 result.j = list->count;
18325 33db65a13e67 Use GCC_LINT, not lint Paul Eggert <eggert@cs.ucla.edu> parents: 18189 diff changeset	627 #if defined GCC_LINT \|\| defined lint
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	628 result.p = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	629 result.q = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	630 #endif
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	631
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	632 return result;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	633 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	634
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	635 static gl_list_iterator_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	636 gl_carray_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	637 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	638 gl_list_iterator_t result;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	639
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	640 if (!(start_index <= end_index && end_index <= list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	641 /* Invalid arguments. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	642 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	643 result.vtable = list->base.vtable;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 result.list = list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	645 result.count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	646 result.i = start_index;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	647 result.j = end_index;
18325 33db65a13e67 Use GCC_LINT, not lint Paul Eggert <eggert@cs.ucla.edu> parents: 18189 diff changeset	648 #if defined GCC_LINT \|\| defined lint
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	649 result.p = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	650 result.q = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	651 #endif
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	652
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	653 return result;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	654 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	655
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	656 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	657 gl_carray_iterator_next (gl_list_iterator_t *iterator,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	658 const void *eltp, gl_list_node_t nodep)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	659 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	660 gl_list_t list = iterator->list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	661 if (iterator->count != list->count)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	662 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	663 if (iterator->count != list->count + 1)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	664 /* Concurrent modifications were done on the list. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	665 abort ();
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	666 /* The last returned element was removed. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	667 iterator->count--;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	668 iterator->i--;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	669 iterator->j--;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	670 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	671 if (iterator->i < iterator->j)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	672 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 size_t i = list->offset + iterator->i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	674 if (i >= list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	675 i -= list->allocated;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	676 *eltp = list->elements[i];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	677 if (nodep != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	678 *nodep = INDEX_TO_NODE (iterator->i);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	679 iterator->i++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	680 return true;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	681 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	682 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	683 return false;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	684 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	685
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	686 static void
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	687 gl_carray_iterator_free (gl_list_iterator_t *iterator)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	688 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	689 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	690
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	691 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	692
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	693 static size_t
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	694 gl_carray_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	695 gl_listelement_compar_fn compar,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	696 size_t low, size_t high,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	697 const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	698 {
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	699 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	700 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	701 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	702 if (low < high)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	703 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	704 /* At each loop iteration, low < high; for indices < low the values
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	705 are smaller than ELT; for indices >= high the values are greater
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	706 than ELT. So, if the element occurs in the list, it is at
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	707 low <= position < high. */
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	708 do
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	709 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	710 size_t mid = low + (high - low) / 2; /* low <= mid < high */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	711 size_t i_mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	712 int cmp;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	713
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	714 i_mid = list->offset + mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	715 if (i_mid >= list->allocated)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	716 i_mid -= list->allocated;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	717
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	718 cmp = compar (list->elements[i_mid], elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	719
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	720 if (cmp < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	721 low = mid + 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	722 else if (cmp > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	723 high = mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	724 else /* cmp == 0 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	725 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	726 /* We have an element equal to ELT at index MID. But we need
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	727 the minimal such index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	728 high = mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	729 /* At each loop iteration, low <= high and
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	730 compar (list->elements[i_high], elt) == 0,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	731 and we know that the first occurrence of the element is at
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	732 low <= position <= high. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	733 while (low < high)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	734 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	735 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	736 size_t i_mid2;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	737 int cmp2;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	738
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	739 i_mid2 = list->offset + mid2;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	740 if (i_mid2 >= list->allocated)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	741 i_mid2 -= list->allocated;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	742
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	743 cmp2 = compar (list->elements[i_mid2], elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	744
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	745 if (cmp2 < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	746 low = mid2 + 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	747 else if (cmp2 > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	748 /* The list was not sorted. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	749 abort ();
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	750 else /* cmp2 == 0 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	751 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	752 if (mid2 == low)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	753 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	754 high = mid2 - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	755 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	756 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	757 return low;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	758 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	759 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	760 while (low < high);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	761 /* Here low == high. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	762 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	763 return (size_t)(-1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	764 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	765
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	766 static size_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	767 gl_carray_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	768 const void *elt)
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	769 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	770 return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	771 elt);
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	772 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	773
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	774 static gl_list_node_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	775 gl_carray_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	776 gl_listelement_compar_fn compar,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	777 size_t low, size_t high,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	778 const void *elt)
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	779 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	780 size_t index =
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	781 gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	782 return INDEX_TO_NODE (index);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	783 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	784
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	785 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	786 gl_carray_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	787 const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	788 {
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	789 size_t index =
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	790 gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	791 return INDEX_TO_NODE (index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	792 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	793
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	794 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	795 gl_carray_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	796 const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	797 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	798 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	799 size_t low = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	800 size_t high = count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	801
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	802 /* At each loop iteration, low <= high; for indices < low the values are
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	803 smaller than ELT; for indices >= high the values are greater than ELT. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	804 while (low < high)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	805 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	806 size_t mid = low + (high - low) / 2; /* low <= mid < high */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	807 size_t i_mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	808 int cmp;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	809
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	810 i_mid = list->offset + mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	811 if (i_mid >= list->allocated)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	812 i_mid -= list->allocated;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	813
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	814 cmp = compar (list->elements[i_mid], elt);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	815
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	816 if (cmp < 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	817 low = mid + 1;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	818 else if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	819 high = mid;
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	820 else /* cmp == 0 */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	821 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	822 low = mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	823 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	824 }
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	825 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	826 return gl_carray_nx_add_at (list, low, elt);
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	827 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	828
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	829 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	830 gl_carray_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	831 const void *elt)
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	832 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	833 size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	834 if (index == (size_t)(-1))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	835 return false;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	836 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	837 return gl_carray_remove_at (list, index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	838 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	839
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	840
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	841 const struct gl_list_implementation gl_carray_list_implementation =
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	842 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	843 gl_carray_nx_create_empty,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	844 gl_carray_nx_create,
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	845 gl_carray_size,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	846 gl_carray_node_value,
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	847 gl_carray_node_nx_set_value,
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	848 gl_carray_next_node,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	849 gl_carray_previous_node,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	850 gl_carray_get_at,
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	851 gl_carray_nx_set_at,
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	852 gl_carray_search_from_to,
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	853 gl_carray_indexof_from_to,
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	854 gl_carray_nx_add_first,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	855 gl_carray_nx_add_last,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	856 gl_carray_nx_add_before,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	857 gl_carray_nx_add_after,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	858 gl_carray_nx_add_at,
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	859 gl_carray_remove_node,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	860 gl_carray_remove_at,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	861 gl_carray_remove,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	862 gl_carray_list_free,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	863 gl_carray_iterator,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	864 gl_carray_iterator_from_to,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	865 gl_carray_iterator_next,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	866 gl_carray_iterator_free,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	867 gl_carray_sortedlist_search,
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	868 gl_carray_sortedlist_search_from_to,
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	869 gl_carray_sortedlist_indexof,
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	870 gl_carray_sortedlist_indexof_from_to,
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	871 gl_carray_sortedlist_nx_add,
6977 e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	872 gl_carray_sortedlist_remove
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	873 };

Mercurial > gnulib

annotate lib/gl_carray_list.c @ 40186:8964917f9574