[Spread-cvs] cvs commit: spread/daemon skiplist.c

jesus at spread.org jesus at spread.org
Tue Jan 28 15:15:52 EST 2003


jesus       03/01/28 15:15:52

  Modified:    daemon   skiplist.c
  Log:
  PREMISE:
  The skiplist multi-index feature was added to allow O(lg n) lookups on different "primary keys" for a single set of data.  It was designed to support an arbitrarily large number of indexes on a single data set.  However, the implementation apparently only works with |indexes| <= 2.  I don't believe that Spread uses any skiplists with more than 2 indexes.
  
  PROBLEM:
  The comparison operator for the internally store index functions was not a true (correct) comparison.  Additionally, because this is a randomized data structure, when creating two skiplists with the same indexing functions, they could behave differently.
  
  SYMPTOMS:
  Successfully inserted items _might_ not be found on a subsequent sl_find_compare() call using a comparator other than that of the primary index.
  
  Revision  Changes    Path
  1.3       +17 -4     spread/daemon/skiplist.c
  
  Index: skiplist.c
  ===================================================================
  RCS file: /storage/cvsroot/spread/daemon/skiplist.c,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- skiplist.c	22 Sep 2002 02:56:52 -0000	1.2
  +++ skiplist.c	28 Jan 2003 20:15:51 -0000	1.3
  @@ -65,14 +65,27 @@
     sl->index = NULL;
   }
   
  -static int indexing_comp(void *a, void *b) {
  +static int indexing_comp(const void *a, const void *b)
  +{
  +  void *ak = (void *) (((Skiplist *) a)->compare);
  +  void *bk = (void *) (((Skiplist *) b)->compare);
     assert(a);
     assert(b);
  -  return (void *)(((Skiplist *)a)->compare)>(void *)(((Skiplist *)b)->compare);
  +  if(ak<bk)
  +    return -1;
  +  if(ak>bk)
  +    return 1;
  +  return 0;
   }
  -static int indexing_compk(void *a, void *b) {
  +static int indexing_compk(const void *ak, const void *b)
  +{
  +  void *bk = (void *) (((Skiplist *) b)->compare);
     assert(b);
  -  return a>(void *)(((Skiplist *)b)->compare);
  +  if(ak<bk)
  +    return -1;
  +  if(ak>bk)
  +    return 1;
  +  return 0;
   }
   
   void sl_init(Skiplist *sl) {
  
  
  




More information about the Spread-cvs mailing list