| For handling linked lists, the following operations are quite useful.
I discovered them in some technical paper, and they help considerably.
ptr0 <- slide (ptr1, ptr2, ..., ptrn)
Evaluate the locations of all the pointers. Set temp <- ptr1,
ptr1 <- ptr2, ..., ptr(n-1) <- ptrn, ptr0 <- temp.
rotate (ptr1, ptr2, ..., ptrn)
Evaluate the locations of all the pointers. Set temp <- ptr1,
ptr1 <- ptr2, ..., ptr(n-1) <- ptrn, ptrn <- temp.
The reason these primitives tend to be so useful is because they
help keep the number of pointers to objects invariant.
For example, (in Pascal-like notation) when you allocate a new object,
and want to insert it on a list, you can use:
ptr0 := 0;
new (ptr0); { create a new object }
ptr0 := slide (ptr0.next, root, ptr0);
Here, I wrote it as a slide, rather than a rotate, to simplify the
explanation of the thought processes behind this. We don't want ptr0
to hold the pointer to the new object -- something *else* is supposed
to point to it. So we want ptr0 to become nil, and the only available
nil is in ptr0.next, and we have:
ptr0 := slide (ptr0.next,
We want ptr0.next to contain the current value of the root. Indeed,
root is the only other pointer of interest now. So we have:
ptr0 := slide (ptr0.next, root,
And we want the root to point to the newly created object:
ptr0 := slide (ptr0.next, root, ptr0,
We've formed a cycle, enough's enough:
ptr0 := slide (ptr0.next, root, ptr0);
Frequently, you may *want* to keep a pointer to the newly created
object (for a little while). For example, you may want to link
the object into several lists. To maintain the invariance (of
one pointer to each object) realize that ptr0 is a local variable,
so that the extra pointer to the new object is effectively destroyed
when the routine returns.
For a doubly-linked list, you'd want to consider separate invariance
amoung the llink and rlink fields. You would have:
new (ptr0); { create a new object }
temp := root.llink;
slide (ptr0.rlink, temp.rlink, ptr0); { return value (nil) discarded }
slide (ptr0.llink, root.llink, ptr0);
{ temp and ptr0 destroyed on return from the procedure }
|
| For working with VMS system service/run-time-library stuff
in VAX C, I've found the following structures invaluable:
struct dsc_descriptor_dll /* Doubly linked list. */
{
unsigned short dsc$w_length;
unsigned char dsc$b_dtype;
unsigned char dsc$b_class;
char *dsc$a_pointer;
struct dsc_descriptor_dll *dsc_blink;
struct dsc_descriptor_dll *dsc_flink;
};
struct dsc_descriptor_sll /* Singly linked list. */
{
unsigned short dsc$w_length;
unsigned char dsc$b_dtype;
unsigned char dsc$b_class;
char *dsc$a_pointer;
struct dsc_descriptor_sll *dsc_flink;
};
The first two longwords of these structures are your usual
string descriptors, so these structures can be used as descrip-
tors in calls to functions that use descriptors. The dsc_blink
and dsc_flink long words are, or course, backward and forward
links.
It's really rather simple, but extremely useful.
<_Jym_>
|
| I'll vouch for Jym's comments. I've also 'extended' string descriptors
to include a 'dsc_l_next' field, and it's been extremely valuable.
Also, when dealing with singly-linked lists in Bliss, the following
construct is useful:
own
root: ref struct_block initial(0); ! Root of the linked list
local
ptr: ref struct_block;
ptr = root - %fieldexpand(struct_l_next,0);
while (ptr = .ptr[struct_l_next]) neq 0 do
begin
...
end;
This sets ptr to the *address* of root, less the offset to the 'next' field,
so that the first fetch grabs the value in root. The value of this is that
the loop control is all on one side of the loop, whereas the alternative:
ptr = .root; ! Actually, I'd use root[base_]
while .ptr neq 0 do ! ... and ptr[base_]
begin
...
ptr = .ptr[struct_l_next];
end;
puts the loop control on *both* sides of the loop, and it's too easy to
omit the assignment at the end of the loop.
|