13.22 Components for hashtables

Tcbuckets are used only to store values in a hashtable: each tcbucket represents an entry in the table. Vicare’s hash tables are implemented as explained in the paper:

Ghuloum, Dybvig. “Generation–Friendly Eq Hash Tables”. Proceedings of the 2007 Workshop on Scheme and Functional Programming.

A tcbucket (tconc bucket, tail–concatenation bucket) is a fixed–length memory block referenced by machine words tagged as vectors; the first word in the memory block is a pair. Quoting the paper:

A tconc is a pair whose car points to the first pair in a non–empty list and whose cdr points to the last pair in that list. Element are enqueued by extending the list destructively through the last–pair pointer and dequeued through the first–pair pointer. The queue is empty when both pointers point to the same pair.

tconc objects allow to enqueue objects faster than ordinary lists.

References to tcbuckets have the following format:

|------------------------|-------------| reference to tcbucket
      heap pointer         vector tag

the memory layout of a tcbucket is as follows:

|-----|-----|-----|-----| tcbucket memory block
 tconc  key   val  next

references to tcbucket are tagged as vectors and reference a word tagged as pair.

Tcbuckets are organised in chains, similarly to pairs in lists. Hash tables are Scheme vectors whose elements are chains of tcbuckets:

buckets vector
--
| 0
--
| --> |tcbucket| --> |tcbucket| --> 1
--
| 2
--
| --> |tcbucket| --> |tcbucket| --> |tcbucket| --> 3
--
| --> |tcbucket| --> 4
--

If a buckets vector’s slot is empty: it is set to a fixnum representing its own index in the vector. Every chain of tcbuckets is a “bucket” in traditional hash tables terminology. When a new tcbucket is added to a bucket: it is prepended to the chain.

The meaning of a tcbucket’s fields is as follows:

tconc

A tconc pair. It is a structure used to efficiently handle hash tables using eq? as equivalence function.

key

A Scheme object representing the key of the hash table entry.

val

A Scheme object representing the value of the hash table entry.

next

If this tcbucket is not the last in its chain: a reference to the next tcbucket in the chain. If this tcbucket is the last in its chain: a non–negative fixnum representing the index of this chain in the table’s buckets vector.

Basic operations

Preprocessor Symbol: disp_tcbucket_tconc

Preprocessor Symbol: disp_tcbucket_key

Preprocessor Symbol: disp_tcbucket_val

Preprocessor Symbol: disp_tcbucket_next

Displacement of fields. The number of bytes to add to an untagged pointer to tcbucket to get the pointer to the first byte in the word of the tcbucket’s field.

Preprocessor Symbol: off_tcbucket_tconc

Preprocessor Symbol: off_tcbucket_key

Preprocessor Symbol: off_tcbucket_val

Preprocessor Symbol: off_tcbucket_next

An integer to add to a tagged ikptr_t reference to retrieve the pointer to the first byte of the word in the tcbucket’s field.