doc/convext/ds.tex

   1 \chapter{Data Structures}
   2
   3 In the course of developing \converse{} and \charmpp{} we had to
   4 implement a number of data structures efficiently. If the ANSI
   5 standard \CC{} library were available to us on all platforms, we could
   6 have used it, but that was not the case. Also, we needed both the C and C++
   7 bindings of most data structures. In most cases, the functionality we needed
   8 was also a subset of the \CC{} standard library functionality, and by
   9 avoiding virtual methods etc, we have tried to code the most efficient
  10 implementations of those data structures.
  11
  12 Since these data structures are already part of \converse{} and \charmpp{},
  13 they are available to the users of these system free of cost \verb+:-<)+.
  14 In this chapter we document the available functions.
  15
  16 \section{Queues, Lists, FIFOs etc.}
  17
  18 This data structure is based on circular buffer, and can be used both like
  19 a FIFO and a Stack.
  20
  21 Following functions are available for use in C:
  22
  23 \function{typedef ... CdsFifo;}
  24 \desc{An opaque data type representing a queue of {\tt void*} pointers.}
  25
  26 \function{CdsFifo CdsFifo\_Create(void);}
  27 \desc{Creates a queue in memory and returns its pointer.}
  28
  29 \function{CdsFifo CdsFifo\_Create\_len(int len);}
  30 \desc{Creates a queue in memory with the initial buffer size of len entries
  31 and returns its pointer.}
  32
  33 \function{void CdsFifo\_Enqueue(CdsFifo q, void *elt);}
  34 \desc{Appends \uw{elt} at the end of \uw{q}.}
  35
  36 \function{void *CdsFifo\_Dequeue(CdsFifo q);}
  37 \desc{Removes an element from the front of the \uw{q}, and returns it. Returns
  38 0 if the queue is empty.}
  39
  40 \function{void *CdsFifo\_Pop(CdsFifo q);}
  41 \desc{Removes an element from the front of the \uw{q}, and returns it. Returns
  42 0 if the queue is empty. An alias for the dequeue function.}
  43
  44 \function{void CdsFifo\_Push(CdsFifo q, void *elt);}
  45 \desc{Inserts \uw{elt} in the beginning of \uw{q}.}
  46
  47 \function{int CdsFifo\_Empty(CdsFifo q);}
  48 \desc{Returns 1 if the \uw{q} is empty, 0 otherwise.}
  49
  50 \function{int CdsFifo\_Length(CdsFifo q);}
  51 \desc{Returns the length of the \uw{q}.}
  52
  53 \function{int CdsFifo\_Peek(CdsFifo q);}
  54 \desc{Returns the element from the front of the \uw{q} without removing it.}
  55
  56 \function{void CdsFifo\_Destroy(CdsFifo q);}
  57 \desc{Releases memory used by \uw{q}.}
  58
  59 Following Templates are available for use in \CC{}:
  60
  61 \begin{alltt}
  62 template<class T>
  63 class CkQ \{
  64   CkQ();  // default constructor
  65   CkQ(int initial_size); // constructor with initial buffer size
  66   ~CkQ(); // destructor
  67   int length(void); // returns length of the q
  68   bool isEmpty(void); // returns true if q is empty, false otherwise
  69   T deq(void); // removes and returns the front element
  70   void enq(const T\&); // appends at the end of the list
  71   void push(const T\&); // inserts in the beginning of the list
  72   T\& operator[](size_t n); // returns the n'th element
  73 \};
  74 \end{alltt}
  75