Quotient Filter

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

/* Find the start index of the run for fq (given that the run exists). */
static uint64_t find_run_index(struct quotient_filter *qf, uint64_t fq)
{
	/* Find the start of the cluster. */
	uint64_t b = fq;
	while (is_shifted(get_elem(qf, b))) {
		b = decr(qf, b);
	}

	/* Find the start of the run for fq. */
	uint64_t s = b;
	while (b != fq) {
		do {
			s = incr(qf, s);
		} while (is_continuation(get_elem(qf, s)));

		do {
			b = incr(qf, b);
		} while (!is_occupied(get_elem(qf, b)));
	}
	return s;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

bool qf_may_contain(struct quotient_filter *qf, uint64_t hash)
{
	uint64_t fq = hash_to_quotient(qf, hash);
	uint64_t fr = hash_to_remainder(qf, hash);
	uint64_t T_fq = get_elem(qf, fq);

	/* If this quotient has no run, give up. */
	if (!is_occupied(T_fq)) {
		return false;
	}

	/* Scan the sorted run for the target remainder. */
	uint64_t s = find_run_index(qf, fq);
	do {
		uint64_t rem = get_remainder(get_elem(qf, s));
		if (rem == fr) {
			return true;
		} else if (rem > fr) {
			return false;
		}
		s = incr(qf, s);
	} while (is_continuation(get_elem(qf, s)));
	return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

bool qf_insert(struct quotient_filter *qf, uint64_t hash)
{
	if (qf->qf_entries >= qf->qf_max_size) {
		return false;
	}

	uint64_t fq = hash_to_quotient(qf, hash);
	uint64_t fr = hash_to_remainder(qf, hash);
	uint64_t T_fq = get_elem(qf, fq);
	uint64_t entry = (fr << 3) & ~7;

	/* Special-case filling canonical slots to simplify insert_into(). */
	if (is_empty_element(T_fq)) {
		set_elem(qf, fq, set_occupied(entry));
		++qf->qf_entries;
		return true;
	}

	if (!is_occupied(T_fq)) {
		set_elem(qf, fq, set_occupied(T_fq));
	}

	uint64_t start = find_run_index(qf, fq);
	uint64_t s = start;

	if (is_occupied(T_fq)) {
		/* Move the cursor to the insert position in the fq run. */
		do {
			uint64_t rem = get_remainder(get_elem(qf, s));
			if (rem == fr) {
				return true;
			} else if (rem > fr) {
				break;
			}
			s = incr(qf, s);
		} while (is_continuation(get_elem(qf, s)));

		if (s == start) {
			/* The old start-of-run becomes a continuation. */
			uint64_t old_head = get_elem(qf, start);
			set_elem(qf, start, set_continuation(old_head));
		} else {
			/* The new element becomes a continuation. */
			entry = set_continuation(entry);
		}
	}

	/* Set the shifted bit if we can't use the canonical slot. */
	if (s != fq) {
		entry = set_shifted(entry);
	}

	insert_into(qf, s, entry);
	++qf->qf_entries;
	return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* Insert elt into QF[s], shifting over elements as necessary. */
static void insert_into(struct quotient_filter *qf, uint64_t s, uint64_t elt)
{
	uint64_t prev;
	uint64_t curr = elt;
	bool empty;

	do {
		prev = get_elem(qf, s);
		empty = is_empty_element(prev);
		if (!empty) {
			/* Fix up `is_shifted' and `is_occupied'. */
			prev = set_shifted(prev);
			if (is_occupied(prev)) {
				curr = set_occupied(curr);
				prev = clr_occupied(prev);
			}
		}
		set_elem(qf, s, curr);
		curr = prev;
		s = incr(qf, s);
	} while (!empty);
}