+2006-10-03 Bruno Haible
+
+ * gl_list.h (gl_sortedlist_search_from_to,
+ gl_sortedlist_indexof_from_to): New declarations.
+ (gl_list_implementation): New fields sortedlist_search_from_to,
+ sortedlist_indexof_from_to.
+ (gl_sortedlist_search_from_to, gl_sortedlist_indexof_from_to): New
+ inline functions.
+ * gl_list.c (gl_sortedlist_search_from_to,
+ gl_sortedlist_indexof_from_to): New functions.
+ * gl_array_list.c (gl_array_sortedlist_indexof_from_to): New function.
+ (gl_array_sortedlist_indexof, gl_array_sortedlist_search): Use it.
+ (gl_array_sortedlist_search_from_to): New function.
+ (gl_array_list_implementation): Update.
+ * gl_carray_list.c (gl_carray_sortedlist_indexof_from_to): New function.
+ (gl_carray_sortedlist_indexof, gl_carray_sortedlist_search): Use it.
+ (gl_carray_sortedlist_search_from_to): New function.
+ (gl_carray_list_implementation): Update.
+ * gl_anylinked_list2.h (gl_linked_sortedlist_search_from_to,
+ gl_linked_sortedlist_indexof_from_to): New functions.
+ * gl_linked_list.c (gl_linked_list_implementation): Update.
+ * gl_linkedhash_list.c (gl_linkedhash_list_implementation): Update.
+ * gl_anytree_list2.h (gl_tree_sortedlist_search_from_to,
+ gl_tree_sortedlist_indexof_from_to): New functions.
+ * gl_avltree_list.c (gl_avltree_list_implementation): Update.
+ * gl_avltreehash_list.c (gl_avltreehash_list_implementation): Update.
+ * gl_rbtree_list.c (gl_rbtree_list_implementation): Update.
+ * gl_rbtreehash_list.c (gl_avltreehash_list_implementation): Update.
+
2006-10-05 Paul Eggert <eggert@cs.ucla.edu>
Fix some Darwin-7.9.0 porting problems reported by Bruno Haible in
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)
return NULL;
}
+static gl_list_node_t
+gl_tree_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ gl_list_node_t node;
+
+ if (!(low <= high
+ && high <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+
+ for (node = list->root; node != NULL; )
+ {
+ size_t left_branch_size =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size)
+ {
+ low -= left_branch_size + 1;
+ high -= left_branch_size + 1;
+ node = node->right;
+ }
+ else if (high <= left_branch_size)
+ node = node->left;
+ else
+ {
+ /* Here low <= left_branch_size < high. */
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ low = 0;
+ high -= left_branch_size + 1;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost
+ such element. */
+ gl_list_node_t found = node;
+ node = node->left;
+ for (; node != NULL; )
+ {
+ size_t left_branch_size2 =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size2)
+ {
+ low -= left_branch_size2 + 1;
+ node = node->right;
+ }
+ else
+ {
+ /* Here low <= left_branch_size2. */
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ low = 0;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found = node;
+ node = node->left;
+ }
+ }
+ }
+ return found;
+ }
+ }
+ }
+ return NULL;
+}
+
static size_t
gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
return (size_t)(-1);
}
+static size_t
+gl_tree_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ gl_list_node_t node;
+ size_t position;
+
+ if (!(low <= high
+ && high <= (list->root != NULL ? list->root->branch_size : 0)))
+ /* Invalid arguments. */
+ abort ();
+
+ for (node = list->root, position = 0; node != NULL; )
+ {
+ size_t left_branch_size =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size)
+ {
+ low -= left_branch_size + 1;
+ high -= left_branch_size + 1;
+ position += left_branch_size + 1;
+ node = node->right;
+ }
+ else if (high <= left_branch_size)
+ node = node->left;
+ else
+ {
+ /* Here low <= left_branch_size < high. */
+ int cmp = compar (node->value, elt);
+
+ if (cmp < 0)
+ {
+ low = 0;
+ high -= left_branch_size + 1;
+ position += left_branch_size + 1;
+ node = node->right;
+ }
+ else if (cmp > 0)
+ node = node->left;
+ else /* cmp == 0 */
+ {
+ /* We have an element equal to ELT. But we need the leftmost
+ such element. */
+ size_t found_position =
+ position + (node->left != NULL ? node->left->branch_size : 0);
+ node = node->left;
+ for (; node != NULL; )
+ {
+ size_t left_branch_size2 =
+ (node->left != NULL ? node->left->branch_size : 0);
+
+ if (low > left_branch_size2)
+ {
+ low -= left_branch_size2 + 1;
+ node = node->right;
+ }
+ else
+ {
+ /* Here low <= left_branch_size2. */
+ int cmp2 = compar (node->value, elt);
+
+ if (cmp2 < 0)
+ {
+ position += left_branch_size2 + 1;
+ node = node->right;
+ }
+ else if (cmp2 > 0)
+ /* The list was not sorted. */
+ abort ();
+ else /* cmp2 == 0 */
+ {
+ found_position = position + left_branch_size2;
+ node = node->left;
+ }
+ }
+ }
+ return found_position;
+ }
+ }
+ }
+ return (size_t)(-1);
+}
+
static gl_list_node_t
gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
static size_t
-gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
- const void *elt)
+gl_array_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 (count > 0)
+ if (!(low <= high && high <= list->count))
+ /* Invalid arguments. */
+ abort ();
+ if (low < high)
{
- size_t low = 0;
- size_t high = count;
-
/* At each loop iteration, low < high; for indices < low the values
are smaller than ELT; for indices >= high the values are greater
than ELT. So, if the element occurs in the list, it is at
return (size_t)(-1);
}
+static size_t
+gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+{
+ return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count,
+ elt);
+}
+
+static gl_list_node_t
+gl_array_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ size_t index =
+ gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt);
+ return INDEX_TO_NODE (index);
+}
+
static gl_list_node_t
gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
{
- size_t index = gl_array_sortedlist_indexof (list, compar, elt);
+ size_t index =
+ gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
return INDEX_TO_NODE (index);
}
gl_array_iterator_next,
gl_array_iterator_free,
gl_array_sortedlist_search,
+ gl_array_sortedlist_search_from_to,
gl_array_sortedlist_indexof,
+ gl_array_sortedlist_indexof_from_to,
gl_array_sortedlist_add,
gl_array_sortedlist_remove
};
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
static size_t
-gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
- const void *elt)
+gl_carray_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 (count > 0)
+ if (!(low <= high && high <= list->count))
+ /* Invalid arguments. */
+ abort ();
+ if (low < high)
{
- size_t low = 0;
- size_t high = count;
-
/* At each loop iteration, low < high; for indices < low the values
are smaller than ELT; for indices >= high the values are greater
than ELT. So, if the element occurs in the list, it is at
return (size_t)(-1);
}
+static size_t
+gl_carray_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+ const void *elt)
+{
+ return gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count,
+ elt);
+}
+
+static gl_list_node_t
+gl_carray_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t low, size_t high,
+ const void *elt)
+{
+ size_t index =
+ gl_carray_sortedlist_indexof_from_to (list, compar, low, high, elt);
+ return INDEX_TO_NODE (index);
+}
+
static gl_list_node_t
gl_carray_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
const void *elt)
{
- size_t index = gl_carray_sortedlist_indexof (list, compar, elt);
+ size_t index =
+ gl_carray_sortedlist_indexof_from_to (list, compar, 0, list->count, elt);
return INDEX_TO_NODE (index);
}
gl_carray_iterator_next,
gl_carray_iterator_free,
gl_carray_sortedlist_search,
+ gl_carray_sortedlist_search_from_to,
gl_carray_sortedlist_indexof,
+ gl_carray_sortedlist_indexof_from_to,
gl_carray_sortedlist_add,
gl_carray_sortedlist_remove
};
gl_linked_iterator_next,
gl_linked_iterator_free,
gl_linked_sortedlist_search,
+ gl_linked_sortedlist_search_from_to,
gl_linked_sortedlist_indexof,
+ gl_linked_sortedlist_indexof_from_to,
gl_linked_sortedlist_add,
gl_linked_sortedlist_remove
};
gl_linked_iterator_next,
gl_linked_iterator_free,
gl_linked_sortedlist_search,
+ gl_linked_sortedlist_search_from_to,
gl_linked_sortedlist_indexof,
+ gl_linked_sortedlist_indexof_from_to,
gl_linked_sortedlist_add,
gl_linked_sortedlist_remove
};
->sortedlist_search (list, compar, elt);
}
+gl_list_node_t
+gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_search_from_to (list, compar, start_index, end_index,
+ elt);
+}
+
size_t
gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
{
->sortedlist_indexof (list, compar, elt);
}
+size_t
+gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+ elt);
+}
+
gl_list_node_t
gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
{
gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n)
gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n)
gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n)
gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n)
+ gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n)
gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n)
*/
/* Search whether an element is already in the list.
The list is assumed to be sorted with COMPAR.
+ Only list elements with indices >= START_INDEX and < END_INDEX are
+ considered; the implementation uses these bounds to minimize the number
+ of COMPAR invocations.
+ Return its node if found, or NULL if not present in the list.
+ If the list contains several copies of ELT, the node of the leftmost one is
+ returned. */
+extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
+/* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
Return its position if found, or (size_t)(-1) if not present in the list.
If the list contains several copies of ELT, the position of the leftmost one
is returned. */
gl_listelement_compar_fn compar,
const void *elt);
+/* Search whether an element is already in the list.
+ The list is assumed to be sorted with COMPAR.
+ Only list elements with indices >= START_INDEX and < END_INDEX are
+ considered; the implementation uses these bounds to minimize the number
+ of COMPAR invocations.
+ Return its position if found, or (size_t)(-1) if not present in the list.
+ If the list contains several copies of ELT, the position of the leftmost one
+ is returned. */
+extern size_t gl_sortedlist_indexof_from_to (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
+
/* Add an element at the appropriate position in the list.
The list is assumed to be sorted with COMPAR.
Return its node. */
gl_list_node_t (*sortedlist_search) (gl_list_t list,
gl_listelement_compar_fn compar,
const void *elt);
+ gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index,
+ size_t end_index,
+ const void *elt);
size_t (*sortedlist_indexof) (gl_list_t list,
gl_listelement_compar_fn compar,
const void *elt);
+ size_t (*sortedlist_indexof_from_to) (gl_list_t list,
+ gl_listelement_compar_fn compar,
+ size_t start_index, size_t end_index,
+ const void *elt);
gl_list_node_t (*sortedlist_add) (gl_list_t list,
gl_listelement_compar_fn compar,
const void *elt);
->sortedlist_search (list, compar, elt);
}
+# define gl_sortedlist_search_from_to gl_sortedlist_search_from_to_inline
+static inline gl_list_node_t
+gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_search_from_to (list, compar, start_index, end_index,
+ elt);
+}
+
# define gl_sortedlist_indexof gl_sortedlist_indexof_inline
static inline size_t
gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
->sortedlist_indexof (list, compar, elt);
}
+# define gl_sortedlist_indexof_from_to gl_sortedlist_indexof_from_to_inline
+static inline size_t
+gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt)
+{
+ return ((const struct gl_list_impl_base *) list)->vtable
+ ->sortedlist_indexof_from_to (list, compar, start_index, end_index,
+ elt);
+}
+
# define gl_sortedlist_add gl_sortedlist_add_inline
static inline gl_list_node_t
gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt)
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
gl_tree_iterator_next,
gl_tree_iterator_free,
gl_tree_sortedlist_search,
+ gl_tree_sortedlist_search_from_to,
gl_tree_sortedlist_indexof,
+ gl_tree_sortedlist_indexof_from_to,
gl_tree_sortedlist_add,
gl_tree_sortedlist_remove
};
projects / gnulib.git / commitdiff