Cicada strings are all stored in linked lists, and when a Cicada script calls a user-defined C function any string arguments are passed as linkedlist structure variables. The linkedlist data type is defined in lnklst.h, so that header file needs to be included in any C source file that uses Cicada strings. lnklst.h also prototypes the functions that help the user read, write, and resize these strings. The lnklst source files were written for Cicada, but they are completely stand-alone and can be used in other C programs.
The linkedlist data type is defined as follows:
typedef struct {
ccInt elementNum;
sublistHeader *memory;
ccInt elementSize;
ccFloat spareRoom;
} linkedlist;
The only field relevant for Cicada strings is elementNum, which stores the number of characters (bytes) in the string. memory points to the first storage sublist, while elementSize should always be 1 (the byte-size of a character). spareRoom is amount of extra room to allocate in sublists relative to elementNum; this extra space uses memory but can speed up the insertion of new elements.
Here is an example of how to use a linked list in a C function.
ccInt doubleString(ccInt argc, char **argv)
{
linkedlist *theString = (linkedlist *) argv[0];
ccInt numInitChars = theString->elementNum;
addElements(theString, numInitChars, ccFalse);
copyElements(theString, 1, theString, numInitChars+1, numInitChars);
return 0;
}
Notice that we used a data type defined in lnklst.h called ccInt, which is (by default) just an int type. The reason for this is that we can change the default integer type to some other signed integer -- for example a short or long int type -- by changing the typedef at the beginning of lnklst.h along with the two integer limits defined below it. We can also change Cicada’s default floating-point type here. If we do this then we should also change the format-string constants at the beginning of cmpile.c.
There are two rules to keep in mind when using linked lists, to avoid crashing Cicada. 1) The linkedlist variable should only be updated by Cicada’s linked list routines. 2) Whenever a linked list is updated the original linkedlist variable (i.e. Cicada’s own copy) must be updated as well. Therefore it is critical that linked lists always be passed by reference to any C routine that could conceivably modify that list.
newLinkedList()
syntax: (numeric) err_code = newLinkedList((linkedlist *) LL, (numeric) element_num, element_size, spare_room, (Boolean) if_cleared)
Allocates the memory for a new linked list. The linkedlist variable itself is not created; rather its memory field is filled with a pointer to a newly-allocated sublist. The first three arguments are just three of the fields of the linkedlist data type described above: the initial number of elements, the byte size of each element, and the percentage of extra room to maintain in the list. The final argument, if set, zeros the memory of the linked list.
deleteLinkedList()
syntax: deleteLinkedList((linkedlist *) LL)
De-allocates the storage of a linked list. The actual variable of type linkedlist is not itself deleted, but its memory pointer is set to zero, indicating that the list is no longer defined.
insertElements()
syntax: (numeric) err_code = insertElements((linkedlist *) LL, (numeric) insertion_point, new_elements, (Boolean) if_cleared)
Adds elements to the beginning, middle or end of a linked list. The elements are added before the specified existing index. So to add before the first element we must set the insertion-point argument to 1; to add after the final existing element we set that argument to the number of current elements plus one. The number of new elements to add is given by the third argument. The fourth argument, if set, zeros the new memory.
Each linked list has a field signifying the amount of spare room it should try to maintain in the list. This spare room takes up more memory, but it can improve the speed with which lists are resized, since adding new elements may not require allocating more sublists if the existing ones have the extra space. When there is not enough room, insertElements() creates and inserts new sublists, again with the extra storage specified in the spareRoom field of the linked list variable.
addElements()
syntax: (numeric) err_code = addElements((linkedlist *) LL, (numeric) new_elements, (Boolean) if_cleared)
Same as insertElements(), except that the elements are appended to the end of the existing list. (This is equivalent to calling insertElements with an insertion point of elementNum+1.)
deleteElements()
syntax: (numeric) err_code = deleteElements((linkedlist *) LL, (numeric) first_index, last_index)
Removes a given range of elements from the linked list. (This is not the same as zeroing the elements!) The range of elements to delete includes the first and last indices, so for example a range of {4, 6} removes three elements.
deleteElement()
syntax: (numeric) err_code = deleteElement((linkedlist *) LL, (numeric) element_index)
Same as deleteElements() except only deletes one element.
resizeLinkedList()
syntax: (numeric) err_code = resizeLinkedList((linkedlist *) LL, (numeric) num_elements, (Boolean) if_cleared)
Adds elements to the end, or deletes elements from the end, so that the linked list will have the required number of elements. If elements are being added then they will be zeroed if and only if if_cleared is set to true (ccTrue).
defragmentLinkedList()
syntax: (numeric) err_code = defragmentLinkedList((linkedlist *) LL)
Rearranges the linked list’s storage into one contiguous block of memory. A linked list is ordinarily broken up over a number of sublists, since that reduces the amount of memory shuffling that has to occur when elements are inserted or removed. If there will be no resizing of the list then it is faster to work with when it is de-fragmented, and it can save memory too (even when spareRoom is 0).
The call() function defragments all of its string-arguments before executing a user-defined C or C++ routine.
copyElements()
syntax: [(numeric) err_code =] copyElements((linkedlist *) source_LL, (numeric) first_source_index, (linkedlist *) dest_list, (numeric) first_dest_index, num_elements_to_copy)
Copies data between two linked lists, or between two parts of the same linked list if the source and destination lists are the same. If the copy is being done within a linked list, then it is performed in such a way that data never overwrites itself and then gets re-copied (in other words, the procedure works correctly and gives the expected result even when the source and destination ranges overlap). The two lists’ element sizes must match.
compareElements()
syntax: (Boolean) err_code/result = CompareElements((linkedlist *) source_LL, (numeric) first_source_index, (linkedlist *) dest_list, (numeric) first_dest_index, num_elements_to_compare)
Compares data between two linked lists, or between two parts of the same linked list. The return value is either an error code, or the Boolean result of the comparison.
fillElements()
syntax: [(numeric) err_code =] FillElements((linkedlist *) LL, (numeric) first_index, last_index, (char) byte_pattern)
Fills the given range of elements of a linked list with the byte pattern specified. That is, each byte of data storage used by those elements is set to the value of the byte given in the fourth argument.
clearElements()
syntax: [(numeric) err_code =] clearElements((linkedlist *) LL, (numeric) first_index, last_index)
Clears -- i.e. sets to zero -- the given range of elements of a linked list. This is equivalent to calling fillElements() with a byte pattern of 0.
setElements()
syntax: [(numeric) err_code =] setElements((linkedlist *) LL, (numeric) first_index, last_index, (void *) read_address)
Copies data from a buffer (the final argument) into a given range of elements in a linked list. The range includes the first and last elements. Whereas the linked list has fragmented memory, the buffer’s storage is expected to be contiguous, and the buffer address is a pointer to the beginning of the data to copy.
setElement()
syntax: [(numeric) err_code =] setElement((linkedlist *) LL, (numeric) index, (void *) read_address)
Copies data from a buffer into a single element of a linked list. This is equivalent to calling setElements() with the same first and last element.
getElements()
syntax: [(numeric) err_code =] getElements((linkedlist *) LL, (numeric) first_index, last_index, (void *) write_address)
Copies data from a range of elements of a linked list (including the first and last elements) into a buffer. The write address points to the start of the buffer.
getElement()
syntax: [(numeric) err_code =] getElement((linkedlist *) LL, (numeric) index, (void *) write_address)
Copies data from a single element of a linked list into a buffer. This is equivalent to calling getElements() with the same first and last element.
elementExists()
syntax: (numeric) err_code/if_exists = elementExists((linkedlist *) LL, (numeric) index)
Returns ccTrue or ccFalse depending on whether a given element of a linked list exists. An error code is thrown if the memory field of the linked list is NULL.
findElement()
syntax: (void *) element_pointer = findElement((linkedlist *) LL, (numeric) element_index)
Returns a pointer to the given element of a linked list, or NULL if the element doesn’t exist.
element()
syntax: (void *) element_pointer = element((linkedlist *) LL, (numeric) element_index)
Returns a pointer to the given element of a linked list. Identical to findElement() except that element() doesn’t do range checking: if the index is out of range then element() will simply crash the program.
skipElements()
syntax: (void *) element_pointer = skipElements((linkedlist *) LL, (sublistHeader *) sublist, (void *) starting_pointer, (ccInt *) sublist_index, (numeric) indices_to_skip)
Only for real pros. Starting from a pointer to an element in the linked list, this routine returns the pointer to another element a given number of indices farther down the list. When canvassing large, heavily-fragmented lists it may be slightly faster to go through the list once using skipElements() than to call element(), which searches from the first sublist each time it is called. The first three arguments are the linked list, a pointer to our current sublist and a pointer to the local index of our starting element (beginning at 0 for the first element in the sublist). The new element must have a higher index than the old; Cicada’s linked lists cannot be explored in reverse.
Last update: May 8, 2024