Internally, nearly all of Yazoo's data memory is stored in resizable data structures called linked lists. This would be of little consequence to the user, except that call() passes strings as linked lists rather than, say, null-terminated byte arrays. The lazy reason for doing this is that each string is already stored in a linked list within Yazoo, so just passing the list saves Yazoo a conversion step. The better reason is that this method allows the user's own C code to share dynamic memory with Yazoo.
Each linked list consists of a header and a number of sublists. The header contains global information about the linked list but stores no data, so its size is fixed. Data is stored in the sublists. Each sublist begins with a header and is followed by an array of data storage, and in general each sublist holds a different number of elements. The C definitions of the relevant data types (taken from lnklst.h) are reproduced below.
typedef struct {
unsigned long elementnum;
sublistHeader *memory;
unsigned short elementsize;
unsigned char spare_room;
} linkedlist;
typedef struct sH_temp {
unsigned long num_elements;
struct sH_temp *next_sublist;
unsigned long max_elements;
} sublistHeader;
The most important fields are elementnum and elementsize in the linkedlist data type, which are, respectively, the number of elements in the array (characters) and the size of each element (for strings, this must be 1). If the list is initialized then the memory field points to the first sublist; otherwise this pointer should be zero.
Each linkedlist variable contains important fields that are updated by the LL routines. Therefore it is critical that linked lists always be passed by reference to any C routine that could conceivably modify that list. Otherwise the original copy of the linked list variable will have out-of-date information on the size of and pointer to the list, which will probably cause a crash somewhere downstream.
To speed up the insertion of new elements, many of the linked lists in Yazoo allocate extra space in the sublists that they create. The spare_room field gives the amount of extra space to allocate, as a percent of what is requested. Thus if this field is set to 100 then each time a new sublist is created it will have double the space that is needed at the time. The maximum amount of spare room is 255.
The user really never needs to worry about the sublist data structure. Each sublist contains both the number of elements currently stored, and the maximum number that can be stored, in that sublist. Resizing an array often involves adding elements only to one sublist. The next_sublist pointer is to the header of the next sublist in the chain; if the current sublist is the last then this field is zero.
It is of course recommended that the user manipulate the linked lists using Yazoo's own LL routines. This is partly to avoid mangling Yazoo's strings, which would probably crash the program down the road; also, it should save the user a good deal of effort. Most linked list routines come in two flavors: a regular version and an `F' version. `F' stands for fast -- the so-called fast routines just omit type-checking and some error-flagging. The error codes that many of these routines return will be explained in a later dedicated section on errors.
NewLinkedList(), FNewLinkedList()
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. Yazoo always sets if_cleared when allocating primitive data storage.
DeleteLinkedList(), FDeleteLinkedList()
syntax: [(numeric) err_code =] DeleteLinkedList((linkedlist *) LL)
De-allocates the storage of a new 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. The fast version of this routine does not return an error value; the slow version at present always returns `passed' (an error code of zero).
InsertElements(), FInsertElements()
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 is given by the third argument. The fourth argument, if set, zeros the new memory. Yazoo always sets the clear flag when new indices are added to primitive arrays, so they are always initialized to zero.
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 spare_room field of the linked list variable.
AddElements(), FAddElements()
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(), FDeleteElements()
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.
DefragmentLinkedList(), FDefragmentLinkedList()
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 access in a de-fragmented form, and it saves memory too because zero extra storage is allocated in the defragmented sublist, regardless of the value of spare_room in the linked list variable.
The call() function defragments all of its string-arguments before executing a user-defined C or C++ routine.
CopyElements(), FCopyElements()
syntax: [(numeric) err_code =] CopyElements((linkedlist *) source_LL, (numeric) first_source_index, (linkedlist *) dest_list, (numeric) first_dest_index, elements_to_copy)
Copies the elements 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 in 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). For obvious reasons the two lists' element sizes must match. The fast FCopyElements() does not have a return value.
CompareElements(), FCompareElements()
syntax: (numeric) err_code/result = CompareElements((linkedlist *) source_LL, (numeric) first_source_index, (linkedlist *) dest_list, (numeric) first_dest_index, elements_to_compare)
Compares the elements between two linked lists, or between two parts of the same linked list. The return value is either an error code (1-5), or the result of the comparison. If the two lists are equal these routines return 100 (`equal', defined in lnklst.h); otherwise they return 101 (`notequal').
FillElements(), FFillElements()
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. The fast FFillElements() does not return a value.
ClearElements(), FClearElements()
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. FClearElements() does not return a value.
SetElements(), FSetElements()
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 given address is a pointer to the first element of data to copy. FSetElements() does not return a value.
SetElement(), FSetElement()
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. FSetElement() does not return a value.
GetElements(), FGetElements()
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 given address points to the start of the buffer. FGetElements() does not return a value.
GetElement(), FGetElement()
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. The fast FGetElement() does not return a value.
ElementExists(), FElementExists()
syntax: (numeric) err_code = ElementExists((linkedlist *) LL, (numeric) index)
Tests to see whether a given element of a linked list exists. If the element is zero or greater than the maximum number currently in the list, it returns false (0). Otherwise it returns true, which is numerically 1 and hence unfortunately overlaps with the memory-allocation error code. However, since this routine cannot throw this particular error, a return value of 1 from ElementExists() always means `yes', as in, yes the element does exist.
Element(), FElement()
syntax: (void *) element_pointer = Element((linkedlist *) LL, (numeric) element_index)
Returns a pointer to the given element of a linked list. Both versions of this function return the same thing; however, if the element doesn't exist Element() will politely return a zero whereas FElement() will simply crash the program.
FSkipElements()
syntax: (void *) element_pointer = FSkipElements((void *) starting_pointer, (numeric) starting_index, indices_to_skip)
Starting from a pointer to an element in the linked list (whose index must be specified), 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 FSkipElements() than to call FElement(), which searches from the first sublist each time it is called. The new element must have a higher index than the old; Yazoo's linked lists cannot be explored in reverse. There is no `slow' version of this routine.
Last update: July 28, 2013