Started documenting Converse data structures.
authorMilind Bhandarkar <milind@cs.uiuc.edu>
Sun, 17 Dec 2000 11:34:01 +0000 (11:34 +0000)
committerMilind Bhandarkar <milind@cs.uiuc.edu>
Sun, 17 Dec 2000 11:34:01 +0000 (11:34 +0000)
doc/convext/ds.tex [new file with mode: 0644]
doc/convext/manual.tex

diff --git a/doc/convext/ds.tex b/doc/convext/ds.tex
new file mode 100644 (file)
index 0000000..b61d39f
--- /dev/null
@@ -0,0 +1,75 @@
+\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}
+
index a18af18168546dd609e8db096e26a5cd3736ee5d..dbd4058198c75f3640156ca18aa2474e364abed7 100644 (file)
@@ -24,6 +24,7 @@ these modules along with \converse{} as a convenience.  {\em You don't
 need to read any part of this manual to use \converse{}.}
 
 \input{msgmgr}
+\input{ds}
 \input{random}
 \input{cpm}
 \input{cldb}