I recently had the opportunity to peruse C.B. Falconer's Hashlib code
(http://cbfalconer.home.att.net/download/hashlib.zip Thank you very
much) and decided subsequently to post my linked list handler for
comments from the sages. That code is at the bottom of this post (as
semi-C++.)

It is slightly different from standard lists in that it does not
allocate per link nor only use freelists. It preallocates a storage
buffer, doubling the size of each allocation as it exceeds each buffer.
The buffer space is treated as a stack, with the first unused item at
the top of the stack being treated as the head of a second list of free
items. If the head points to nothing, it will be given to the user, and
a new head established. If the user deletes items from his list, the
free list head is pointed at these items and subsequent to this the
first node after the head will be used for handing to the user when new
items are added until the head is again the only node in the free list.
This insures that the list will never allocate needlessly.

One question is whether such behavior actually would be desirable for
any application.

Thank you,
Chris Williams

List.h
------
#ifndef __LIST_H__
#define __LIST_H__

/* Copyright (C) 2005 by Chris Williams

I am not currently providing this code for any sort of use outside of
looking at and testing. My only intention at this point in time is to
garner feedback. It should be treated as being untested and
completely unfit for any use in any software.

I can be contacted at thesagerat@yahoo.co.jp if you have any questions
or comments. Once I feel that this code is both desirable and of
production level, it will be posted to my website at
http://www.aahz.com with a proper license. GPL perhaps?

*/

#include <limits.h>
#define UINT_BITS (sizeof(unsigned int) * CHAR_BIT)

class List {
private:
	struct holder {
		void* myItem;
		holder* prev;
		holder* next;
	};

	unsigned int allocateSize;	/* will be doubled after each allocation.
So even with an initial setting of 1, we will only ever be able to have
as many buffers as UINT_BITS before going past the amount of memory we
can access with an unsigned int */

	holder* firstHolder,* lastHolder,* currHolder;
	unsigned int holderCount;	/* total number in the List */

	holder* buffers[UINT_BITS];	/* can have as many buffers as we can have
bits in an unsigned it. The first will be allocateSize * sizeof(holder)
and each one after will be double the size of the previous
(allocateSize * sizeof(holder)) * ((2^n) - 1) */
	unsigned int bufferSize[UINT_BITS];		/* number of holders we can fit
in each buffer */
	unsigned int bufferTop;		/* how many slots have ever been used in the
newest buffer */
	unsigned int bufferCount;

	bool enumBegin;

public:
	List(unsigned int initialSize);	/* initial size will be the number of
items to allocate for, not the actual allocation size */
	~List();

	int addItem(void* item);

	void initEnumeration();
	void* getNextItem();
	int moreLeft();
	void deleteCurrent();

	unsigned int getLength();
};

#endif

List.cpp
--------
/* Copyright (C) 2005 by Chris Williams

I am not currently providing this code for any sort of use outside of
looking at and testing. My only intention at this point in time is to
garner feedback. It should be treated as being untested and
completely unfit for any use in any software.

I can be contacted at thesagerat@yahoo.co.jp if you have any questions
or comments. Once I feel that this code is both desirable and of
production level, it will be posted to my website at
http://www.aahz.com with a proper license. GPL perhaps?

*/

#include "List.h"

#include <stdlib.h>

List::List(unsigned int initialSize) :
	firstHolder((holder*)NULL),
	lastHolder((holder*)NULL),
	currHolder((holder*)NULL),
	holderCount(0),
	bufferCount(0),
	allocateSize(initialSize)
{
	buffers[0] = NULL;
	bufferSize[0] = 0;
	bufferTop = 0;
}

List::~List() {
	unsigned int L;

	for (L = 0; L < bufferCount; L++) {
		free(buffers[L]);
	}
}

int List::addItem(void* item) {
	if (buffers[0] == NULL) {	/* need to create first buffer */
		buffers[0] = (holder*)calloc(allocateSize, sizeof(holder));
		if (buffers[0] == NULL) return 0;

		bufferSize[0] = allocateSize;
		allocateSize <<= 1;	/* double allocate size for next time */
		++bufferCount;
	}

	holder* newHolder = &buffers[bufferCount - 1][bufferTop];

	if (newHolder->prev != NULL) {	/* has a record of a previously emptied
holder */
		holder* emptiedHolder = newHolder->prev;	/* grab it */

		if (emptiedHolder->prev != NULL) {	/* check to see if it has a link
to an even more previous item */
			newHolder->prev = emptiedHolder->prev;	/* point the top item to it
so that next time we will use it */
		}
		else {	/* no old emptied holders left. We should use the top slot
next time */
			newHolder->prev = NULL;
		}

		newHolder = emptiedHolder;	/* and use this one this time */
	}
	else {
		++bufferTop;	/* we have used the top item, so we will need to use the
next slot next time */

		if (bufferTop == bufferSize[bufferCount - 1]) {	/* No more slots left
in this one! */
			buffers[bufferCount] = (holder*)calloc(allocateSize,
sizeof(holder));

			bufferSize[bufferCount] = allocateSize;
			bufferTop = 0;
			allocateSize <<= 1;
			++bufferCount;
		}
	}

	newHolder->myItem = item;
	newHolder->next = NULL;

	if (holderCount == 0) {	/* only holder in existence */
		newHolder->prev = NULL;	/* there can be no previous one */
		firstHolder = newHolder;	/* set as the head of the list */
	}
	else {
		lastHolder->next = newHolder;
		newHolder->prev = lastHolder;
	}
	lastHolder = newHolder;

	++holderCount;

	return 1;
}

void List::initEnumeration() {
	currHolder = firstHolder;
	enumBegin = true;
}

int List::moreLeft() {
	if (currHolder == NULL || currHolder->next == NULL) return 0;

	return 1;
}

void* List::getNextItem() {
	if (enumBegin) {
		enumBegin = false;

		if (currHolder == NULL) return NULL;
	}
	else {
		if (currHolder != NULL) {
			currHolder = currHolder->next;

			if (currHolder == NULL) return NULL;	/* don't want to try accessing
currHolder->myItem if currHolder is null! */
		}
		else {
			return NULL;
		}
	}

	return currHolder->myItem;
}

void List::deleteCurrent() {
	holder* emptiedSlot = currHolder;

	if (currHolder->prev != NULL) {
		if (currHolder->next != NULL) {	/* is between two others */
			currHolder->prev->next = currHolder->next;	/* link them to each
other */
			currHolder->next->prev = currHolder->prev;

			currHolder = currHolder->prev;
		}
		else {	/* we are the last item in the list */
			lastHolder = currHolder->prev;
			currHolder = currHolder->prev;	/* move back */
			currHolder->next = NULL;		/* and set as end */
		}
	}
	else {
		if (currHolder->next != NULL) {	/* first item in the list */
			firstHolder = currHolder->next;
			currHolder = currHolder->next;
			enumBegin = true;	/* don't increment pointer to get to next item, we
are already at it! */
		}
		else {	//we were the only item in the list
			firstHolder = NULL;
			lastHolder = NULL;
			currHolder = NULL;
		}
	}

	emptiedSlot->next = NULL;	/* be clean */
	emptiedSlot->prev = buffers[bufferCount - 1][bufferTop].prev;	/*
record the previous emptied slot */
	buffers[bufferCount - 1][bufferTop].prev = emptiedSlot;	/* and set as
the newest emptied slot */

	--holderCount;
}

unsigned int List::getLength() {
	return holderCount;
}

Chris Williams wrote:
> 
> I recently had the opportunity to peruse C.B. Falconer's Hashlib
> code (http://cbfalconer.home.att.net/download/hashlib.zip Thank
> you very much) and decided subsequently to post my linked list
> handler for comments from the sages. That code is at the bottom
> of this post (as semi-C++.)
> 
> It is slightly different from standard lists in that it does not
> allocate per link nor only use freelists. It preallocates a
> storage buffer, doubling the size of each allocation as it
> exceeds each buffer. The buffer space is treated as a stack,
> with the first unused item at the top of the stack being treated
> as the head of a second list of free items. If the head points
> to nothing, it will be given to the user, and a new head
> established. If the user deletes items from his list, the free
> list head is pointed at these items and subsequent to this the
> first node after the head will be used for handing to the user
> when new items are added until the head is again the only node in
> the free list. This insures that the list will never allocate
> needlessly.
> 
> One question is whether such behavior actually would be desirable
> for any application.

The moment you try to allocate things from your internal buffer you
run into alignment problems.  The only reasonable way to maintain
your buffer is as an array of char (of some sex) in the first
place.  Now there is no portable way of ensuring proper alignment
for any entity you can saw off from that, unless that entity is
again a char (or char array).  In particular you can't assign space
for pointers, void * or otherwise.  No characteristic of an address
in that buffer can guarantee alignment, although in practice it
often will suffice.

That is why malloc and friends are system functions in the first
place.  They just can't be implemented in a completely portable
manner.  Use them.

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

CBFalconer wrote:
> The moment you try to allocate things from your internal buffer you
> run into alignment problems.  The only reasonable way to maintain
> your buffer is as an array of char (of some sex) in the first
> place.  Now there is no portable way of ensuring proper alignment
> for any entity you can saw off from that, unless that entity is
> again a char (or char array).  In particular you can't assign space
> for pointers, void * or otherwise.  No characteristic of an address
> in that buffer can guarantee alignment, although in practice it
> often will suffice.

This is beyond my level of understanding.
My only knowledge of alignment (at this point in time) is something
along the general lines that getting particularly sized items (for
instance, a four byte int) alligned on addresses that are a multiple of
their size are accessed faster. ...That's if I remember correctly, and
if that is the kind of alignment we are talking about here.
But from that I would think that the only penalty would be slowness?
(Or is that enough, for this particular topic?)

Is there a particular site I could be pointed to where this is
explained in more detail? Though I will research on my own as well.

Thank you,
Chris

Chris Williams <thesagerat@yahoo.co.jp> wrote:
> My only knowledge of alignment (at this point in time) is something
> along the general lines that getting particularly sized items (for
> instance, a four byte int) alligned on addresses that are a multiple of
> their size are accessed faster. ...That's if I remember correctly, and
> if that is the kind of alignment we are talking about here.
> But from that I would think that the only penalty would be slowness?

No, slowness is a penality you might incur on Intel processors. On
other architectures you will get a bus error and the program crashes.
Something simple as

char *x = malloc( 100 * sizeof *x );
int *i = ( int * ) ( x + 1 );
*i = 42;

will do it...
                                   Regards, Jens
-- 
  \   Jens Thoms Toerring  ___  Jens.Toerring@physik.fu-berlin.de
   \__________________________  http://www.toerring.de

Chris Williams wrote:
> CBFalconer wrote:
> 
>> The moment you try to allocate things from your internal buffer you
>> run into alignment problems.  The only reasonable way to maintain
>> your buffer is as an array of char (of some sex) in the first
>> place.  Now there is no portable way of ensuring proper alignment
>> for any entity you can saw off from that, unless that entity is
>> again a char (or char array).  In particular you can't assign space
>> for pointers, void * or otherwise.  No characteristic of an address
>> in that buffer can guarantee alignment, although in practice it
>> often will suffice.
> 
> This is beyond my level of understanding.
> My only knowledge of alignment (at this point in time) is something
> along the general lines that getting particularly sized items (for
> instance, a four byte int) alligned on addresses that are a multiple of
> their size are accessed faster. ...That's if I remember correctly, and
> if that is the kind of alignment we are talking about here.
> But from that I would think that the only penalty would be slowness?
> (Or is that enough, for this particular topic?)

Not only slowness, but your system may abort.  It depends on the
hardware.  With virtual memory systems the actual physical address
can be anything, so a virtual address value carries no alignment
information (at least in a portable manner).

> 
> Is there a particular site I could be pointed to where this is
> explained in more detail? Though I will research on my own as well.

I don't know of any offhand.  I expect there are.

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

Chris Williams wrote:
> CBFalconer wrote:
> 
>>The moment you try to allocate things from your internal buffer you
>>run into alignment problems.  The only reasonable way to maintain
>>your buffer is as an array of char (of some sex) in the first
>>place.  Now there is no portable way of ensuring proper alignment
>>for any entity you can saw off from that, unless that entity is
>>again a char (or char array).  In particular you can't assign space
>>for pointers, void * or otherwise.  No characteristic of an address
>>in that buffer can guarantee alignment, although in practice it
>>often will suffice.
> 
> 
> This is beyond my level of understanding.
> My only knowledge of alignment (at this point in time) is something
> along the general lines that getting particularly sized items (for
> instance, a four byte int) alligned on addresses that are a multiple of
> their size are accessed faster. ...That's if I remember correctly, and
> if that is the kind of alignment we are talking about here.
> But from that I would think that the only penalty would be slowness?
> (Or is that enough, for this particular topic?)
> 
> Is there a particular site I could be pointed to where this is
> explained in more detail? Though I will research on my own as well.
> 
> Thank you,
> Chris
> 

You can find custom memory allocation examples in 
http://users.bestweb.net/~ctips

I don't know if it'll answer your questions regarding alignment, though.

Jens.Toerring@physik.fu-berlin.de wrote:
> Chris Williams <thesagerat@yahoo.co.jp> wrote:
> > My only knowledge of alignment (at this point in time) is something
> > along the general lines that getting particularly sized items (for
> > instance, a four byte int) alligned on addresses that are a
multiple of
> > their size are accessed faster. ...That's if I remember correctly,
and
> > if that is the kind of alignment we are talking about here.
> > But from that I would think that the only penalty would be
slowness?
>
> No, slowness is a penality you might incur on Intel processors. On
> other architectures you will get a bus error and the program crashes.
> Something simple as
>
> char *x = malloc( 100 * sizeof *x );
> int *i = ( int * ) ( x + 1 );
> *i = 42;

Thinking over the various wonkiness' I can envision with embedded
hardware (and possibly mainframes?) that seems reasonable--if not
desirable.

* thinks of things he has done in times previous like:

int i;
float f = -1.5f;

i = *((int*)&f); //w00t!

and shudders *

-Chris

CTips wrote:
> You can find custom memory allocation examples in
> http://users.bestweb.net/~ctips
>
> I don't know if it'll answer your questions regarding alignment,
though.

OT to this thread, but a question about Tip #16:

/* this belongs in some project-wide common header */
#if( NVERIFY )
  #define verify(_file, _line, _e)	((void)0)
#else
  #define verify(_file, _line, _e) \
	((_e)?	(void)0: \
		( fprintf(stderr, "%s %d: verify failure: %s", \
			_file, _line, #_e), \
		  abort()))
#endif

[snip]

void
verify_int_stack(
	FILE *		file,
	int		line,
	const int_stack	stack
	)
{
  verify( file, line, len_int_stack(stack) >= 0 );
  verify( file, line, len_int_stack(stack) <= max_int_stack(stack) );
  verify( file, line, max_int_stack(stack) >= 16 );
  verify( file, line, ((max_int_stack(stack) - 16)%16) == 0 );
}

Is this correct? You appear to be printing a FILE* with %s in fprintf?
My copy of stdio.h, at least, is showing FILE as a sort of struct with
various random data.

-Chris

Chris Williams wrote:
> CTips wrote:
> 
>>You can find custom memory allocation examples in
>>http://users.bestweb.net/~ctips
>>
>>I don't know if it'll answer your questions regarding alignment,
> 
> though.
> 
> OT to this thread, but a question about Tip #16:
> 
> /* this belongs in some project-wide common header */
> #if( NVERIFY )
>   #define verify(_file, _line, _e)	((void)0)
> #else
>   #define verify(_file, _line, _e) \
> 	((_e)?	(void)0: \
> 		( fprintf(stderr, "%s %d: verify failure: %s", \
> 			_file, _line, #_e), \
> 		  abort()))
> #endif
> 
> [snip]
> 
> void
> verify_int_stack(
> 	FILE *		file,
> 	int		line,
> 	const int_stack	stack
> 	)
> {
>   verify( file, line, len_int_stack(stack) >= 0 );
>   verify( file, line, len_int_stack(stack) <= max_int_stack(stack) );
>   verify( file, line, max_int_stack(stack) >= 16 );
>   verify( file, line, ((max_int_stack(stack) - 16)%16) == 0 );
> }
> 
> Is this correct? You appear to be printing a FILE* with %s in fprintf?
> My copy of stdio.h, at least, is showing FILE as a sort of struct with
> various random data.
> 
> -Chris
> 

Yup; it should have been char *, not FILE *. BUG!!!

:)