Segfault on sparse lists

[richardstartin]

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.

[winash12]

@richardstartin I have reproduced your problem on my box. You are precisely right it only happens for sparse lists. The segmentation fault is at this line - https://github.com/flippingbits/cssl/blob/master/skiplist.c#L306

If the skip list is continuous range and by that I mean a dense list it works fine but for sparse lists it is failing. My research problem requires sparse lists as well.

[flippingbits]

Sorry for the late response. Somehow, I didn't see any notification for this issue.

It looks like this is indeed a bug in the implementation. Unfortunately, I don't have time to work on this project at the moment. I'd be happy to merge a bug fix.

[winash12]

@flippingbits The issue is that you do not scan the entire list in the end if you do not find a match in the proxy lane array. Proxy lane array and data list are not identical. So if no match is found in the proxy lane array you need to scan the entire data list.