/* Sequential list data type implemented by a linked list.
- Copyright (C) 2006 Free Software Foundation, Inc.
+ Copyright (C) 2006-2008 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2006.
- This program is free software; you can redistribute it and/or modify
+ This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software Foundation,
- Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* Common code of gl_linked_list.c and gl_linkedhash_list.c. */
gl_linked_create_empty (gl_list_implementation_t implementation,
gl_listelement_equals_fn equals_fn,
gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
bool allow_duplicates)
{
- struct gl_list_impl *list =
- (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+ struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
list->base.vtable = implementation;
list->base.equals_fn = equals_fn;
list->base.hashcode_fn = hashcode_fn;
+ list->base.dispose_fn = dispose_fn;
list->base.allow_duplicates = allow_duplicates;
#if WITH_HASHTABLE
list->table_size = 11;
- list->table =
- (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+ list->table = XCALLOC (list->table_size, gl_hash_entry_t);
#endif
list->root.next = &list->root;
list->root.prev = &list->root;
gl_linked_create (gl_list_implementation_t implementation,
gl_listelement_equals_fn equals_fn,
gl_listelement_hashcode_fn hashcode_fn,
+ gl_listelement_dispose_fn dispose_fn,
bool allow_duplicates,
size_t count, const void **contents)
{
- struct gl_list_impl *list =
- (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+ struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
gl_list_node_t tail;
list->base.vtable = implementation;
list->base.equals_fn = equals_fn;
list->base.hashcode_fn = hashcode_fn;
+ list->base.dispose_fn = dispose_fn;
list->base.allow_duplicates = allow_duplicates;
#if WITH_HASHTABLE
{
if (estimate < 10)
estimate = 10;
list->table_size = next_prime (estimate);
- list->table =
- (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+ list->table = XCALLOC (list->table_size, gl_hash_entry_t);
}
#endif
list->count = count;
tail = &list->root;
for (; count > 0; contents++, count--)
{
- gl_list_node_t node =
- (struct gl_list_node_impl *)
- xmalloc (sizeof (struct gl_list_node_impl));
+ gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
node->value = *contents;
#if WITH_HASHTABLE
return node->value;
}
+static void
+gl_linked_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+#if WITH_HASHTABLE
+ if (elt != node->value)
+ {
+ size_t new_hashcode =
+ (list->base.hashcode_fn != NULL
+ ? list->base.hashcode_fn (elt)
+ : (size_t)(uintptr_t) elt);
+
+ if (new_hashcode != node->h.hashcode)
+ {
+ remove_from_bucket (list, node);
+ node->value = elt;
+ node->h.hashcode = new_hashcode;
+ add_to_bucket (list, node);
+ }
+ else
+ node->value = elt;
+ }
+#else
+ node->value = elt;
+#endif
+}
+
static gl_list_node_t
gl_linked_next_node (gl_list_t list, gl_list_node_t node)
{
(list->base.hashcode_fn != NULL
? list->base.hashcode_fn (elt)
: (size_t)(uintptr_t) elt);
- size_t index = hashcode % list->table_size;
+ size_t bucket = hashcode % list->table_size;
gl_listelement_equals_fn equals = list->base.equals_fn;
if (!list->base.allow_duplicates)
gl_list_node_t found = NULL;
gl_list_node_t node;
- for (node = (gl_list_node_t) list->table[index];
+ for (node = (gl_list_node_t) list->table[bucket];
node != NULL;
node = (gl_list_node_t) node->h.hash_next)
if (node->h.hashcode == hashcode
gl_list_node_t first_match = NULL;
gl_list_node_t node;
- for (node = (gl_list_node_t) list->table[index];
+ for (node = (gl_list_node_t) list->table[bucket];
node != NULL;
node = (gl_list_node_t) node->h.hash_next)
if (node->h.hashcode == hashcode
(list->base.hashcode_fn != NULL
? list->base.hashcode_fn (elt)
: (size_t)(uintptr_t) elt);
- size_t index = hashcode % list->table_size;
+ size_t bucket = hashcode % list->table_size;
gl_listelement_equals_fn equals = list->base.equals_fn;
gl_list_node_t node;
if (!list->base.allow_duplicates)
{
/* Look for the first match in the hash bucket. */
- for (node = (gl_list_node_t) list->table[index];
+ for (node = (gl_list_node_t) list->table[bucket];
node != NULL;
node = (gl_list_node_t) node->h.hash_next)
if (node->h.hashcode == hashcode
bool multiple_matches = false;
gl_list_node_t first_match = NULL;
- for (node = (gl_list_node_t) list->table[index];
+ for (node = (gl_list_node_t) list->table[bucket];
node != NULL;
node = (gl_list_node_t) node->h.hash_next)
if (node->h.hashcode == hashcode
static gl_list_node_t
gl_linked_add_first (gl_list_t list, const void *elt)
{
- gl_list_node_t node =
- (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+ gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
ASYNCSAFE(const void *) node->value = elt;
#if WITH_HASHTABLE
static gl_list_node_t
gl_linked_add_last (gl_list_t list, const void *elt)
{
- gl_list_node_t node =
- (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+ gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
ASYNCSAFE(const void *) node->value = elt;
#if WITH_HASHTABLE
static gl_list_node_t
gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
{
- gl_list_node_t new_node =
- (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+ gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
ASYNCSAFE(const void *) new_node->value = elt;
#if WITH_HASHTABLE
static gl_list_node_t
gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
{
- gl_list_node_t new_node =
- (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+ gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
ASYNCSAFE(const void *) new_node->value = elt;
#if WITH_HASHTABLE
/* Invalid argument. */
abort ();
- new_node =
- (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+ new_node = XMALLOC (struct gl_list_node_impl);
ASYNCSAFE(const void *) new_node->value = elt;
#if WITH_HASHTABLE
new_node->h.hashcode =
next->prev = prev;
list->count--;
+ if (list->base.dispose_fn != NULL)
+ list->base.dispose_fn (node->value);
free (node);
return true;
}
#endif
list->count--;
+ if (list->base.dispose_fn != NULL)
+ list->base.dispose_fn (removed_node->value);
free (removed_node);
return true;
}
static void
gl_linked_list_free (gl_list_t list)
{
+ gl_listelement_dispose_fn dispose = list->base.dispose_fn;
gl_list_node_t node;
for (node = list->root.next; node != &list->root; )
{
gl_list_node_t next = node->next;
+ if (dispose != NULL)
+ dispose (node->value);
free (node);
node = next;
}
return NULL;
}
+static gl_list_node_t
+gl_linked_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ size_t count = list->count;
+
+ if (!(low <= high && high <= list->count))
+ /* Invalid arguments. */
+ abort ();
+
+ high -= low;
+ if (high > 0)
+ {
+ /* Here we know low < count. */
+ size_t position = low;
+ gl_list_node_t node;
+
+ if (position <= ((count - 1) / 2))
+ {
+ node = list->root.next;
+ for (; position > 0; position--)
+ node = node->next;
+ }
+ else
+ {
+ position = count - 1 - position;
+ node = list->root.prev;
+ for (; position > 0; position--)
+ node = node->prev;
+ }
+
+ do
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp > 0)
+ break;
+ if (cmp == 0)
+ return node;
+ node = node->next;
+ }
+ while (--high > 0);
+ }
+ return NULL;
+}
+
static size_t
gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
return (size_t)(-1);
}
+static size_t
+gl_linked_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ size_t count = list->count;
+
+ if (!(low <= high && high <= list->count))
+ /* Invalid arguments. */
+ abort ();
+
+ high -= low;
+ if (high > 0)
+ {
+ /* Here we know low < count. */
+ size_t index = low;
+ size_t position = low;
+ gl_list_node_t node;
+
+ if (position <= ((count - 1) / 2))
+ {
+ node = list->root.next;
+ for (; position > 0; position--)
+ node = node->next;
+ }
+ else
+ {
+ position = count - 1 - position;
+ node = list->root.prev;
+ for (; position > 0; position--)
+ node = node->prev;
+ }
+
+ do
+ {
+ int cmp = compar (node->value, elt);
+
+ if (cmp > 0)
+ break;
+ if (cmp == 0)
+ return index;
+ node = node->next;
+ index++;
+ }
+ while (--high > 0);
+ }
+ return (size_t)(-1);
+}
+
static gl_list_node_t
gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
projects / gnulib.git / blobdiff