X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fgl_anylinked_list2.h;h=718dfb713a8e8d7036e7273e61f5daf56e694207;hb=0d0706a5f5e05d18ab61e7f19ca407452db68a31;hp=8368f276edda2daef6a933c3f89b5304205096f2;hpb=407400d9367b16a628b57b2d9b8565bb5a08ffae;p=gnulib.git diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h index 8368f276e..718dfb713 100644 --- a/lib/gl_anylinked_list2.h +++ b/lib/gl_anylinked_list2.h @@ -43,8 +43,7 @@ gl_linked_create_empty (gl_list_implementation_t implementation, gl_listelement_hashcode_fn hashcode_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; @@ -52,8 +51,7 @@ gl_linked_create_empty (gl_list_implementation_t implementation, 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; @@ -69,8 +67,7 @@ gl_linked_create (gl_list_implementation_t implementation, 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; @@ -83,17 +80,14 @@ gl_linked_create (gl_list_implementation_t implementation, 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 @@ -229,7 +223,7 @@ gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index, (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) @@ -238,7 +232,7 @@ gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index, 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 @@ -279,7 +273,7 @@ gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index, 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 @@ -385,7 +379,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, (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; @@ -393,7 +387,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, 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 @@ -408,7 +402,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, 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 @@ -497,8 +491,7 @@ gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, 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 @@ -528,8 +521,7 @@ gl_linked_add_first (gl_list_t list, const void *elt) 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 @@ -559,8 +551,7 @@ gl_linked_add_last (gl_list_t list, const void *elt) 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 @@ -590,8 +581,7 @@ gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt) 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 @@ -628,8 +618,7 @@ gl_linked_add_at (gl_list_t list, size_t position, const void *elt) /* 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 = @@ -906,6 +895,54 @@ gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, 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) @@ -927,6 +964,56 @@ gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, 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)