doc/devel/source/types.en.tm

   1 <TeXmacs|1.0.0.17>
   2
   3 <style|tmdoc>
   4
   5 <\body>
   6   <expand|tmdoc-title|Basic data types>
   7
   8   In this chapter, we give a rough description of <apply|TeXmacs>'s basic
   9   data types in <verbatim|Basic>. The description of the exported functions
  10   is non exhaustive and we refer to the corresponding header files for more
  11   precision.
  12
  13   <section|Memory allocation and data structures in TeXmacs>
  14
  15   The file <verbatim|fast_alloc.hpp> declares the <apply|TeXmacs> memory
  16   allocation routines. These routines are very fast for small sizes, since
  17   for each such size, <apply|TeXmacs> maintains a linked list of freed
  18   objects of that size. No garbage collection has been implemented yet.
  19
  20   Modulo a few exceptions, all <apply|TeXmacs> composite data structures are
  21   based on the modules <verbatim|concrete>, <verbatim|abstract>,
  22   <verbatim|concrete_null> and <verbatim|abstract_null>. Consequently, these
  23   data structures are pointers to representation classes, which may be
  24   abstract in the case of <verbatim|abstract> and <verbatim|abstract_null>,
  25   and which always contain a reference counter. Because of the reference
  26   counter, the C++ copy operator is very fast. Most of the implemented data
  27   structures also export a function <verbatim|copy>, which should be used if
  28   one really wants to physically duplicate an object,
  29
  30   For classes constructed using <verbatim|concrete_null> or
  31   <verbatim|abstract_null>, the pointer to the representation class is
  32   allowed to be <verbatim|NULL> and we have a default constructor which
  33   initializes this pointer with <verbatim|NULL>. Instances of these classes
  34   are tested to be <verbatim|NULL> using the function <verbatim|nil>.
  35   Examples of such classes are lists, files and widgets.
  36
  37   <section|Array-like structures>
  38
  39   <apply|TeXmacs> implements three ``array-like'' structures:
  40
  41   <\itemize>
  42     <item><verbatim|string> is the string type, which may contain '0'
  43     characters.
  44
  45     <item><verbatim|tree> is the tree type with string labels.
  46
  47     <item><verbatim|array\<less\>T\<gtr\>> is the generic array type with
  48     elements of type <verbatim|T>.
  49   </itemize>
  50
  51   Array-like structures export the following operations:
  52
  53   <\itemize>
  54     <item><verbatim|N> computes the length of an array.
  55
  56     <item><verbatim|[]> accesses an element.
  57
  58     <item><verbatim|\<less\>\<less\>> is used for appending elements or
  59     arrays.
  60   </itemize>
  61
  62   For trees <verbatim|t>, we notice that <verbatim|t-\<gtr\>label> yields the
  63   label of the tree and <verbatim|t-\<gtr\>a> the array of its children. The
  64   second argument of <verbatim|\<less\>\<less\>> for trees is either a tree
  65   or an array of trees.
  66
  67   The implementation has been made such that the <verbatim|\<less\>\<less\>>
  68   operation is fast, which is useful when considering arrays as buffers.
  69   Actually, the allocated space for arrays with more than five elements
  70   (words for strings) is always a power of two, so that new elements can be
  71   appended quickly. Notice that GNU malloc also always allocates blocks,
  72   whose sizes are powers of two. Therefore, we do not waste memory for small
  73   and large arrays.
  74
  75   <section|Lists>
  76
  77   Generic lists are implemented by the class <verbatim|list\<less\>T\<gtr\>>.
  78   The ``nil'' list is created using <verbatim|list\<less\>T\<gtr\>()>, an
  79   atom using <verbatim|list\<less\>T\<gtr\>(T x)> and a general list using
  80   <verbatim|list\<less\>T\<gtr\>(T x, list\<less\>T\<gtr\> next)>. If
  81   <verbatim|l> is a list, <verbatim|l-\<gtr\>item> and
  82   <verbatim|l-\<gtr\>next> correspond to its label and its successor
  83   respectively (<verbatim|car> and <verbatim|cdr> in lisp). The functions
  84   <verbatim|nil> and <verbatim|atom> tests whether a list is nil or an atom.
  85   The function <verbatim|N> computes the length of a list.
  86
  87   The type <verbatim|list\<less\>T\<gtr\>> is also denoted by
  88   <verbatim|path>, because some additional functions are defined for it.
  89   Indeed, paths are used for accessing descendents in tree like structures.
  90   For instance, we implemented the function <verbatim|tree subtree (tree t,
  91   path p)>.
  92
  93   <section|Hash tables>
  94
  95   The <verbatim|hashmap\<less\>T,U\<gtr\>> class implements hash tables with
  96   entries in <verbatim|T> and values in <verbatim|U>. A function
  97   <verbatim|hash> should be implemented for <verbatim|T>. Given a hash table
  98   <verbatim|H>. We set elements through\
  99
 100   <\verbatim>
 101     \ \ \ \ H(x)=y;
 102   </verbatim>
 103
 104   and access to elements through\
 105
 106   <\verbatim>
 107     \ \ \ \ H[x]
 108   </verbatim>
 109
 110   We also implemented a variant <verbatim|rel_hashmap\<less\>T,U\<gtr\>> of
 111   hash tables, which also have a list-like structure, which makes them useful
 112   for implementing recursive environments.
 113
 114   <section|Other data structures>
 115
 116   <\itemize>
 117     <item><verbatim|command> implements abstract commands.
 118
 119     <item><verbatim|file> implements files.
 120
 121     <item><verbatim|iterator\<less\>T\<gtr\>> implements generic iterators.
 122
 123     <item><verbatim|rectangles> implements rectangles and lists of
 124     rectangles.
 125
 126     <item><verbatim|space> implements stretchable spaces.
 127
 128     <item><verbatim|timer> implements timers.
 129   </itemize>
 130
 131   <apply|tmdoc-copyright|1998--2002|Joris van der Hoeven>
 132
 133   <expand|tmdoc-license|Permission is granted to copy, distribute and/or
 134   modify this document under the terms of the GNU Free Documentation License,
 135   Version 1.1 or any later version published by the Free Software Foundation;
 136   with no Invariant Sections, with no Front-Cover Texts, and with no
 137   Back-Cover Texts. A copy of the license is included in the section entitled
 138   "GNU Free Documentation License".>
 139 </body>
 140
 141 <\initial>
 142   <\collection>
 143     <associate|paragraph width|150mm>
 144     <associate|odd page margin|30mm>
 145     <associate|shrinking factor|4>
 146     <associate|page right margin|30mm>
 147     <associate|page top margin|30mm>
 148     <associate|reduction page right margin|25mm>
 149     <associate|page type|a4>
 150     <associate|reduction page bottom margin|15mm>
 151     <associate|even page margin|30mm>
 152     <associate|reduction page left margin|25mm>
 153     <associate|page bottom margin|30mm>
 154     <associate|reduction page top margin|15mm>
 155     <associate|language|english>
 156   </collection>
 157 </initial>
 158
 159 <\references>
 160   <\collection>
 161     <associate|toc-5|<tuple|<uninit>|?>>
 162     <associate|toc-1|<tuple|<uninit>|?>>
 163     <associate|idx-1|<tuple|<uninit>|?>>
 164     <associate|idx-2|<tuple|<uninit>|?>>
 165     <associate|toc-2|<tuple|<uninit>|?>>
 166     <associate|toc-3|<tuple|<uninit>|?>>
 167     <associate|toc-4|<tuple|<uninit>|?>>
 168   </collection>
 169 </references>
 170
 171 <\auxiliary>
 172   <\collection>
 173     <\associate|toc>
 174       Memory allocation and data structures in
 175       TeXmacs<value|toc-dots><pageref|toc-1>
 176
 177       Array-like structures<value|toc-dots><pageref|toc-2>
 178
 179       Lists<value|toc-dots><pageref|toc-3>
 180
 181       Hash tables<value|toc-dots><pageref|toc-4>
 182
 183       Other data structures<value|toc-dots><pageref|toc-5>
 184     </associate>
 185   </collection>
 186 </auxiliary>