octave-nkf/gnulib-hg: lib/gl_array

annotate lib/gl_array_list.c @ 7405:0de49c40e105

Add searching operations, limited to a subsequence of the list.

author	Bruno Haible <bruno@clisp.org>
date	Thu, 05 Oct 2006 12:45:16 +0000
parents	df2f24a4f4b4
children	9704ff2cbdfe

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.
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	2 Copyright (C) 2006 Free Software Foundation, Inc.
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	5 This program is free software; you can redistribute it and/or modify
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	7 the Free Software Foundation; either version 2, or (at your option)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	8 any later version.
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	16 along with this program; if not, write to the Free Software Foundation,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	18
7304 1c4ed7637c24 Include <config.h> unconditionally. Bruno Haible <bruno@clisp.org> parents: 6975 diff changeset	19 #include <config.h>
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	20
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 /* Specification. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	22 #include "gl_array_list.h"
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	23
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 #include <stdlib.h>
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	25 /* Get memcpy. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 #include <string.h>
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	27
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 #include "xalloc.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 /* Checked size_t computations. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	31 #include "xsize.h"
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	32
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 #ifndef uintptr_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	34 # define uintptr_t unsigned long
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	35 #endif
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	36
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 /* -------------------------- gl_list_t Data Type -------------------------- */
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 /* 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	40 struct gl_list_impl
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	42 struct gl_list_impl_base base;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 /* 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	44 0 <= COUNT <= ALLOCATED. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	46 size_t count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	47 size_t allocated;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	48 };
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	49
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 /* 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	51 indices + 1. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 #define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 #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	54
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 static gl_list_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	56 gl_array_create_empty (gl_list_implementation_t implementation,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 gl_listelement_equals_fn equals_fn,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	58 gl_listelement_hashcode_fn hashcode_fn,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	59 bool allow_duplicates)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	61 struct gl_list_impl *list =
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	62 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	63
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 list->base.vtable = implementation;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 list->base.equals_fn = equals_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 list->base.hashcode_fn = hashcode_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 list->base.allow_duplicates = allow_duplicates;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	68 list->elements = NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 list->count = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 list->allocated = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	71
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 return list;
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 static gl_list_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 gl_array_create (gl_list_implementation_t implementation,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	77 gl_listelement_equals_fn equals_fn,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 gl_listelement_hashcode_fn hashcode_fn,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	79 bool allow_duplicates,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	80 size_t count, const void **contents)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	81 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	82 struct gl_list_impl *list =
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	83 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	84
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 list->base.vtable = implementation;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 list->base.equals_fn = equals_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 list->base.hashcode_fn = hashcode_fn;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 list->base.allow_duplicates = allow_duplicates;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	89 if (count > 0)
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->elements =
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 (const void *) xmalloc (count sizeof (const void *));
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 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	94 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 list->elements = NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 list->count = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 list->allocated = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	99
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	100 return list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	102
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 static size_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	104 gl_array_size (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	105 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	106 return list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	107 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	108
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	109 static const void *
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 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	111 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	112 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	113 if (!(index < list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	115 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 return list->elements[index];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	118
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	120 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	121 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	123 if (!(index < list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 index++;
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 return INDEX_TO_NODE (index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	130 return NULL;
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	133 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	134 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	135 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	137 if (!(index < list->count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	140 if (index > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 return INDEX_TO_NODE (index - 1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	142 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	143 return NULL;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	144 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	145
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	146 static const void *
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	147 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	148 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	149 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	150
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	151 if (!(position < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	153 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 return list->elements[position];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	156
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	157 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	158 gl_array_set_at (gl_list_t list, size_t position, const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	159 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	160 size_t count = list->count;
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 if (!(position < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	163 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 list->elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	168
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	169 static size_t
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	170 gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	171 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	172 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	173 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	174
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	175 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	176 /* Invalid arguments. */
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	177 abort ();
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	178
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	179 if (start_index < end_index)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 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	182 if (equals != NULL)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	185
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	186 for (i = start_index;;)
6975 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 (equals (elt, list->elements[i]))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 return i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 i++;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	191 if (i == end_index)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 break;
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 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	196 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	197 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	198
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	199 for (i = start_index;;)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	200 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 if (elt == list->elements[i])
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	202 return i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 i++;
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	204 if (i == end_index)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 break;
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 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	208 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	209 return (size_t)(-1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	210 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	211
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	212 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	213 gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	214 const void *elt)
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	215 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	216 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	217 return INDEX_TO_NODE (index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	218 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	219
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	220 /* Ensure that list->allocated > list->count. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	221 static void
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	222 grow (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	223 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	224 size_t new_allocated;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	225 size_t memory_size;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	226 const void **memory;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	227
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	228 new_allocated = xtimes (list->allocated, 2);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	229 new_allocated = xsum (new_allocated, 1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 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	231 if (size_overflow_p (memory_size))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	232 /* Overflow, would lead to out of memory. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	233 xalloc_die ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	234 memory = (const void **) xrealloc (list->elements, memory_size);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	235 if (memory == NULL)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	236 /* Out of memory. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	237 xalloc_die ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 list->elements = memory;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	239 list->allocated = new_allocated;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	240 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	241
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	242 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	243 gl_array_add_first (gl_list_t list, const void *elt)
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 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	246 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	247 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	248
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 if (count == list->allocated)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	250 grow (list);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	251 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 for (i = count; i > 0; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	253 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	254 elements[0] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	255 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 return INDEX_TO_NODE (0);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	257 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	258
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	259 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	260 gl_array_add_last (gl_list_t list, const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	261 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	262 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	263
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	264 if (count == list->allocated)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	265 grow (list);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	266 list->elements[count] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	267 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	268 return INDEX_TO_NODE (count);
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	271 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	272 gl_array_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	273 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	274 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	276 size_t position;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	277 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	278 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	279
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 if (!(index < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	281 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	282 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	283 position = index;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	284 if (count == list->allocated)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	285 grow (list);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	286 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	287 for (i = count; i > position; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	288 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	289 elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	290 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	291 return INDEX_TO_NODE (position);
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	294 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	295 gl_array_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	296 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	298 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	299 size_t position;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	300 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	301 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	302
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	303 if (!(index < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	304 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	305 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	306 position = index + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	307 if (count == list->allocated)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	308 grow (list);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	309 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	310 for (i = count; i > position; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	311 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	312 elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	313 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	314 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	315 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	316
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	317 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	318 gl_array_add_at (gl_list_t list, size_t position, const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	319 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	320 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	321 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	322 size_t i;
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 if (!(position <= count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	325 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	326 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	327 if (count == list->allocated)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	328 grow (list);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	329 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	330 for (i = count; i > position; i--)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	331 elements[i] = elements[i - 1];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	332 elements[position] = elt;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	333 list->count = count + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	334 return INDEX_TO_NODE (position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	335 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	336
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	337 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	338 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	339 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	340 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	341 uintptr_t index = NODE_TO_INDEX (node);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	342 size_t position;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	343 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	344 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	345
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	346 if (!(index < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	347 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	348 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	349 position = index;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	350 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	351 for (i = position + 1; i < count; i++)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	352 elements[i - 1] = elements[i];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 list->count = count - 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	354 return true;
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	357 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	358 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	359 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	360 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	361 const void **elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	362 size_t i;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	363
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	364 if (!(position < count))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 /* Invalid argument. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	367 elements = list->elements;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 for (i = position + 1; i < count; i++)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	369 elements[i - 1] = elements[i];
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 list->count = count - 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 return true;
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	375 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	376 {
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	377 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	378 if (position == (size_t)(-1))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	379 return false;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	381 return gl_array_remove_at (list, position);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	382 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	383
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	384 static void
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	385 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	386 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	387 if (list->elements != NULL)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	388 free (list->elements);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	389 free (list);
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 /* --------------------- gl_list_iterator_t Data Type --------------------- */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	393
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	394 static gl_list_iterator_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	395 gl_array_iterator (gl_list_t list)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	396 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	397 gl_list_iterator_t result;
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 result.vtable = list->base.vtable;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	400 result.list = list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	401 result.count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	402 result.p = list->elements + 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	403 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	404 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	405 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	406 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	407 #endif
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	408
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	409 return result;
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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 static gl_list_iterator_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	413 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	414 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	415 gl_list_iterator_t result;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	416
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	417 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	418 /* Invalid arguments. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	419 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	420 result.vtable = list->base.vtable;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	421 result.list = list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	422 result.count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	423 result.p = list->elements + start_index;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	424 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	425 #ifdef lint
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	426 result.i = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	427 result.j = 0;
3d5bd6899004 * gl_anylinked_list2.h [lint] (gl_linked_iterator) Ralf Wildenhues <Ralf.Wildenhues@gmx.de> parents: 7304 diff changeset	428 #endif
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	429
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	430 return result;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	431 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	432
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	433 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	434 gl_array_iterator_next (gl_list_iterator_t *iterator,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	435 const void *eltp, gl_list_node_t nodep)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	436 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	437 gl_list_t list = iterator->list;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	438 if (iterator->count != list->count)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	439 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	440 if (iterator->count != list->count + 1)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	441 /* Concurrent modifications were done on the list. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	442 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 /* The last returned element was removed. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	444 iterator->count--;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	445 iterator->p--;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	446 iterator->q--;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	447 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	448 if (iterator->p < iterator->q)
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 const void p = (const void ) iterator->p;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	451 eltp = p;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	452 if (nodep != NULL)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 *nodep = INDEX_TO_NODE (p - list->elements);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	454 iterator->p = p + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	455 return true;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	456 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	457 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	458 return false;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	459 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	460
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	461 static void
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	462 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	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
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	466 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
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 static size_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	469 gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	470 const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	471 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	472 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	473
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 if (count > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	475 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	476 size_t low = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	477 size_t high = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	478
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	479 /* At each loop iteration, low < high; for indices < low the values
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	480 are smaller than ELT; for indices >= high the values are greater
7398 df2f24a4f4b4 Comment fixes. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	481 than ELT. So, if the element occurs in the list, it is at
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	482 low <= position < high. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	483 do
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 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	486 int cmp = compar (list->elements[mid], elt);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	487
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	488 if (cmp < 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	489 low = mid + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	490 else if (cmp > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	491 high = mid;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	492 else /* cmp == 0 */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	493 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	494 /* We have an element equal to ELT at index MID. But we need
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	495 the minimal such index. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	496 high = mid;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	497 /* At each loop iteration, low <= high and
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	498 compar (list->elements[high], elt) == 0,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	499 and we know that the first occurrence of the element is at
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	500 low <= position <= high. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	501 while (low < high)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	502 {
7398 df2f24a4f4b4 Comment fixes. Bruno Haible <bruno@clisp.org> parents: 7352 diff changeset	503 size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	504 int cmp2 = compar (list->elements[mid2], elt);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	505
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	506 if (cmp2 < 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	507 low = mid2 + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 else if (cmp2 > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	509 /* The list was not sorted. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 abort ();
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	511 else /* cmp2 == 0 */
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 if (mid2 == low)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 break;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	515 high = mid2 - 1;
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 return low;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 }
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 while (low < high);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	522 /* Here low == high. */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	523 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	524 return (size_t)(-1);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	525 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	526
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	527 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	528 gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	529 const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	530 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 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	532 return INDEX_TO_NODE (index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	533 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	534
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	535 static gl_list_node_t
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	536 gl_array_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	537 const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	539 size_t count = list->count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	540 size_t low = 0;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	541 size_t high = count;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	542
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	543 /* 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	544 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	545 while (low < high)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	546 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	547 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	548 int cmp = compar (list->elements[mid], elt);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	549
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	550 if (cmp < 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	551 low = mid + 1;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	552 else if (cmp > 0)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	553 high = mid;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	554 else /* cmp == 0 */
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	555 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	556 low = mid;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	557 break;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	558 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 return gl_array_add_at (list, low, elt);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	561 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	562
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	563 static bool
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	564 gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	565 const void *elt)
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 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	568 if (index == (size_t)(-1))
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 return false;
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 else
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	571 return gl_array_remove_at (list, index);
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	572 }
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	573
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	574
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 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	576 {
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	577 gl_array_create_empty,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	578 gl_array_create,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	579 gl_array_size,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	580 gl_array_node_value,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	581 gl_array_next_node,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	582 gl_array_previous_node,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	583 gl_array_get_at,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	584 gl_array_set_at,
7405 0de49c40e105 Add searching operations, limited to a subsequence of the list. Bruno Haible <bruno@clisp.org> parents: 7398 diff changeset	585 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	586 gl_array_indexof_from_to,
6975 1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	587 gl_array_add_first,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	588 gl_array_add_last,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	589 gl_array_add_before,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	590 gl_array_add_after,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	591 gl_array_add_at,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	592 gl_array_remove_node,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	593 gl_array_remove_at,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	594 gl_array_remove,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	595 gl_array_list_free,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	596 gl_array_iterator,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	597 gl_array_iterator_from_to,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	598 gl_array_iterator_next,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	599 gl_array_iterator_free,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 gl_array_sortedlist_search,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	601 gl_array_sortedlist_indexof,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	602 gl_array_sortedlist_add,
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	603 gl_array_sortedlist_remove
1a5c885aecea Sequential list data type implemented by an array. Bruno Haible <bruno@clisp.org> parents: diff changeset	604 };

Mercurial > hg > octave-nkf > gnulib-hg

annotate lib/gl_array_list.c @ 7405:0de49c40e105