[fpc-devel] TLinkedList

[Micha Nelissen]

Hi,

I've attached my promised linked list. It's become a doubly-linked list,
so that Delete can be called multiple times in a row without problems.
OTOH, it would not be hard to make a singly-linked list variant (anyone
who uses only a single Delete after linear Find only?). I think the
interface should speak for itself. Every list item is actually an array of
items.

There are some "knobs", ItemSize and ArraySize: they can only be set before
adding first item or after clearing the list.
1) ItemSize: the number of bytes taken per item, default: sizeof(ptrint).
2) ArraySize: the number of bytes allocated per linked list "array",
including 3 pointers: prev, next, last-in-list.

If one knows to be adding a lot of items, set larger ArraySize. Default is
14 pointers, so that 14 * 4 + 8 (heap mgr overhead) is exactly 64 bytes.

One can store records of arbitrary size, but remember to adjust ArraySize
as well, if storing big records. There is little error checking.

Add and FindItem assume you're using ItemSize at least 4, and
modify/compare those 4 bytes. (Hint: if storing records, start your record
with a PtrInt, and use FindItem to search on its first field).

Insert, FindData and property ItemPointer are the generic ItemSize
counterparts, they use Pointers to a block of data. Add uses Insert though,
and FindData uses CompareMem, so may be slower than FindItem although
equivalent if ItemSize = sizeof(PtrInt).

Find, Prior, Next, Last, FindData, FindItem return true if they have
positioned on a valid new item, in that case you may use the properties
Item and ItemPointer to retrieve the data in the item.

I've tested the implementation with the attached listtest.pas, which tests
some bits but not all possible combinations by far. So consider TLinkedList
beta quality for now.

Comments are welcome.

Micha
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linkedlist.tar.gz
Type: application/octet-stream
Size: 1787 bytes
Desc: not available
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20051223/ba9d2680/attachment.obj>