\chapter{Data Structures}

In the course of developing \converse{} and \charmpp{} we had to
implement a number of data structures efficiently. If the ANSI
standard \CC{} library were available to us on all platforms, we could
have used it, but that was not the case. Also, we needed both the C and C++
bindings of most data structures. In most cases, the functionality we needed
was also a subset of the \CC{} standard library functionality, and by
avoiding virtual methods etc, we have tried to code the most efficient
implementations of those data structures.

Since these data structures are already part of \converse{} and \charmpp{},
they are available to the users of these system free of cost \verb+:-<)+.
In this chapter we document the available functions.

\section{Queues, Lists, FIFOs etc.}

This data structure is based on circular buffer, and can be used both like
a FIFO and a Stack.

Following functions are available for use in C:

\function{typedef ... CdsFifo;}
\desc{An opaque data type representing a queue of {\tt void*} pointers.}

\function{CdsFifo CdsFifo\_Create(void);}
\desc{Creates a queue in memory and returns its pointer.}

\function{CdsFifo CdsFifo\_Create\_len(int len);}
\desc{Creates a queue in memory with the initial buffer size of len entries
and returns its pointer.}

\function{void CdsFifo\_Enqueue(CdsFifo q, void *elt);}
\desc{Appends \uw{elt} at the end of \uw{q}.}

\function{void *CdsFifo\_Dequeue(CdsFifo q);}
\desc{Removes an element from the front of the \uw{q}, and returns it. Returns
0 if the queue is empty.}

\function{void *CdsFifo\_Pop(CdsFifo q);}
\desc{Removes an element from the front of the \uw{q}, and returns it. Returns
0 if the queue is empty. An alias for the dequeue function.}

\function{void CdsFifo\_Push(CdsFifo q, void *elt);}
\desc{Inserts \uw{elt} in the beginning of \uw{q}.}

\function{int CdsFifo\_Empty(CdsFifo q);}
\desc{Returns 1 if the \uw{q} is empty, 0 otherwise.}

\function{int CdsFifo\_Length(CdsFifo q);}
\desc{Returns the length of the \uw{q}.}

\function{int CdsFifo\_Peek(CdsFifo q);}
\desc{Returns the element from the front of the \uw{q} without removing it.}

\function{void CdsFifo\_Destroy(CdsFifo q);}
\desc{Releases memory used by \uw{q}.}

Following Templates are available for use in \CC{}:

\begin{alltt}
template<class T>
class CkQ \{
  CkQ();  // default constructor
  CkQ(int initial_size); // constructor with initial buffer size
  ~CkQ(); // destructor
  int length(void); // returns length of the q
  CmiBool isEmpty(void); // returns CmiTrue if q is empty, CmiFalse otherwise
  T deq(void); // removes and returns the front element
  void enq(const T\&); // appends at the end of the list
  void push(const T\&); // inserts in the beginning of the list
  T\& operator[](size_t n); // returns the n'th element
\};
\end{alltt}

