- TRACE("s3", "find_preds: searching for key %p in skiplist (head is %p)", key, pred);
-#ifndef NDEBUG
- int count = 0;
+ TRACE("s3", "find_preds: searching for key %p in sl (head is %p)", key, pred);
+
+ int start_level = MAX_LEVEL;
+#if MAX_LEVEL > 2
+ // Optimization for small lists. No need to traverse empty higher levels.
+ start_level = 2;
+ while (pred->next[start_level+1] != NULL) {
+ start_level += start_level - 1;
+ if (EXPECT_FALSE(start_level >= MAX_LEVEL)) {
+ start_level = MAX_LEVEL;
+ break;
+ }
+ }
+ if (EXPECT_FALSE(start_level < n)) {
+ start_level = n;
+ }