Types de données élémentaires

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.

1.Memory allocation and data structures in TeXmacs

The file fast_alloc.hpp 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.

2.Array-like structures

TeXmacs implements three “array-like” structures:

• string is the string type, which may contain '0' characters.
• tree is the tree type with string labels.
• array<T> is the generic array type with elements of type T.

Array-like structures export the following operations:

• N computes the length of an array.
• [] accesses an element.
• << is used for appending elements or arrays.

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.

3.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).

4.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

    H(x)=y;

and access to elements through

    H[x]

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.

5.Other data structures

• command implements abstract commands.
• file implements files.
• iterator<T> implements generic iterators.
• rectangles implements rectangles and lists of rectangles.
• space implements stretchable spaces.
• timer implements timers.