Modified Node search

node_search.c

// Overall search function; takes in a skiplist node
int invoke(skiplistNode *sl_node, Node *val) {
  int idx = modified_bsearch((Node **)sl_node->vals, 0, sl_node->sortedThreshold, val);
  if (idx >= 0) return idx;

  for (int i = sl_node->sortedThreshold; i < sl_node->numVals; i ++) {
    if (sl_node->vals[i]->id == val->id) {
      return i;
    }
  }
  return -1;
}

// Inner, binary search function
int modified_bsearch(Node **vals, int lb, int ub, Node *val) {
  if (lb > ub) return -1;

  Node *item;
  int orig_idx, idx;
  orig_idx = idx = (ub + lb) / 2;

  while ((item = vals[idx]) == NA) {
    idx --;
    if (idx < lb) {
      return modifed_bsearch(vals, orig_idx + 1, ub, val);
    }
  }

  if (item->id < val->id) {
    return modifed_bsearch(vals, orig_idx + 1, ub, val);
  } else if (item > val) {
    return modifed_bsearch(vals, lb, idx - 1, val);
  }
  return idx;
}