Idea

New data structures are needed in CIVL-C in order to model what happens in OpenMP and other complex APIs. Sequences, sets, and maps, specifically. The purpose of this page is to propose the new interface for these structures.

Typeof

First we need a new expression $typeof. This expression has the syntax $typeof(typename). It is just like sizeof syntactically. It represents any type as a value. The type of the $typeof expression is the type $type. This is also represented in the CIVL model layer as "dynamic type".

Sequences

This is an abstract datatype for an immutable (functional) sequence of elements of the same type.

New type: $seq. Functions:

/* Returns the empty seq whose elements (if it had any)
 * would have the given type.  The type becomes associated
 * with the seq.  */
$seq $seq_empty($type type);

/* Returns the type of an element that goes in this seq */
$type $seq_element_type($seq v);

/* Returns the seq that is like the given one but with one more
 * element added.  A runtime exception is generated if the thing pointed
 * to by eltptr doesn't have the right type for v. */
$seq $seq_add($seq v, void * eltptr);

/* Returns the seq that is like the given one but with the element
 * at position index removed and the subsequent elements shifted down */
$seq $seq_remove($seq v, int index);

/* Returns the seq that is like the given one but with the element
 * at position index replaced with whatever object is pointed to by
 * ptr. */
$seq $seq_set($seq v, int index, void * ptr);

/* Returns the length of the seq (i.e., the number of elements) */
int $seq_length($seq v);

/* Returns the seq that is like the given one but with an element
 * inserted at position i (and the subsequent elements shifted up).
 * The parameter eltptr is a pointer to the element to insert. */
$seq $seq_insert($seq v, int index, void * eltptr);

/* Gets the element at position index and stores it in wherever
 * ptr points to. */
void $seq_get($seq v, int index, void * ptr);

/* Returns the subsequence */
$seq $seq_sub($seq v, int start, int stop);

/* Returns the concatenation of the two sequences */
$seq $seq_concat($seq s1, $seq s2);

Sets

Should we make it an ordered set, $oset?

New type: $set. Functions:

/* Returns the empty set whose elements (if it had any)
 * would have the given type.  The type becomes associated
 * with the set.  */
$set $set_empty($type type);

/* Returns the type of an element that goes in this set */
$type $set_element_type($set v);

/* Returns the set that is like the given one but with one more
 * element added.  A runtime exception is generated if the thing pointed
 * to by eltptr doesn't have the right type for s. */
$set $set_add($set v, void * eltptr);

/* Returns the set that is like the given one but with the specified element
 * removed.  If the set does not contain the element the set returned
 * will equal the given one. */
$set $set_remove($set s, void * eltptr);

/* Does the set contain the specified element? */
_Bool $set_contains($set s, void * eltptr);

$set $set_union($set s1, $set s2);

$set $set_intersection($set s1, $set s2);

$set $set_difference($set s1, $set s2);

/* Returns the singleton set consisting of the single element
 * specified by the pointer and the type */
$set $set_single($type type, void * eltptr);

// need a way to iterate over elements of a set.

Maps

$map

$map $map_empty($type keyType, $type valType);

$map $map_put($map map, void * keyPtr, void * valPtr);

void $map_get($map map, void * keyPtr, void * resultPtr);

$map $map_removeKey($map map, void * keyPtr);