
\chapter{Basic data structures}

In this chapter, we give a rough description of \TeXmacs's basic data types
in ¤Basic¤. The description of the exported functions is non exhaustive and
we refer to the corresponding header files for more precision.

\section{Memory allocation and data structures in TeXmacs}

The file ¤fast_alloc.gen.h¤ declares the \TeXmacs\ memory allocation routines.
These routines are very fast for small sizes, since for each such size,
\TeXmacs\ maintains a linked list of freed objects of that size.
No garbage collection has been implemented yet.

Modulo a few exceptions, all \TeXmacs\ composite data structures are based on
the modules ¤concrete¤, ¤abstract¤, ¤concrete_null¤ and ¤abstract_null¤.
Consequently, these data structures are pointers to representation classes,
which may be abstract in the case of ¤abstract¤ and ¤abstract_null¤,
and which always contain a reference counter.
Because of the reference counter, the C++ copy operator is very fast.
Most of the implemented data structures also export a function ¤copy¤,
which should be used if one really wants to physically duplicate an object,

For classes constructed using ¤concrete_null¤ or ¤abstract_null¤,
the pointer to the representation class is allowed to be ¤NULL¤ and
we have a default constructor which initializes this pointer with ¤NULL¤.
Instances of these classes are tested to be ¤NULL¤ using the function ¤nil¤.
Examples of such classes are lists, files and widgets.

\section{Array-like structures}

\TeXmacs\ implements three ``array-like'' structures:
\begin{itemize}
  \item ¤string¤ is the string type, which may contain '0' characters.
  \item ¤tree¤ is the tree type with string labels.
  \item ¤array<T>¤ is the generic array type with elements of type ¤T¤.
\end{itemize}
Array-like structures export the following operations:
\begin{itemize}
  \item ¤N¤ computes the length of an array.
  \item ¤[]¤ accesses an element.
  \item ¤<<¤ is used for appending elements or arrays.
\end{itemize}
For trees ¤t¤, we notice that ¤t->label¤ yields the label
of the tree and ¤t->a¤ the array of its children.
The second argument of ¤<<¤ for trees is either
a tree or an array of trees.

The implementation has been made such that the ¤<<¤ operation is fast,
which is useful when considering arrays as buffers.
Actually, the allocated space for arrays with more than
five elements (words for strings) is always a power of two,
so that new elements can be appended quickly.
Notice that GNU malloc also always allocates blocks,
whose sizes are powers of two. Therefore,
we do not waste memory for small and large arrays.

\section{Lists}

Generic lists are implemented by the class ¤list<T>¤.
The ``nil'' list is created using ¤list<T>()¤, an atom using
¤list<T>(T x)¤ and a general list using ¤list<T>(T x, list<T> next)¤.
If ¤l¤ is a list, ¤l->item¤ and ¤l->next¤ correspond to
its label and its successor respectively (¤car¤ and ¤cdr¤ in lisp).
The functions ¤nil¤ and ¤atom¤ tests whether a list is nil or an atom.
The function ¤N¤ computes the length of a list.

The type ¤list<T>¤ is also denoted by ¤path¤,
because some additional functions are defined for it.
Indeed, paths are used for accessing descendents in
tree like structures. For instance, we implemented
the function ¤tree subtree (tree t, path p)¤.

\section{Hash tables}

The ¤hashmap<T,U>¤ class implements hash tables with entries
in ¤T¤ and values in ¤U¤. A function ¤hash¤ should be implemented for ¤T¤.
Given a hash table ¤H¤. We set elements through
\begin{verbatim}
    H(x)=y;
\end{verbatim}
and access to elements through
\begin{verbatim}
    H[x]
\end{verbatim}
We also implemented a variant ¤rel_hashmap<T,U>¤ of hash tables,
which also have a list-like structure, which makes them useful
for implementing recursive environments.

\section{Other data structures}

\begin{itemize}
  \item ¤command¤ implements abstract commands.
  \item ¤file¤ implements files.
  \item ¤iterator<T>¤ implements generic iterators.
  \item ¤rectangles¤ implements rectangles and lists of rectangles.
  \item ¤space¤ implements stretchable spaces.
  \item ¤timer¤ implements timers.
\end{itemize}
