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) {
|
