# Fundamental data structures

## Linked lists

Linked lists are a fundamental data structure in Dusk. They are simply addresses
in memory each pointing to the next element, with the last element of the list
pointing to 0. The first field of a LL (linked list) element is always the
pointer field.

Iterating a LL is easy, it's as simple as reading next with @ ("llnext" makes
the intent clearer).

When you want to append a new element to the list, you can call "lladd", which
makes the list's last element point to "here". You can then write your new
element.

## Dictionary structure

Words in this Forth are embedded in a dictionary, which is a list of entries
each pointing to the previous entry. We keep that last added entry in "sysdict".
Dictionaries are a form of linked list.

The structure of each entry is:

Xb of zero-padding to align the structure to 4b
Yb name
1b name length + immediate + compileonly
4b pointer to previous entry --> this is where we link
... payload ...

The "previous entry" field in an entry refers to this same place.

The "name length" field is a 6 bit length with the 8th bit reserved for the
"immediate" flag (1=immediate) and the 7th bit reserved for the "compileonly"
flag (1=compileonly).

The whole structure is aligned to 4 bytes, with zero padding in front of the
name to enforce that alignment. This means that the payload is also always
aligned to 4b.

X+Y is guaranteed to be at least 3 bytes. This guarantees a stable value of the
4 bytes ending with the "length" field, that is, a value that isn't dependent on
the memory contents that preceeds the entry.

When we refer to a "word" in Dusk OS, we always refer to its payload, its first
executable byte, right after the link field. When what you have is a word, you
can call it.

When we refer to an "entry", we refer to the data structure. This means that an
entry is a pointer to the "previous entry" field. To get a word from an entry,
we add 4 bytes. "e>w" and "w>e" are helper words to add and remove that offset
from a given address.

Except for words specifically made for manipulating dictionary entries, we
rarely deal with "entry" pointers. We most often deal with word pointers.

Entries are created with the "entry" word, which creates the structure described
below in a way that ensures that the link field and the payload are 32-bit
aligned.

"sysdict" hold a pointer to the latest entry of the system dictionary, "current"
yields the word associated to that entry.

The most important dictionary in Dusk is the system dictionary, but there are
other dictionaries (for example, each struct has its own dictionary) and they
all share the same terminology.

### Dictionary links

Dictionary links, such as the "sysdict" variable, are not only linked lists, but
also "noop" entries, that is, they don't match anything, but they're still a
link in the chain.

This peculiarity opens interesting possibilities as it allows an entry to use it
as an "indirect" link.

For example, let's say that you create a "fork" entry (not part of the system
dict, such as is the case in a namespace) and link it to "sysdict @", that is,
the last entry to have been added to the system dict. It's going to work, but
your new "dictionary branch" will be frozen in time: new entries added to the
system dictionary will not be present in the fork.

If, instead, you link your new forked entry to "sysdict" (without the @
dereferencing), then your "fork" becomes fluid: entries added to the system
dictionary will also be part of the "fork" (but "under" it).

To create a new "dictionary link", you need to create a word that yields an
address of memory that has at least 4b of zeroes preceding it. If you simply use
"create", you risk creating a "false match" on the link itself, with dreadful
consequences. You can create such a link with "dictlink" from mem/dict.

## Units

Units [doc/usage/unit] structure is a linked list with that structure:

4b link to next
4b link to bottom entry
4b link to top entry
Xb unit name (as string)

By "top entry", we mean the entry of the last word that was added to it.

By "bottom entry", we mean its first word.

## Allocator

An allocator, the struct that SYSALLOC represents and where CURALLOC points to,
is a 12 bytes struct:

4b HERE
4b HEREMAX
4b NEWHERE

See [doc/usage/mem] for details of how that works.

## SYSVARS

System variables (described in [doc/dict]) live together at a memory address
determined by the kernel, which is exposed through the "SYSVARS" word, which
yield this address. [xcomp/boot.fs] then creates the constants for each
variable by applying an offset to it. These are the offsets:

+00 reserved for platform-specific purposes
+04 COMPILING
+08 CURALLOC
+0c SYSDICT
+10 HBANKIDX
+14 [rcnt]
+18 FINDMASK
+1c SYSALLOC (size=$0c bytes)
+28 INPTR
+2c $14 bytes unused
+40 reserved for platform-specific purposes
+44 PARSEPTR
+48 PSTOP
+4c PSSZ
+50 RSTOP
... $2c bytes unused
+80 HBANK
+c0 end of SYSVARS

You will notice that we have a PSSZ but no RSSZ. That's because there's no
convenient place, in the system flow, to check for RS overflow or underflow. So
we don't. Having RS go awry breaks the system in a catastrophic manner.

At boot time, a kernel must have initialized these values:

SYSDICT CURALLOC SYSALLOC(HERE) INPTR PARSEPTR PSTOP PSSZ RSTOP

The rest is initialized to zero.
