In AmigaOS, there exists a pervasive data structure which is used everywhere: a doubly-linked list that, optionally, can support insertion sort based on priority. Tripos also makes use of linked lists, albeit singly-linked. This was reasonable for the time: with the absence of caches, linked lists offer great flexibility without incurring significant performance hits. However, today, with caches everywhere and several levels deep, it turns out linked lists are surprisingly expensive. Simply copying arrays around turns out to be measurably faster.
In my interpretation of Tripos, I anticipate the possibility of supporting more sophisticated RISC-V processor technology. I do this by choosing to use vector-based approaches to managing data instead of relying on linked lists.
The root of the dynamic array is, well, the array itself. It has a certain number of elements total, called its capacity. The array length determines how many elements are actually in use.
+-----+-----+-----+-/ /-+-----+
| 0 | 1 | 2 | ... | n |
+-----+-----+-----+-/ /-+-----+
^ ^ ^
| | |
+-- (length) --' |
| |
+------- (capacity) ----------'
|
base
Each element in the array consists of some number of bytes, which is known as the element size.
Note: Unlike queues, dynamic arrays are capable of recording entire records of data, not just pointers to them.
+----------+ | a_base | +----------+ | a_length | +----------+ | a_cap | +----------+ | a_size | +----------+ | a_flags | +----------+
The a_base field records the base address of the array.
The AF_DYNAMIC flag (kept in a_flags) determines if the array is dynamically managed on the heap (set) or is statically allocated (cleared).
The AF_SELFMANAGE flag determines who manages the array memory: you (set) or the dynamic array library (clear).
These flags are the same flags as found in the queue library.
The a_length and a_cap determines the length and capacity of the array
in elements, not bytes.
Each element is a_size bytes in size.
Given an index, return the address of the element.
TO Get element address (ary, e) DO
IF 0 < e THEN
RETURN result for index out of range
END
IF e >= a_length DO
RETURN result for index out of range
END
Compute byte offset from base of element.
RETURN address of element.
END
TO set element (e) of array (ary) to (v) DO
Get element address (ary, e).
IF successful THEN
Copy bytes a_size bytes from v to address.
Assume result is successful.
END
RETURN results.
END
TO copy element (e) from array (ary) to (v) DO
IF v is illegal THEN
RETURN results for bad parameter.
END
Get element address (ary, e).
IF successful THEN
Copy bytes a_size bytes from address to v.
Assume result is successful.
END
RETURN results.
END
TO set array capacity THEN
IF array is self-managed THEN
RETURN results for self-managed array.
END
IF new capacity is smaller than the current capacity THEN
Set new capacity.
Limit array length IF length exceeds capacity.
RETURN success.
END
IF new capacity is equal to current capacity THEN
Limit array length IF length exceeds capacity.
RETURN success.
END
-- new capacity must be greater than current capacity
Determine new buffer size in bytes.
IF array is dynamically managed THEN
Determine current array's total allocation size.
IF new buffer size fits in current array's allocation THEN
Set new capacity.
Limit array length IF length exceeds capacity.
RETURN success.
END
END
Allocate a new array.
IF not successful THEN
RETURN results for out of memory.
END
Zero new array.
Copy current array into new array.
IF old array is dynamically managed THEN
Free old array.
END
Set new base address.
Note that array is now dynamically managed.
Record new capacity.
Limit array length IF length exceeds capacity.
RETURN success.
END
TO grow the array THEN
Double the current array capacity.
RETURN results from setting array capacity.
END
TO set array length THEN
IF new length fits in available capacity THEN
Set new length field.
RETURN success.
END
Set array capacity.
IF successful THEN
Set new length field.
END
RETURN results.
END
TO insert value (v) at position (i) DO
Make hole at position i.
IF successful THEN
Set element i to value v.
END
RETURN results.
END
TO add value v to head DO
RETURN results for Insert value v at position 0.
END
TO add value v to tail DO
RETURN results for Insert value v at position (length).
END
TO make a hole at position (i) DO
IF i is an invalid position THEN
RETURN results for invalid position.
END
IF capacity is large enough THEN
Let last represent the last element in the array.
Bump length of array.
Copy elements [i,last) to [i+1,last+1).
RETURN success.
ELSE
Grow the array.
IF successful THEN
Let last represent the last element in the array.
Bump length of array.
Copy elements [i,last) to [i+1,last+1).
RETURN success.
ELSE
RETURN results for out of memory.
END
END
END
Generally speaking, you'll get the best performance if you avoid removing elements from an array. Instead, I strongly recommend placing unused elements in a free-list. This avoids having to constantly scoot elements in the array back up.
TO collapse value at position (i) DO
IF i is an invalid position THEN
RETURN invalid position error
END
Let end represent the last element in the array.
Copy elements [i+1,end+1) to [i,end).
Decrement length of array.
RETURN success.
END