4. Data Structures

In the course of developing Converse and Charm++ we had to implement a number of data structures efficiently. If the ANSI standard C++ 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 C++ 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 Charm++ , they are available to the users of these system free of cost :-<). In this chapter we document the available functions.

4.1 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:

typedef ... CdsFifo;
An opaque data type representing a queue of void* pointers.

CdsFifo CdsFifo_Create(void);
Creates a queue in memory and returns its pointer.

CdsFifo CdsFifo_Create_len(int len);
Creates a queue in memory with the initial buffer size of len entries and returns its pointer.

void CdsFifo_Enqueue(CdsFifo q, void *elt);
Appends elt at the end of q.

void *CdsFifo_Dequeue(CdsFifo q);
Removes an element from the front of the q, and returns it. Returns 0 if the queue is empty.

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

void CdsFifo_Push(CdsFifo q, void *elt);
Inserts elt in the beginning of q.

int CdsFifo_Empty(CdsFifo q);
Returns 1 if the q is empty, 0 otherwise.

int CdsFifo_Length(CdsFifo q);
Returns the length of the q.

int CdsFifo_Peek(CdsFifo q);
Returns the element from the front of the q without removing it.

void CdsFifo_Destroy(CdsFifo q);
Releases memory used by q.

Following Templates are available for use in C++ :

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
  bool isEmpty(void); // returns true if q is empty, false 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