octave-nkf/gnulib-hg: lib/gl_array

annotate lib/gl_array_list.c @ 17848:ab58d4870664

version-etc: new year * doc/gnulib.texi: * lib/version-etc.c (COPYRIGHT_YEAR): Update copyright date. * all files: Run 'make update-copyright'.

author	Paul Eggert <eggert@cs.ucla.edu>
date	Thu, 01 Jan 2015 01:38:23 +0000
parents	af887cfa71dd
children

rev	line source
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	1 /* Sequential list data type implemented by an array.
17848 ab58d4870664 version-etc: new year Paul Eggert <eggert@cs.ucla.edu> parents: 17761 diff changeset	2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	3 Written by Bruno Haible <bruno@clisp.org>, 2006.
1a5c885aecea Sequential list data type implemented by an 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
6975 1a5c885aecea Sequential list data type implemented by an 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.
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	9
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	13 GNU General Public License for more details.
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	14
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	15 You should have received a copy of the GNU General Public License
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 8438 diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	17
7304 1c4ed7637c24 Include <config.h> unconditionally. Bruno Haible <bruno@clisp.org> parents: 6975 diff changeset	18 #include <config.h>
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	19
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 /* Specification. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 #include "gl_array_list.h"
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	22
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 #include <stdlib.h>
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 /* Get memcpy. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 #include <string.h>
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	26
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 /* Checked size_t computations. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 #include "xsize.h"
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	29
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	30 #ifndef uintptr_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	31 # define uintptr_t unsigned long
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 #endif
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	33
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 /* -------------------------- gl_list_t Data Type -------------------------- */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	35
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 /* Concrete gl_list_impl type, valid for this file only. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 struct gl_list_impl
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	38 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	39 struct gl_list_impl_base base;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	40 /* An array of ALLOCATED elements, of which the first COUNT are used.
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 0 <= COUNT <= ALLOCATED. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 size_t count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 size_t allocated;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 };
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	46
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 /* struct gl_list_node_impl doesn't exist here. The pointers are actually
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 indices + 1. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 #define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	51
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 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	53 gl_array_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	54 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	55 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	56 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	57 bool allow_duplicates)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	59 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	60 (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	61
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	62 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	63 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	64
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 list->base.vtable = implementation;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 list->base.equals_fn = equals_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 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: 7604 diff changeset	68 list->base.dispose_fn = dispose_fn;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 list->base.allow_duplicates = allow_duplicates;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 list->elements = NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 list->count = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 list->allocated = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	73
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 return list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	76
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 static gl_list_t
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	78 gl_array_nx_create (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	79 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	80 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	81 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	82 bool allow_duplicates,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	83 size_t count, const void **contents)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	85 struct gl_list_impl *list =
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	86 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	87
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	88 if (list == NULL)
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	89 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	90
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 list->base.vtable = implementation;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 list->base.equals_fn = equals_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 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: 7604 diff changeset	94 list->base.dispose_fn = dispose_fn;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 list->base.allow_duplicates = allow_duplicates;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 if (count > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	98 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	99 goto fail;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	100 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	101 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	102 goto fail;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 memcpy (list->elements, contents, count * sizeof (const void *));
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	104 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	105 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	106 list->elements = NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 list->count = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	108 list->allocated = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	109
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 return list;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	111
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	112 fail:
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	113 free (list);
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	114 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	116
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 static size_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	118 gl_array_size (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 return list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	121 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	122
17761 af887cfa71dd avltree-list: avoid compiler warnings Dylan Cali <calid1984@gmail.com> parents: 17587 diff changeset	123 static const void * _GL_ATTRIBUTE_PURE
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 gl_array_node_value (gl_list_t list, gl_list_node_t node)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	127 if (!(index < list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 return list->elements[index];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	131 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	132
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	133 static int
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	134 gl_array_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	135 const void *elt)
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	136 {
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	137 uintptr_t index = NODE_TO_INDEX (node);
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	138 if (!(index < list->count))
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	139 /* Invalid argument. */
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	140 abort ();
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	141 list->elements[index] = elt;
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	142 return 0;
9686 25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	143 }
25f7280c9cf0 New abstract list operation 'node_set_value'. Bruno Haible <bruno@clisp.org> parents: 9309 diff changeset	144
17761 af887cfa71dd avltree-list: avoid compiler warnings Dylan Cali <calid1984@gmail.com> parents: 17587 diff changeset	145 static gl_list_node_t _GL_ATTRIBUTE_PURE
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	146 gl_array_next_node (gl_list_t list, gl_list_node_t node)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	147 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	148 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	149 if (!(index < list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	150 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	151 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 index++;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	153 if (index < list->count)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 return INDEX_TO_NODE (index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	156 return NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	157 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	158
17761 af887cfa71dd avltree-list: avoid compiler warnings Dylan Cali <calid1984@gmail.com> parents: 17587 diff changeset	159 static gl_list_node_t _GL_ATTRIBUTE_PURE
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 gl_array_previous_node (gl_list_t list, gl_list_node_t node)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	162 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	163 if (!(index < list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 if (index > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 return INDEX_TO_NODE (index - 1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	168 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	169 return NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	170 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	171
17761 af887cfa71dd avltree-list: avoid compiler warnings Dylan Cali <calid1984@gmail.com> parents: 17587 diff changeset	172 static const void * _GL_ATTRIBUTE_PURE
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	173 gl_array_get_at (gl_list_t list, size_t position)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	174 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	175 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	176
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	177 if (!(position < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	178 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	179 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 return list->elements[position];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	182
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 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	184 gl_array_nx_set_at (gl_list_t list, size_t position, const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	185 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	187
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	188 if (!(position < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	191 list->elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	194
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 static size_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	196 gl_array_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	197 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	198 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	199 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	200
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	201 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	202 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	203 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	204
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	205 if (start_index < end_index)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	206 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	207 gl_listelement_equals_fn equals = list->base.equals_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 if (equals != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	209 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	210 size_t i;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	211
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	212 for (i = start_index;;)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	213 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	214 if (equals (elt, list->elements[i]))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	215 return i;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	216 i++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	217 if (i == end_index)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	218 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	219 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	220 }
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	221 else
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	222 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	223 size_t i;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	224
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	225 for (i = start_index;;)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	226 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	227 if (elt == list->elements[i])
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	228 return i;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	229 i++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	230 if (i == end_index)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	231 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	232 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	233 }
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	234 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	235 return (size_t)(-1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	236 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	237
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 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	239 gl_array_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	240 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	241 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	242 size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	243 return INDEX_TO_NODE (index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	244 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	245
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	246 /* 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	247 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	248 static int
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 grow (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	250 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	251 size_t new_allocated;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 size_t memory_size;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	253 const void **memory;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	254
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	255 new_allocated = xtimes (list->allocated, 2);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 new_allocated = xsum (new_allocated, 1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	257 memory_size = xtimes (new_allocated, sizeof (const void *));
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	258 if (size_overflow_p (memory_size))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	259 /* 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	260 return -1;
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	261 memory = (const void **) realloc (list->elements, memory_size);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	262 if (memory == NULL)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	263 /* 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	264 return -1;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	265 list->elements = memory;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	266 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	267 return 0;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	269
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	270 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	271 gl_array_nx_add_first (gl_list_t list, const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	273 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	274 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	276
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	277 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	278 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	279 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	281 for (i = count; i > 0; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	282 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	283 elements[0] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	284 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	285 return INDEX_TO_NODE (0);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	286 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	287
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	288 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	289 gl_array_nx_add_last (gl_list_t list, const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	290 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	291 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	292
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	293 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	294 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	295 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	296 list->elements[count] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	298 return INDEX_TO_NODE (count);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	299 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	300
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	301 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	302 gl_array_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	303 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	304 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	305 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	306 size_t position;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	307 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	308 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	309
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	310 if (!(index < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	311 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	312 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	313 position = index;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	314 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	315 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	316 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	317 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	318 for (i = count; i > position; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	319 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	320 elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	321 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	322 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	323 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	324
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	325 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	326 gl_array_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	327 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	328 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	329 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	330 size_t position;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	331 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	332 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	333
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	334 if (!(index < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	335 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	336 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	337 position = index + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	338 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	339 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	340 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	341 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	342 for (i = count; i > position; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	343 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	344 elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	345 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	346 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	347 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	348
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	349 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	350 gl_array_nx_add_at (gl_list_t list, size_t position, const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	351 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	352 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	354 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	355
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	356 if (!(position <= count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	357 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	358 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	359 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	360 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	361 return NULL;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	362 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	363 for (i = count; i > position; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	364 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	367 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	369
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 gl_array_remove_node (gl_list_t list, gl_list_node_t node)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	372 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	373 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	375 size_t position;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	376 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	377 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	378
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	379 if (!(index < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	381 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	382 position = index;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	383 elements = list->elements;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	384 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	385 list->base.dispose_fn (elements[position]);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	386 for (i = position + 1; i < count; i++)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	387 elements[i - 1] = elements[i];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	388 list->count = count - 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	389 return true;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	390 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	391
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	392 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	393 gl_array_remove_at (gl_list_t list, size_t position)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	394 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	395 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	396 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	397 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	398
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	399 if (!(position < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	400 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	401 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	402 elements = list->elements;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	403 if (list->base.dispose_fn != NULL)
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	404 list->base.dispose_fn (elements[position]);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	405 for (i = position + 1; i < count; i++)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	406 elements[i - 1] = elements[i];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 list->count = count - 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	408 return true;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	409 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	410
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	411 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 gl_array_remove (gl_list_t list, const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	413 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	414 size_t position = gl_array_indexof_from_to (list, 0, list->count, elt);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	415 if (position == (size_t)(-1))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	416 return false;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	417 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	418 return gl_array_remove_at (list, position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	419 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	420
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	421 static void
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	422 gl_array_list_free (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	423 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	424 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: 7604 diff changeset	425 {
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	426 if (list->base.dispose_fn != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	427 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	428 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: 7604 diff changeset	429
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	430 if (count > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	431 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	432 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	433 const void **elements = list->elements;
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	434
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	435 do
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	436 dispose (*elements++);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	437 while (--count > 0);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	438 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	439 }
8438 238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	440 free (list->elements);
238942284e2f Allow the use of a destructor for the values stored in the list. Bruno Haible <bruno@clisp.org> parents: 7604 diff changeset	441 }
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	442 free (list);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	444
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	445 /* --------------------- gl_list_iterator_t Data Type --------------------- */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	446
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	447 static gl_list_iterator_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	448 gl_array_iterator (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	449 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	450 gl_list_iterator_t result;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	451
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	452 result.vtable = list->base.vtable;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 result.list = list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	454 result.count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	455 result.p = list->elements + 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	456 result.q = list->elements + list->count;
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	457 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	458 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	459 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	460 #endif
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	461
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	462 return result;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	463 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	464
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	465 static gl_list_iterator_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	466 gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	467 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	468 gl_list_iterator_t result;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	469
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	470 if (!(start_index <= end_index && end_index <= list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	471 /* Invalid arguments. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	472 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	473 result.vtable = list->base.vtable;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 result.list = list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	475 result.count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	476 result.p = list->elements + start_index;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	477 result.q = list->elements + end_index;
7352 3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	478 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	479 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	480 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	481 #endif
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	482
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	483 return result;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	484 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	485
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	486 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	487 gl_array_iterator_next (gl_list_iterator_t *iterator,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	488 const void *eltp, gl_list_node_t nodep)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	489 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	490 gl_list_t list = iterator->list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	491 if (iterator->count != list->count)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	492 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	493 if (iterator->count != list->count + 1)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	494 /* Concurrent modifications were done on the list. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	495 abort ();
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	496 /* The last returned element was removed. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	497 iterator->count--;
7604 63dde3c4bef5 ANSI C compliance. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	498 iterator->p = (const void **) iterator->p - 1;
63dde3c4bef5 ANSI C compliance. Bruno Haible <bruno@clisp.org> parents: 7603 diff changeset	499 iterator->q = (const void **) iterator->q - 1;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	500 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	501 if (iterator->p < iterator->q)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	502 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	503 const void p = (const void ) iterator->p;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	504 eltp = p;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	505 if (nodep != NULL)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	506 *nodep = INDEX_TO_NODE (p - list->elements);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	507 iterator->p = p + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 return true;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	509 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	511 return false;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	512 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	513
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 static void
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 gl_array_iterator_free (gl_list_iterator_t *iterator)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	516 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	517 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	518
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	520
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	521 static size_t
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	522 gl_array_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	523 gl_listelement_compar_fn compar,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	524 size_t low, size_t high,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	525 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	526 {
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	527 if (!(low <= high && high <= list->count))
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	528 /* Invalid arguments. */
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	529 abort ();
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	530 if (low < high)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	532 /* 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	533 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	534 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	535 low <= position < high. */
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	536 do
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	537 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	538 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	539 int cmp = compar (list->elements[mid], elt);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	540
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	541 if (cmp < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	542 low = mid + 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	543 else if (cmp > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	544 high = mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	545 else /* cmp == 0 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	546 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	547 /* 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	548 the minimal such index. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	549 high = mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	550 /* At each loop iteration, low <= high and
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	551 compar (list->elements[high], elt) == 0,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	552 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	553 low <= position <= high. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	554 while (low < high)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	555 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	556 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	557 int cmp2 = compar (list->elements[mid2], elt);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	558
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	559 if (cmp2 < 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	560 low = mid2 + 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	561 else if (cmp2 > 0)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	562 /* The list was not sorted. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	563 abort ();
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	564 else /* cmp2 == 0 */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	565 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	566 if (mid2 == low)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	567 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	568 high = mid2 - 1;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	569 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	570 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	571 return low;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	572 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	573 }
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 while (low < high);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 /* Here low == high. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	576 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	577 return (size_t)(-1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	578 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	579
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	580 static size_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	581 gl_array_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	582 const void *elt)
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	583 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	584 return gl_array_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	585 elt);
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	586 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	587
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	588 static gl_list_node_t
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	589 gl_array_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	590 gl_listelement_compar_fn compar,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	591 size_t low, size_t high,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	592 const void *elt)
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	593 {
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	594 size_t index =
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	595 gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	596 return INDEX_TO_NODE (index);
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	597 }
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	598
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	599 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 gl_array_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	601 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	602 {
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	603 size_t index =
9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	604 gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 return INDEX_TO_NODE (index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	606 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	607
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	608 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	609 gl_array_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	610 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	611 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	612 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	613 size_t low = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	614 size_t high = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	615
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	616 /* At each loop iteration, low <= high; for indices < low the values are
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	617 smaller than ELT; for indices >= high the values are greater than ELT. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	618 while (low < high)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	619 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	620 size_t mid = low + (high - low) / 2; /* low <= mid < high */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	621 int cmp = compar (list->elements[mid], elt);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	622
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	623 if (cmp < 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	624 low = mid + 1;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	625 else if (cmp > 0)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	626 high = mid;
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	627 else /* cmp == 0 */
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	628 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	629 low = mid;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	630 break;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 9686 diff changeset	631 }
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	632 }
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	633 return gl_array_nx_add_at (list, low, elt);
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	634 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	635
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	636 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	637 gl_array_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	638 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	639 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	640 size_t index = gl_array_sortedlist_indexof (list, compar, elt);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	641 if (index == (size_t)(-1))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	642 return false;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	643 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 return gl_array_remove_at (list, index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	645 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	646
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	647
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	648 const struct gl_list_implementation gl_array_list_implementation =
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	649 {
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	650 gl_array_nx_create_empty,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	651 gl_array_nx_create,
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	652 gl_array_size,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	653 gl_array_node_value,
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	654 gl_array_node_nx_set_value,
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	655 gl_array_next_node,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	656 gl_array_previous_node,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	657 gl_array_get_at,
12445 a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	658 gl_array_nx_set_at,
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	659 gl_array_search_from_to,
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	660 gl_array_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	661 gl_array_nx_add_first,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	662 gl_array_nx_add_last,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	663 gl_array_nx_add_before,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	664 gl_array_nx_add_after,
a8c91b846640 Move the malloc checking from module 'list' to new module 'xlist'. Bruno Haible <bruno@clisp.org> parents: 12421 diff changeset	665 gl_array_nx_add_at,
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	666 gl_array_remove_node,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	667 gl_array_remove_at,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	668 gl_array_remove,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	669 gl_array_list_free,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	670 gl_array_iterator,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	671 gl_array_iterator_from_to,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	672 gl_array_iterator_next,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 gl_array_iterator_free,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	674 gl_array_sortedlist_search,
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	675 gl_array_sortedlist_search_from_to,
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	676 gl_array_sortedlist_indexof,
7410 9704ff2cbdfe Add bounded list search operations. Bruno Haible <bruno@clisp.org> parents: 7405 diff changeset	677 gl_array_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	678 gl_array_sortedlist_nx_add,
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	679 gl_array_sortedlist_remove
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	680 };

Mercurial > hg > octave-nkf > gnulib-hg

annotate lib/gl_array_list.c @ 17848:ab58d4870664