octave-jordi/gnulib-hg: lib/gl_carray

annotate lib/gl_carray_list.c @ 6977:e6c62f234610

Sequential list data type implemented by a circular array.

author	Bruno Haible <bruno@clisp.org>
date	Mon, 17 Jul 2006 11:29:21 +0000
parents
children	1c4ed7637c24

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
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	19 #ifdef HAVE_CONFIG_H
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	20 # include <config.h>
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	21 #endif
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	22
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	23 /* Specification. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	24 #include "gl_carray_list.h"
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	25
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	26 #include <stdlib.h>
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	27 /* Get memcpy. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	28 #include <string.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 #include "xalloc.h"
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	31
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	32 /* Checked size_t computations. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	33 #include "xsize.h"
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	34
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	35 #ifndef uintptr_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	36 # define uintptr_t unsigned long
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	37 #endif
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 /* -------------------------- gl_list_t Data Type -------------------------- */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	40
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	41 /* 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	42 struct gl_list_impl
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	43 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	44 struct gl_list_impl_base base;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	45 /* 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	46 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	47 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	48 0 <= OFFSET < ALLOCATED. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	49 const void **elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	50 size_t offset;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	51 size_t count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	52 size_t allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	53 };
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	54
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	55 /* 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	56 indices + 1. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	57 #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	58 #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	59
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	60 static gl_list_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	61 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	62 gl_listelement_equals_fn equals_fn,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	63 gl_listelement_hashcode_fn hashcode_fn,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	64 bool allow_duplicates)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	65 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	66 struct gl_list_impl *list =
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	67 (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	68
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	69 list->base.vtable = implementation;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	70 list->base.equals_fn = equals_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	71 list->base.hashcode_fn = hashcode_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	72 list->base.allow_duplicates = allow_duplicates;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	73 list->elements = NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	74 list->offset = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	75 list->count = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	76 list->allocated = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	77
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	78 return list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	79 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	80
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	81 static gl_list_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	82 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	83 gl_listelement_equals_fn equals_fn,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	84 gl_listelement_hashcode_fn hashcode_fn,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	85 bool allow_duplicates,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	86 size_t count, const void **contents)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	87 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	88 struct gl_list_impl *list =
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	89 (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	90
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	91 list->base.vtable = implementation;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	92 list->base.equals_fn = equals_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	93 list->base.hashcode_fn = hashcode_fn;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	94 list->base.allow_duplicates = allow_duplicates;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	95 if (count > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	96 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	97 list->elements =
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	98 (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	99 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	100 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	101 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	102 list->elements = NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	103 list->offset = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	104 list->count = count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	105 list->allocated = count;
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 return list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	108 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	109
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	110 static size_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	111 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	112 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	113 return list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	114 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	115
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	116 static const void *
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	117 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	118 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	119 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	120 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	121
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	122 if (!(index < list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	123 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	124 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	125 i = list->offset + index;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	126 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	127 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	128 return list->elements[i];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	129 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	130
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	131 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	132 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	133 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	134 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	135 if (!(index < list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	136 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	137 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	138 index++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	139 if (index < list->count)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	140 return INDEX_TO_NODE (index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	141 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	142 return NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	143 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	144
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	145 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	146 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	147 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	148 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	149 if (!(index < list->count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	150 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	151 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	152 if (index > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	153 return INDEX_TO_NODE (index - 1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	154 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	155 return NULL;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	156 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	157
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	158 static const void *
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	159 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	160 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	161 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	162 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	163
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	164 if (!(position < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	165 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	166 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	167 i = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	168 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	169 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	170 return list->elements[i];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	171 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	172
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	173 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	174 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	175 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	176 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	177 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	178
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	179 if (!(position < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	180 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	181 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	182 i = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	183 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	184 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	185 list->elements[i] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	186 return INDEX_TO_NODE (position);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	187 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	188
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	189 static size_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	190 gl_carray_indexof (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	191 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	192 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	193 if (count > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	194 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	195 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	196 size_t allocated = list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	197 size_t i_end;
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 i_end = list->offset + list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	200 if (i_end >= allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	201 i_end -= allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	202
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	203 if (equals != NULL)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	204 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	205 size_t i;
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 for (i = list->offset;;)
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 if (equals (elt, list->elements[i]))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	210 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	211 i++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	212 if (i == allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	213 i = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	214 if (i == i_end)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	215 break;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	216 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	217 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	218 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	219 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	220 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	221
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	222 for (i = list->offset;;)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	223 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	224 if (elt == list->elements[i])
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	225 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	226 i++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	227 if (i == allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	228 i = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	229 if (i == i_end)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	230 break;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	231 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	232 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	233 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	234 return (size_t)(-1);
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
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	237 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	238 gl_carray_search (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	239 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	240 size_t index = gl_carray_indexof (list, elt);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	241 return INDEX_TO_NODE (index);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	242 }
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 /* Ensure that list->allocated > list->count. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	245 static void
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	246 grow (gl_list_t list)
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 size_t new_allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	249 size_t memory_size;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	250 const void **memory;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	251
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	252 new_allocated = xtimes (list->allocated, 2);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	253 new_allocated = xsum (new_allocated, 1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	254 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	255 if (size_overflow_p (memory_size))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	256 /* 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	257 xalloc_die ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	258 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	259 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	260 memory = (const void **) xmalloc (memory_size);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	261 if (memory == NULL)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	262 /* Out of memory. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	263 xalloc_die ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	264 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	265 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	266 memcpy (memory, &list->elements[list->offset],
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	267 (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	268 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	269 (list->offset + list->count - list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	270 * sizeof (const void *));
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	271
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 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	274 memcpy (memory, &list->elements[list->offset],
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	275 list->count * sizeof (const void *));
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	276 if (list->elements != NULL)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	277 free (list->elements);
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 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	280 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	281 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	282 if (memory == NULL)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	283 /* Out of memory. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	284 xalloc_die ();
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 list->elements = memory;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	287 list->offset = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	288 list->allocated = new_allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	289 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	290
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	291 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	292 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	293 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	294 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	295
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	296 if (count == list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	297 grow (list);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	298 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	299 list->elements[list->offset] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	300 list->count = count + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	301 return INDEX_TO_NODE (0);
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_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	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 size_t i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	309
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	310 if (count == list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	311 grow (list);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	312 i = list->offset + count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	313 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	314 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	315 list->elements[i] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	316 list->count = count + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	317 return INDEX_TO_NODE (count);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	318 }
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 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	321 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	322 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	323 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	324 const void **elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	325
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	326 if (!(position <= count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	327 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	328 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	329 if (count == list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	330 grow (list);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	331 elements = list->elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	332 if (position <= (count / 2))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	333 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	334 /* 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	335 size_t i2, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	336
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	337 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	338
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	339 i2 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	340 if (i2 >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	341 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	342 /* 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	343 size_t i1 = list->allocated - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	344 i2 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	345 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	346 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	347 elements[i1] = elements[0];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	348 for (i = 0; i < i2; i++)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	349 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	350 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	351 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	352 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	353 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	354 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	355 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	356 elements[i2] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	357 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	358 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	359 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	360 /* 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	361 size_t i1, i3, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	362
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	363 i1 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	364 i3 = list->offset + count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	365 if (i1 >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	366 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	367 i1 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	368 i3 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	369 for (i = i3; i > i1; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	370 elements[i] = elements[i - 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	371 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	372 else if (i3 >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	373 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	374 /* 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	375 size_t i2 = list->allocated - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	376 i3 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	377 for (i = i3; i > 0; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	378 elements[i] = elements[i - 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	379 elements[0] = elements[i2];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	380 for (i = i2; i > i1; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	381 elements[i] = elements[i - 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	382 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	383 else
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 for (i = i3; i > i1; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	386 elements[i] = elements[i - 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	387 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	388 elements[i1] = elt;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	389 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	390 list->count = count + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	391 return INDEX_TO_NODE (position);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	392 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	393
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	394 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	395 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	396 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	397 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	398 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	399
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	400 if (!(index < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	401 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	402 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	403 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	404 }
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 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	407 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	408 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	409 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	410 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	411
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	412 if (!(index < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	413 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	414 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	415 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	416 }
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 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	419 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	420 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	421 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	422 const void **elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	423
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	424 if (!(position < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	425 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	426 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	427 /* Here we know count > 0. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	428 elements = list->elements;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	429 if (position <= ((count - 1) / 2))
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 /* 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	432 size_t i0, i2, i;
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 i0 = list->offset;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	435 i2 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	436 if (i2 >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	437 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	438 /* 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	439 size_t i1 = list->allocated - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	440 i2 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	441 for (i = i2; i > 0; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	442 elements[i] = elements[i - 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	443 elements[0] = elements[i1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	444 for (i = i1; i > i0; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	445 elements[i] = elements[i - 1];
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 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	448 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	449 for (i = i2; i > i0; i--)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	450 elements[i] = elements[i - 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	451 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	452
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	453 i0++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	454 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	455 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	456 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	457 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	458 /* 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	459 size_t i1, i3, i;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	460
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	461 i1 = list->offset + position;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	462 i3 = list->offset + count - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	463 if (i1 >= list->allocated)
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 i1 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	466 i3 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	467 for (i = i1; i < i3; i++)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	468 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	469 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	470 else if (i3 >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	471 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	472 /* 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	473 size_t i2 = list->allocated - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	474 i3 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	475 for (i = i1; i < i2; i++)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	476 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	477 elements[i2] = elements[0];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	478 for (i = 0; i < i3; i++)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	479 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	480 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	481 else
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 for (i = i1; i < i3; i++)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	484 elements[i] = elements[i + 1];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	485 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	486 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	487 list->count = count - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	488 return true;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	489 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	490
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	491 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	492 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	493 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	494 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	495 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	496
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	497 if (!(index < count))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	498 /* Invalid argument. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	499 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	500 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	501 }
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 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	504 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	505 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	506 size_t position = gl_carray_indexof (list, elt);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	507 if (position == (size_t)(-1))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	508 return false;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	509 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	510 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	511 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	512
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	513 static void
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	514 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	515 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	516 if (list->elements != NULL)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	517 free (list->elements);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	518 free (list);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	519 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	520
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	521 /* --------------------- gl_list_iterator_t Data Type --------------------- */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	522
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	523 static gl_list_iterator_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	524 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	525 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	526 gl_list_iterator_t result;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	527
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	528 result.vtable = list->base.vtable;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	529 result.list = list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	530 result.count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	531 result.i = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	532 result.j = list->count;
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 return result;
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
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	537 static gl_list_iterator_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	538 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	539 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	540 gl_list_iterator_t result;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	541
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	542 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	543 /* Invalid arguments. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	544 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	545 result.vtable = list->base.vtable;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	546 result.list = list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	547 result.count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	548 result.i = start_index;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	549 result.j = end_index;
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 bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	555 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	556 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	557 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	558 gl_list_t list = iterator->list;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	559 if (iterator->count != list->count)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	560 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	561 if (iterator->count != list->count + 1)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	562 /* 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	563 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	564 /* The last returned element was removed. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	565 iterator->count--;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	566 iterator->i--;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	567 iterator->j--;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	568 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	569 if (iterator->i < iterator->j)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	570 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	571 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	572 if (i >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	573 i -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	574 *eltp = list->elements[i];
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	575 if (nodep != NULL)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	576 *nodep = INDEX_TO_NODE (iterator->i);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	577 iterator->i++;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	578 return true;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	579 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	580 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	581 return false;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	582 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	583
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	584 static void
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	585 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	586 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	587 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	588
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	589 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	590
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	591 static size_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	592 gl_carray_sortedlist_indexof (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	593 const void *elt)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	594 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	595 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	596
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	597 if (count > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	598 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	599 size_t low = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	600 size_t high = count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	601
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	602 /* 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	603 are smaller than ELT; for indices >= high the values are greater
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	604 than ELT. So, if the element occurs in the list, is at
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	605 low <= position < high. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	606 do
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 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	609 size_t i_mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	610 int cmp;
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 i_mid = list->offset + mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	613 if (i_mid >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	614 i_mid -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	615
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	616 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	617
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	618 if (cmp < 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	619 low = mid + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	620 else if (cmp > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	621 high = mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	622 else /* cmp == 0 */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	623 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	624 /* 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	625 the minimal such index. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	626 high = mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	627 /* 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	628 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	629 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	630 low <= position <= high. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	631 while (low < high)
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 size_t mid2 = 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	634 size_t i_mid2;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	635 int cmp2;
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 i_mid2 = list->offset + mid2;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	638 if (i_mid2 >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	639 i_mid2 -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	640
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	641 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	642
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	643 if (cmp2 < 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	644 low = mid2 + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	645 else if (cmp2 > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	646 /* The list was not sorted. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	647 abort ();
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	648 else /* cmp2 == 0 */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	649 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	650 if (mid2 == low)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	651 break;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	652 high = mid2 - 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	653 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	654 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	655 return low;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	656 }
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 while (low < high);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	659 /* Here low == high. */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	660 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	661 return (size_t)(-1);
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	662 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	663
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	664 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	665 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	666 const void *elt)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	667 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	668 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	669 return INDEX_TO_NODE (index);
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
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	672 static gl_list_node_t
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	673 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	674 const void *elt)
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 size_t count = list->count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	677 size_t low = 0;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	678 size_t high = count;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	679
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	680 /* 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	681 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	682 while (low < high)
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 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	685 size_t i_mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	686 int cmp;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	687
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	688 i_mid = list->offset + mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	689 if (i_mid >= list->allocated)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	690 i_mid -= list->allocated;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	691
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	692 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	693
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	694 if (cmp < 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	695 low = mid + 1;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	696 else if (cmp > 0)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	697 high = mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	698 else /* cmp == 0 */
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	699 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	700 low = mid;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	701 break;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	702 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	703 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	704 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	705 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	706
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	707 static bool
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	708 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	709 const void *elt)
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	710 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	711 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	712 if (index == (size_t)(-1))
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	713 return false;
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	714 else
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	715 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	716 }
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	717
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	718
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	719 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	720 {
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	721 gl_carray_create_empty,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	722 gl_carray_create,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	723 gl_carray_size,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	724 gl_carray_node_value,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	725 gl_carray_next_node,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	726 gl_carray_previous_node,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	727 gl_carray_get_at,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	728 gl_carray_set_at,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	729 gl_carray_search,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	730 gl_carray_indexof,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	731 gl_carray_add_first,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	732 gl_carray_add_last,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	733 gl_carray_add_before,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	734 gl_carray_add_after,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	735 gl_carray_add_at,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	736 gl_carray_remove_node,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	737 gl_carray_remove_at,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	738 gl_carray_remove,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	739 gl_carray_list_free,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	740 gl_carray_iterator,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	741 gl_carray_iterator_from_to,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	742 gl_carray_iterator_next,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	743 gl_carray_iterator_free,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	744 gl_carray_sortedlist_search,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	745 gl_carray_sortedlist_indexof,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	746 gl_carray_sortedlist_add,
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	747 gl_carray_sortedlist_remove
e6c62f234610 Sequential list data type implemented by a circular array. Bruno Haible <bruno@clisp.org> parents: diff changeset	748 };

Mercurial > hg > octave-jordi > gnulib-hg

annotate lib/gl_carray_list.c @ 6977:e6c62f234610