Path: utzoo!mnetor!uunet!lll-winken!lll-tis!mordor!lll-lcc!well!shf
From: shf@well.UUCP (Stuart H. Ferguson)
Newsgroups: comp.sys.amiga
Subject: IPC - Standard Message Blocks
Message-ID: <5699@well.UUCP>
Date: 14 Apr 88 23:59:15 GMT
Reply-To: shf@well.UUCP (Stuart H. Ferguson)
Organization: The Blue Planet
Lines: 83
Summary: "Entry" array vs. other methods


A Comparison of Different Standard Message Formats

There have been a variety of proposals for a standard message structure
which allows any number of blocks of data of any type.  The three I
compare are nested chunks, entry list, and linked list of chunks. Nested
chunks structure is basically a simple IFF file in memory.  Entry list
structure has an array of pointers to entries.  Linked chunk list is
just a plain old-fashioned linked list of chunks.  For the purpose of
comparing the efficiency and ease of use of the different techniques, I
write a function which takes a message and returns a pointer to the
entry or chunk of type "ctype."  I'm leaving out the type definitions
for brevity -- hopefully that won't render things completely
incomprehensible. 

Nested chunk list (or any other in-line memory structure):
---------------------------------------------------------

struct Chunk *FindChunk (mess,ctype)
	struct StdMsg *mess;
	long ctype;
{
	char *ptr;
	int i;

	ptr = (char*) mess->first_chunk;
	for (i=0; i<mess->number_of_chunks; i++) {
		if (((struct Chunk*)ptr)->ctype == ctype) return ptr;
		ptr += ((struct Chunk*)ptr)->chunk_size;
	}
	return NULL;
}

Entry list:
----------

struct Entry *FindEntry (mess,ctype)
	struct StdMsg *mess;
	long ctype;
{
	struct Entry *ptr;
	int i;

	for (i=0; i<mess->number_of_entries; i++) {
		ptr = mess->entry_array[i];
		if (ptr->ctype == ctype) return ptr;
	}
	return NULL;
}

Linked Chunk list:
-----------------

struct Chunk *FindChunk (mess,ctype)
	struct StdMsg *mess;
	long ctype;
{
	struct Chunk *ptr;

	for (ptr=mess->first_chunk; ptr; ptr=ptr->next_chunk)
		if (ptr->ctype == ctype) break;
	return ptr;
}


So - suprise! - the winner in minimum code complexity is the linked list
design.  This design also wins with regard to ease of changing the data
in a message.  Changing either of the other two involves allocating new
memory, copying old data to the new memory and de-allocating the old
memory.  With a linked list, adding or removing nodes is as simple as
swapping pointers.  It may not seem like a big deal, but de-allocating
memory can incur substantial overhead, since the system takes some time
to merge the freed memory back into the available memory lists to reduce
fragmentation. 

It's hard to beat good old-fashioned linked lists -- especially
Exec-style linked lists with no special cases for insertion and
deletion.  Linked lists: a fast, reliable, no-limits design.  Not just a
good idea -- a great idea! 

This message has been brought to you by the Linked List Avisory Board. 
-- 
		Stuart Ferguson		(shf@well.UUCP)
		Action by HAVOC		(shf@Solar.Stanford.EDU)