flippingbits / cssl Goto Github PK

I have ported this to Java. This may or may not be worthwhile since it's not possible to explicitly vectorise the search for the end key in searchRange, but measuring the performance will be interesting nonetheless.

Do you have some test cases that verify the data structure's correctness? I would like to use these as sanity checks for my port.

The function below segfaults, but works fine with dense lists (my compiler is gcc 7.2.0, OS Windows). Please confirm if you can reproduce this or if I have done something silly.

#include <stdio.h>
#include <string.h>
#include "skiplist.h"

void sanity_test() {
  _CSSL_SkipList* slist = createSkipList(9, 5);
  for (int i = 0; i < 100000; i += 1000) {
    insertElement(slist, i);
  }
  _CSSL_RangeSearchResult result = searchRange(slist, 500, 2500);
  printf("Result = %d", result.count);
  printf("First = %d", result.start->key);
  printf("Last = %d", result.end->key);
}

Adding every hundredth integer to the skip list produces an incorrect number of matches (0, 20 expected), but does not segfault.

This skiplist can only insert sorted data?

I noticed the range search uses unaligned vector loads. It would be interesting to see how much better the performance is with aligned fast lanes (allowing the use of _mm256_load_si256 instead of _mm256_loadu_si256).