11. AVAILABLE ORGANIZATIONS

11.1 RING
11.2 COLLECTION
11.3 AGGREGATION (TRIANGLE, hierarchy)
11.4 TREE
11.5 GRAPH
11.6 LINK and NAME
11.7 STACK
11.8 ENTITY_RELATIONSHIP MODEL
11.9 Run-time Extensibility (PROPERTY)
11.10 Run-time Detection (SELF_ID)
11.11 Time Stamp (TIME_STAMP)
11.12 Dynamic Array and Binary Heap (ARRAY)
11.13 Hash Tables (HASH)
11.14 Pager (PAGER)
11.15 Access to Type Tables (TYPE)

This chapter describes the data organizations and hardwired features currently available from the library.

Only a conceptual introduction to each organization is presented. For programming details, including examples, use one of the following sources:

Although the library already contains all the essential organizations, it is still growing. We provide our active users with regular updates.

All OrgC++ organizations are based on a ring-type arrangement, not on a NULL-ending list. The two arrangements are similar in access and performance, but a RING has several advantages: head and tail are represented by the same pointer, handling is more uniform, and a NULL pointer cannot occur within a valid organization. The last property is the key to run-time protection against dangling pointers in OrgC++.

With the exception of the GENERAL_LINK, OrgC++ structures are strongly typed. This has the advantage of the code being thoroughly checked by the compiler, but requires special handling of heterogenous objects. For example, if we declare

ZZ_HYPER_SINGLE_RING(aRing,Apple);
ZZ_HYPER_SINGLE_RING(oRing,Orange);

aRing may contain only Apples but no Oranges, and oRing may contain only Oranges but no Apples. Neither of the two rings may contain Plums or Pears.

Heterogeneous situations can be handled easily either by using a virtual function - see the example in Chap. 7.3- or by combining GENERAL_LINK with other OrgC++ organizations. For example, in addition to Apples and Oranges, we can declare a general object called Fruit. Then

ZZ_HYPER_SINGLE_RING(fRing,Fruit);
ZZ_HYPER_GENERAL_LINK(fLink,Fruit);

describes a RING of Fruits, that may be anything, including Pears or Plums. GENERAL_LINK provides the link between the general object (Fruit) and the particular object (Apple,Orange, Plum, ...).

Most organizations automatically provide an iterator, which lets you to walk through the entire data set. Singly linked organizations let you walk only head to tail, using either function fwd() (short for 'forward') or iterator operator ++. For convenience, we recommend you to use macro ITERATE(iterator,objPtr){...} which hides a for loop using operator ++. For examples, see orgc/test/test50.c.

Doubly linked organizations allow you to traverse the data also in the reverse direction, using either function bwd() (short for 'backward') or iterator operator--!!TODO - Check with Jiri. Again, we recommend you using convenient macro RETRACE, which is just like ITERATE, except that it traverses the data tail to head.

Macros ITERATE and RETRACE hide normal for(..) loops, and therefore can include continue statements. These loops can also be nested at any number of levels. Note however that operators ++ and -- are designed only for straight traversal of the whole set. For example, you cannot mix the use of ++ and -- within one loop. If you need to perform some complex traversal of the data, going back and forth over it, use functions fwd() and bwd() they have no limitations.

11.1 RING

Purpose:

List - RING can serve the same purpose as a NULL-ending list;
Queue - objects can be retrieved in the same/reverse order as they are loaded.

IMPORTANT: This organization represents a ring without the encapsulated entry point, which must be managed externally. If you need a fully encapsulated ring, look at COLLECTION (Chap.11.2).

SINGLE_ and DOUBLE_RING:

Both RINGS behave identically, except that the DELETE operation is much faster for the DOUBLE_RING. In applications where DELETE is not used frequently, SINGLE_RING is a better choice (it is faster, and needs less memory).

Sorting:

The sort() function sorts a given ring. You provide your own compare function, as you do with qsort(). See the example in test 15a.c. Note that sort() which is based on the merge algorithm, is generally faster than qsort().

Adding and deleting objects:

In our library, a ring (or circular list) is a structure existing on a set of objects, without any start/tail pointer encapsulated in a special class. If you want a ring with an encapsulated entry point, use COLLECTION or AGGREGATE.

Since the entry to the ring is not encapsulated, you have to keep it externally yourself, otherwise the ring would be there, but you would not know how to get to it. The entry is also important if you are concerned about the order of the objects in the ring. The entry to the ring will be returned as the last element when traversing the ring.

Before you start to use any ring, set entry=NULL. Use add() to add an object after start, ins() to insert it before entry (you can only do that for a DOUBLE_RING), and del() to delete an object.

Order of objects:

If you represent a RING as a sequence of objects, starting from the entry object, then the RING behaves in the following manner:

empty RING adding A gives A
A adding B gives AB
AB adding C gives ACB
ACB adding D gives ADCB
ADCB deleting C gives ADB
ADB deleting A gives BD

If you want to return objects in the same order as they were added to the ring, two methods can be used: Either use a DOUBLE_RING and the iterator instead of the ++ iterator (see below on the interators), or reset the entry after each object is added. The first method works for a DOUBLE ring only, the second method works for both SINGLE and DOUBLE rings. Here is an example of the second method (resetting the entry point):

entry=NULL; /* initialize start before using the ring*/
...
entry=myRing.add(entry,p1);
entry=p1;
...
entry=myRing.add(entry,p2);
entry=p2;
...

This method will store objects in the order in which they were loaded, because the entry represents the 'tail' of the ring.

empty RING adding A gives A
A adding B gives BA
AB adding C gives CAB
ACB adding D gives DABC

When running this sequence through the iterator you get: A,B,C,D.

Merging or Splitting Rings

It is interesting (see the diagram on the following page) that the same operation with pointers provides merge/split operations, depending on whether the two given points are in the same ring, or in two different rings.

Algorithm: For given points A and C, disconnect pointers to B (which is next to A) and to D (which is next to C). Then connect A to D and C to B.

If A and C were originally on the same ring, the operation results in splitting the ring; A is on one ring, and C is on the other ring. If A and C were originally on different rings, the operation merges the two rings into one. One command, merge(), serves both operations. If you want to extract a single object and make it a new ring, do this:

ZZ_HYPER_SINGLE_RING(myRing,Obj);
...
Obj *p1,*p2;
p2=myRing.fwd(p1);
p1=myRing.merge(p1,p2);
// now p2 forms a single object ring,
// remaining objects are on the p1 ring

Moving around the RING:

Use an iterator to move around a RING:

myRing_iterator it(p1);
while(p2= ++it){
...
}

For example, for ring ADCB, this loop returns D,C,B,A.

fwd() returns the next object in the chain (right neighbour).
bwd()
, which is defined only for the organization DOUBLE_RING, returns the previous object, and allows traversal of objects in reverse order. del() can be used while traversing the set with the iterator.

If you call bwd() for a SINGLE_RING, the compiler will detect an error.

Syntax:

The syntax is the same for single/double rings:

ZZ_HYPER_SINGLE_RING(id,TYPE);
ZZ_HYPER_DOUBLE_RING(id,TYPE);

declare singly/doubly-linked rings,

TYPE* id.add(TYPE *entry,TYPE *newObj);

Adds new object newObj to the ring with entry point entry and returns a new entry. For an empty ring, set entry=NULL before this call.

TYPE* id.del(TYPE *entry,TYPE *remObj);

Deletes remObj from the ring, and returns the new tail of the ring. If remObj is the tail before the call, the new tail will be different. If remObj is the last object in the ring, the function returns NULL.

TYPE* id.sort(int (*cmpFun)(const void*,const void*), TYPE *entry);

Sorts a ring, using cmpFun() to compare objects. In most cases, entry will change after this call.

TYPE* id.merge(TYPE *obj1,TYPE *obj2);

If the two objects are on the same ring, this splits the ring into two. If the objects are on different rings, it merges the rings. Always returns obj1.

TYPE* id.fwd(TYPE *obj);

For a given object, it returns the next object on the ring. If the object is not connected to any ring, it returns next=NULL

TYPE *entry,*obj
id_iterator it(entry);
while(obj= ++it){ ... };

This traverses the ring with entry point entry.

it.start(entry); //restarts the same loop

Commands available only for the DOUBLE_RING:

TYPE* id.bwd(TYPE *obj);

For a given object, the function returns the previous object in the ring. If the object is not in any ring, it returns NULL.

void id.ins(TYPE *obj,TYPE *newObj);

Inserts newObj before obj.

TYPE *entry,*obj;
id_iterator it(entry);
while(obj=it---){ ... };

This traverses the ring in the opposite direction.

it.start(entry); //restarts the same loop

Examples:

  1. List of cell instances and list of signal nets on a VLSI chip (test2.c).
  2. Employee records sorted into two rings: one by employee name and one by salary (test15a).
  3. Loading Blocks and Nets into netlist without reversing the order (test0a.c).

Warning: The ZORTECH C++ version of OrgC++ does not contain the sort() function. Instead, the macro ZZ_SORT() must be used, as is used in plain OrgC.

 

Chapter 10: Org C++ Library Next Section: 11.2 COLLECTION