Function _binarySearchLeftmost

src/execution_plan/ops/op_value_hash_join.c:34–66

performs binary search, returns the leftmost index of a match

// performs binary search, returns the leftmost index of a match
static bool _binarySearchLeftmost
(
	uint *idx,
	Record *array,
	uint array_len,
	int join_key_idx,
	SIValue v
) {
	ASSERT(idx != NULL);

	SIValue x;
	uint pos = 0;
	uint left = 0;
	uint right = array_len;

	while(left < right) {
		pos = (right + left) / 2;
		x = Record_Get(array[pos], join_key_idx);
		if(SIValue_Compare(x, v, NULL) < 0) left = pos + 1;
		else right = pos;
	}

	// make sure value was found
	*idx = left;

	if(left == array_len) return false;

	x = Record_Get(array[*idx], join_key_idx);
	// return false if the value wasn't found or evaluated to NULL
	int disjointOrNull = 0;
	return (SIValue_Compare(x, v, &disjointOrNull) == 0 &&
			disjointOrNull != COMPARED_NULL);
}

// performs binary search, returns the rightmost index of a match
// assuming 'v' exists in 'array'