bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

'sublist' module (2/3): add bounded list search operations to 'list' mod


From: Bruno Haible
Subject: 'sublist' module (2/3): add bounded list search operations to 'list' modules
Date: Fri, 6 Oct 2006 14:05:37 +0200
User-agent: KMail/1.9.1

When searching a sublist of a sorted list, the number of comparisons
performed can be significantly reduced. I'm therefore adding such a
"bounded search" operation.

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.

diff -c -3 -r1.2 gl_list.h
*** lib/gl_list.h       5 Oct 2006 12:45:16 -0000       1.2
--- lib/gl_list.h       6 Oct 2006 12:02:24 -0000
***************
*** 85,91 ****
--- 85,93 ----
     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)
   */
***************
*** 303,308 ****
--- 305,324 ----
  
  /* 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.  */
***************
*** 310,315 ****
--- 326,345 ----
                                     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.  */
***************
*** 374,382 ****
--- 404,421 ----
    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);
***************
*** 634,639 ****
--- 673,687 ----
         ->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)
***************
*** 642,647 ****
--- 690,704 ----
         ->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)
diff -c -3 -r1.3 gl_list.c
*** lib/gl_list.c       5 Oct 2006 12:45:16 -0000       1.3
--- lib/gl_list.c       6 Oct 2006 12:02:24 -0000
***************
*** 232,237 ****
--- 232,245 ----
         ->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)
  {
***************
*** 239,244 ****
--- 247,260 ----
         ->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)
  {
diff -c -3 -r1.4 gl_anylinked_list2.h
*** lib/gl_anylinked_list2.h    5 Oct 2006 12:45:16 -0000       1.4
--- lib/gl_anylinked_list2.h    6 Oct 2006 12:02:23 -0000
***************
*** 906,911 ****
--- 906,959 ----
    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,932 ****
--- 975,1030 ----
    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)
diff -c -3 -r1.3 gl_anytree_list2.h
*** lib/gl_anytree_list2.h      5 Oct 2006 12:45:16 -0000       1.3
--- lib/gl_anytree_list2.h      6 Oct 2006 12:02:23 -0000
***************
*** 601,606 ****
--- 601,688 ----
    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)
***************
*** 656,661 ****
--- 738,829 ----
    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)
diff -c -3 -r1.5 gl_array_list.c
*** lib/gl_array_list.c 5 Oct 2006 12:45:16 -0000       1.5
--- lib/gl_array_list.c 6 Oct 2006 12:02:24 -0000
***************
*** 466,481 ****
  /* ---------------------- 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)
  {
!   size_t count = list->count;
! 
!   if (count > 0)
      {
-       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
--- 466,481 ----
  /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
  
  static size_t
! gl_array_sortedlist_indexof_from_to (gl_list_t list,
!                                    gl_listelement_compar_fn compar,
!                                    size_t low, size_t high,
!                                    const void *elt)
  {
!   if (!(low <= high && high <= list->count))
!     /* Invalid arguments.  */
!     abort ();
!   if (low < high)
      {
        /* 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
***************
*** 524,534 ****
    return (size_t)(-1);
  }
  
  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);
    return INDEX_TO_NODE (index);
  }
  
--- 524,554 ----
    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_from_to (list, compar, 0, list->count, elt);
    return INDEX_TO_NODE (index);
  }
  
***************
*** 598,604 ****
--- 618,626 ----
      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
    };
diff -c -3 -r1.3 gl_avltree_list.c
*** lib/gl_avltree_list.c       5 Oct 2006 12:45:16 -0000       1.3
--- lib/gl_avltree_list.c       6 Oct 2006 12:02:24 -0000
***************
*** 91,97 ****
--- 91,99 ----
      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
    };
diff -c -3 -r1.4 gl_avltreehash_list.c
*** lib/gl_avltreehash_list.c   5 Oct 2006 12:45:16 -0000       1.4
--- lib/gl_avltreehash_list.c   6 Oct 2006 12:02:24 -0000
***************
*** 120,126 ****
--- 120,128 ----
      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
    };
diff -c -3 -r1.5 gl_carray_list.c
*** lib/gl_carray_list.c        5 Oct 2006 12:45:16 -0000       1.5
--- lib/gl_carray_list.c        6 Oct 2006 12:02:24 -0000
***************
*** 610,625 ****
  /* ---------------------- 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)
  {
!   size_t count = list->count;
! 
!   if (count > 0)
      {
-       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
--- 610,625 ----
  /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
  
  static size_t
! gl_carray_sortedlist_indexof_from_to (gl_list_t list,
!                                     gl_listelement_compar_fn compar,
!                                     size_t low, size_t high,
!                                     const void *elt)
  {
!   if (!(low <= high && high <= list->count))
!     /* Invalid arguments.  */
!     abort ();
!   if (low < high)
      {
        /* 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
***************
*** 682,692 ****
    return (size_t)(-1);
  }
  
  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);
    return INDEX_TO_NODE (index);
  }
  
--- 682,712 ----
    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_from_to (list, compar, 0, list->count, elt);
    return INDEX_TO_NODE (index);
  }
  
***************
*** 763,769 ****
--- 783,791 ----
      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
    };
diff -c -3 -r1.3 gl_linked_list.c
*** lib/gl_linked_list.c        5 Oct 2006 12:45:16 -0000       1.3
--- lib/gl_linked_list.c        6 Oct 2006 12:02:24 -0000
***************
*** 58,64 ****
--- 58,66 ----
      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
    };
diff -c -3 -r1.5 gl_linkedhash_list.c
*** lib/gl_linkedhash_list.c    5 Oct 2006 12:45:16 -0000       1.5
--- lib/gl_linkedhash_list.c    6 Oct 2006 12:02:24 -0000
***************
*** 115,121 ****
--- 115,123 ----
      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
    };
diff -c -3 -r1.3 gl_rbtree_list.c
*** lib/gl_rbtree_list.c        5 Oct 2006 12:45:16 -0000       1.3
--- lib/gl_rbtree_list.c        6 Oct 2006 12:02:24 -0000
***************
*** 92,98 ****
--- 92,100 ----
      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
    };
diff -c -3 -r1.5 gl_rbtreehash_list.c
*** lib/gl_rbtreehash_list.c    5 Oct 2006 12:45:16 -0000       1.5
--- lib/gl_rbtreehash_list.c    6 Oct 2006 12:02:24 -0000
***************
*** 121,127 ****
--- 121,129 ----
      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
    };




reply via email to

[Prev in Thread] Current Thread [Next in Thread]