octave-jordi/gnulib-hg: lib/gl_carray

annotate lib/gl_carray_list.c @ 7410:9704ff2cbdfe

Add bounded list search operations.

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

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

Mercurial > hg > octave-jordi > gnulib-hg

annotate lib/gl_carray_list.c @ 7410:9704ff2cbdfe