# 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 padding to align the structure to 4b
Yb name
1b name length + immediate
4b pointer to metadata
4b pointer to previous entry --> this is where we link
... payload ...

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

The link to "metadata" is a linked list, initialized to 0.

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

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 first executable
byte, right after the name length 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 5 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 *word* is 32-bit aligned. This means that
metadata and link fields are necessarily out of alignment. But the callable word
is 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 struct[ definition) 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 5 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.

### Dictionary entry metadata

Each entry in the dictionary can have metadata linked to it in the form of a
linked list. The pointer to the first element (or 0 if none) for an entry is
given by the word "e>meta".

Each metadata element has this structure:

4b link to next
4b type ID
( any other type-specific data )

IDs below $100 are reserved for the system, IDs below $1000 are reserved for
Dusk OS, the rest is free to use. This is the list of used meta IDs:

$10  EMETA_8B        "code8b" code fragment
$11  EMETA_16B       "code16b" code fragment
$20  EMETA_DATAPTR   Link the the "data" portion of a word, used for namespaces
$21  EMETA_COMPILING ":compiling" code fragment

$100 EMETA_BOTHCONST See comp/c/sexpr.fs
$101 EMETA_CONSTOP   See comp/c/sexpr.fs

## SYSVARS

System variables 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 HERE
+0c CURCONTEXT
+10 HBANKIDX
+14 [rcnt]
+18 nextmeta
+1c MOD
+20 NEXTWORD
+24 INPTR
+28 HEREMAX
+2c SYSCONTEXT (size=$14 bytes)
+40 reserved for platform-specific purposes
+44 PARSEPTR
+48 PSTOP
+4c RSTOP
... $10 bytes unused
+60 curword
+80 HBANK
+c0 end of SYSVARS

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

SYSCONTEXT Has its "dict" part point to the last word of the kernel
CURCONTEXT Points to SYSCONTEXT
HERE       Beginning of HERE memory
HEREMAX    Upper bound of HERE memory
INPTR      Address of boot code (xcomp/boot.fs and following) contents
PARSEPTR   To a word ( str -- ?n f ) that can parse decimals
PSTOP      Where "abort" must reset PSP to
RSTOP      Where "quit" must reset RSP to

The rest is initialized to zero.

## floaded

Dusk can remember which paths it loaded so that it we can ensure that a unit
isn't loaded twice without having to do individual "guards" around units.

This system is based around the fact that each file in a filesystem is
identifiable by a 32-bit integer (see [doc/sys/file]).

What we do is that every time we load a file, we add its path ID to a linked
list called "floaded". Then, when we want to know whether a path has been
loaded, we traverse this list, looking for a match.

## Contexts

The combination of "sysdict" and "floaded" is what we call a Context. In Dusk,
contexts can be forked to create multiple little subsystems, which allows us to
easily solve name clashes. The convenience layer for this lives at
[doc/lib/context].

For example, assemblers often use the same mnemonic words, so loading two
assemblers in the same context results in an unusable frankenstein assembler.

What you can do instead is fork the system context, load an assembler, then go
back to the fork point, load another assembler. When you want to use a
particular assembler, you activate a context, do your stuff, then activate
another context.

A Context has this structure:

12b dict link ("sysdict" word points to context+8, see "dict structure" above)
8b  floaded   (4b "next", 4b "FS ID")

Dusk OS has the word "CURCONTEXT" which yields the address of a pointer to the
currently active context. In other words, "sysdict" is "CURCONTEXT @ 8 +" and
"floaded" is "CURCONTEXT @ 12 +".

"SYSCONTEXT" is a constant that points to the system context. "system ( -- )"
sets "CURCONTEXT" to "SYSCONTEXT".
