Engineering a List container Part 2: Implementations

[jacob navia]

Specifications
--------------

Add

int (*Add)(List *l,const void *data);
int (*Add)(TYPEList *l, TYPE data);

Description:
Adds the given element to the container. In its generic form it is
assumed that ”data” points to a contiguous memory area of at least
ElementSize bytes. Inits specialized form the data is passed by value.
Returns a value greater than zero if the addition of the element to the
list completed successfully, a negative error code otherwise.

Errors:
CONTAINER ERROR BADARG The list or the data pointers are NULL .
CONTAINER ERROR READONLY The list is read-only. No modifications allowed.
CONTAINER ERROR NOMEMORY Not enough memory to complete the operation.
Invariants: The input data is not modified.

Returns:
A positive number if the element was added or a negative error code
otherwise.

Example:
/* This example shows how to:
(1) Create a linked list of "double" data
(2) Fill it using the "Add" function
(3) Print it using the GetElement function */
#include <containers.h>
static void PrintList(List *AL)
{
size_t i;
for (i=0; i<iList.Size(AL);i++) {
printf("%g ",*(double *)iList.GetElement(AL,i));
}
printf("\n");
}
static void FillList(List * AL,size_t siz)
{
size_t i;
for (i=0; i<siz;i++) {
double d = i;
iList.Add(AL,&d);
}
}
int main(void)
{
List *AL = iList.Create(sizeof(double));
FillList(AL,10);
PrintList(AL);
return 0;
}
OUTPUT: 0123456789

------------------------------------------------------------------------------------
Implementation
--------------
Add

/* Add without error checking (nd for no debug) */
1 static int Add_nd(List *l,void *elem)
2 {
3 list_element *newl;
4 newl = new_link(l,elem,"iList.Add");
5 if (newl == 0)
6 return CONTAINER_ERROR_NOMEMORY;
7 if (l->count == 0) {
8 l->First = newl;
10 }
11 else {
12 l->Last->Next = newl;
13 }
14 l->Last = newl;
15 l->timestamp++;
16 ++l->count;
17 return
18 }
19
20 static int Add(List *l,void *elem)
21 {
22 int r;
23 if (l == NULL || elem == NULL) return NullPtrError("Add");
24 if (l->Flags &CONTAINER_READONLY) return ErrorReadOnly(l,"Add");
25 r = Add_nd(l,elem);
26 if (r && (l->Flags & CONTAINER_HAS_OBSERVER))
27 iObserver.Notify(l,CCL_ADD,elem,NULL);
28 return r;
29 }

This function adds one element at the end. The Add entry point performs
the error checking and calls Add_nd an internal function that does the
actual work. This is needed because other functions call internally Add
after they have already performed the error checking.

The Add_nd function requests a new list element (line 4). If that
succeeds the new element must be inserted in the list. If the list is
empty it just establishes the start of the list (8), if not, it adds it
after the last element (12). The new list element is the last one (14).

Errors leave the list unchanged. Exclusive access to the list is needed
between the line 8 and the line 16 in the code. This operation is a
modification of the list, and it needs to update the timestamp value to
notify possible iterators that they are invalid.

If the Add_nd function was successful and this container has a
registered observer we notify the observer of this event.

AddRange
1 static int AddRange(List * AL,size_t n, void *data)
2 {
3 unsigned char *p;
4 list_element *oldLast;
5
6 if (AL == NULL) return NullPtrError("AddRange");
7 if (AL->Flags & CONTAINER_READONLY) {
8 AL->RaiseError("iList.AddRange",CONTAINER_ERROR_READONLY);
9 return CONTAINER_ERROR_READONLY;
10 }
11 if (n == 0) return 0;
12 if (data == NULL) {
13 AL->RaiseError("iList.AddRange",CONTAINER_ERROR_BADARG);
14 return CONTAINER_ERROR_BADARG;
15 }
16 p = data;
17 oldLast = AL->Last; while(n>0){
18 int r = Add_nd(AL,p);
19 if (r < 0) {
20 AL->Last = oldLast;
21 if (AL->Last) {
22 list_element *removed = oldLast->Next;
23 while (removed) {
24 list_element *tmp = removed->Next;
25 if (AL->Heap)
26 iHeap.FreeObject(AL->Heap,removed);
27
28 else AL->Allocator->free(removed);
29 removed = tmp;
30 }
31 AL->Last->Next = NULL;
32 }
33 return r;
34 }
35 p += AL->ElementSize; /* Point to the next element */
36 n--; /* Count the items added so far */
37 }
38 AL->timestamp++;
39 if (AL->Flags & CONTAINER_HAS_OBSERVER)
40 iObserver.Notify(AL,CCL_ADDRANGE,data,(void *)n);
41 return 1;
42 }

This function calls repeatedly Add_nd for each element of the given
array. Any error provokes an abort and the original list is left
unchanged.

Error checking is done in lines 6 to 15, testing for NULL for the list
and the data. If the number of elements is zero the function does
nothing and returns zero. The code accepts data as NULL if the number of
elements is zero. If n is zero this code still checks that the list is
not NULL , and that the list is not read only, considering both to be
errors. Nothing is specified for those cases and you can’t rely on this
behavior for other implementations.

Note that at compile time we do not know the size of each element and we
can’t index into this array. We just setup a generic pointer to the
start of the data area (16), and increment it by the size of each
element at each iteration (line 35). This implementation supposes that
the size of the elements as assumed by the list is the same as the size
of the element as assumed by the calling program.

If an error occurs when adding elements the new elements are discarded,
the list is reset to its previous state and an error code is returned.
(lines 20-33). The eventually added elements are discarded (lines 24-30).

Notes:
It would be far more efficient to test at the start of the loop if there
is enough space for the n list elements than doing it within the loop.
That would eliminate the code for reclaiming the already allocated
items. This isn’t done because the list allocator could be the default
malloc function that doesn’t allow queries of this type.

 

[jacob navia]

Le 08/12/2013 01:08, jacob navia a écrit :

...
15 l->timestamp++;
16 ++l->count;
17 return
18 }
19

OOOPS bad copy and paste! that should have been
17 return 1;

 

[jacob navia]

Le 19/12/2013 08:01, Gareth Owen a écrit :

How would you implement the following in CCL?

void complex_function(const std::list<std::list<double> >&);

void make_list_of_lists(size_t siz)
{
using std::list;
list<list<double> > list_of_lists;

for(size_t z=0;z<siz;++z){
list<double> tmp;
FillList(tmp,z);
list_of_lists.push_back(tmp);
}
complex_function(list_of_lists);
}

Don't forget to include cleanup, and some method of propagating memory
exhaustion errors back to the caller.

1. You create a list of pointers to lists.

List *ListOfLists = iList.Create(sizeof(List *));
if (ListOfLists == NULL) {
goto NoMem;
}
// Use a heap to increase speed
iList.UseHeap(ListOfLists,NULL);

for (size_t z = 0; z<siz; ++z) {
List *doubleList = iList.Create(sizeof(double));
if (doubleList == NULL) goto NoMem;
FillList(doubleList,z);
int r = iList.Add(ListOfLists,doubleList);
if (r == CONTAINER_ERROR_NOMEMORY) {
NoMem:
// Do something about no memory errors
}
}
The "ListOfLists" list contains "siz" pointers to lists of 0 to siz-1
elements, following your specs. I do not see what the point of a list of
zero elements could be but anyway, I followed your model.


Cleanup:

Method 1: Iterate the list freeing the small lists of doubles

Iterator *it = iList.NewIterator(ListOfLists);
List *le;

for (le = it.GetFirst(it); le != NULL; le = it.GetNext(it)) {
iList.Finalize(le);
}

Method 2:
Setup a destructor for the list of lists

int FreeList(void *l)
{
iList.Finalize(l);
}

iList.SetDestructor(ListOfLists,FreeList);


Whenever a list element is destroyed, the function "FreeList" will be
called with the pointer to a list of doubles.

The second method is more efficient

Method 3:
An even MORE efficient method would be to force the list of lists AND
the sublists to use the same allocator. In that case you would avoid
iterating the lists at all and even destroying them. You just destroy
all memory used by the allocator.

You can do that by writing a custom allocator using any
external heap functions. Under windows, for instance, the run
time of windows provides heap allocators that you can use in your
custom allocators. I am sure you can find similar functions
under Linux or Mac.

Note that I did not use the type generic interface for the list of
doubles. For the elementary types (int, double) the ccl provides
specialized lists. I did not use it to show the general case.

 

[jacob navia]

Le 19/12/2013 08:01, Gareth Owen a écrit :

How would you implement the following in CCL?

void complex_function(const std::list<std::list<double> >&);

void make_list_of_lists(size_t siz)
{
using std::list;
list<list<double> > list_of_lists;

for(size_t z=0;z<siz;++z){
list<double> tmp;
FillList(tmp,z);
list_of_lists.push_back(tmp);
}
complex_function(list_of_lists);
}

Don't forget to include cleanup, and some method of propagating memory
exhaustion errors back to the caller.

I forgot!

Concerning the cleanup the BEST solution is a garbage collector of
course.

The lcc compiler provides (as a part of the standad distribution) a GC.

The Boehm GC runs in most machines and can be used with minimal setup.

With a GC, C has the same behavior as C++ concerning memory management.

 

[jacob navia]

Le 19/12/2013 18:26, Gareth Owen a écrit :

That leaks memory on success (and on failure until you fill in the
blanks). None of the lists is ever deallocated.

If you use a garbage collector the code above is ALL that needs to be
written

Cleanup:

Method 1: Iterate the list freeing the small lists of doubles

[snip]

Can we see the full function, including all the code please in one
function, so we can see how straightforward it is?
i.e. put your Cleanup code into the NoMem: label above.

You are used to C++. In C++ there is only ONE soution since the language
forces it into you if you wznt it or not.

In C there are several solutions, and you can CHOOSE which is the one
you prefer. I outlined some of them, with advantages and drawbacks.

Otherwise, how can we compare?

// Do something
followed by a rough outline is not correct error handling.

Well, what do you do in C++ when there is no more memory?
Since you did not outline any throw/catch code that handles the
exception for no memory I thought that the actual behavior
wasn't important. Your code did not show any error handling
of the no memory condition so if the situation arises you get
an uncaught exception error and your program exits.

I bet your error handling code alone will be three times longer than the
entire C++ code.

Wrong bet.

Using a GC the code is:
void make_list_of_lists(size_t siz)
{
List *ListOfLists = iList.Create(sizeof(List *));
if (ListOfLists == NULL) {
goto NoMem;
}
for (size_t z = 0; z<siz; ++z) {
List *doubleList = iList.Create(sizeof(double));
if (doubleList == NULL) goto NoMem;
FillList(doubleList,z);
int r = iList.Add(ListOfLists,doubleList);
if (r == CONTAINER_ERROR_NOMEMORY) {
NoMem:
exit(1);
}
}
}

Using manual cleanup:

void make_list_of_lists(size_t siz)
{
List *ListOfLists = iList.Create(sizeof(List *));
if (ListOfLists == NULL) {
goto NoMem;
}
iList.SetDestructor(ListOfLists,
(DestructorFunction)iList.Finalize);
for (size_t z = 0; z<siz; ++z) {
List *doubleList = iList.Create(sizeof(double));
if (doubleList == NULL) goto NoMem;
FillList(doubleList,z);
int r = iList.Add(ListOfLists,doubleList);
if (r == CONTAINER_ERROR_NOMEMORY) {
NoMem:
exit(1);
}
}
complex_function(ListOfLists);
iList.Finalize(ListOfLists);
}

As you can see, C is slightly longer than C++ but there isn't a
factor of three involved, just a few lines.

Note too that if FillList uses memory (and it would be surprising that
it doesn't) its return value should be tested for any errors.

jacob

 

[Martin Shobe]

Le 19/12/2013 18:26, Gareth Owen a écrit : [snip]

[snip]

Can we see the full function, including all the code please in one
function, so we can see how straightforward it is?
i.e. put your Cleanup code into the NoMem: label above.

You are used to C++. In C++ there is only ONE soution since the language
forces it into you if you wznt it or not.

In C there are several solutions, and you can CHOOSE which is the one
you prefer. I outlined some of them, with advantages and drawbacks.

I'm pretty sure that all the C solutions are available in C++ as well.

[snip]

Martin Shobe

 

[jacob navia]

Le 20/12/2013 01:49, Martin Shobe a écrit :

Le 19/12/2013 18:26, Gareth Owen a écrit : [snip]

[snip]

Can we see the full function, including all the code please in one
function, so we can see how straightforward it is?
i.e. put your Cleanup code into the NoMem: label above.

You are used to C++. In C++ there is only ONE soution since the language
forces it into you if you wznt it or not.

In C there are several solutions, and you can CHOOSE which is the one
you prefer. I outlined some of them, with advantages and drawbacks.

I'm pretty sure that all the C solutions are available in C++ as well.

[snip]

Martin Shobe

For reasons unknown, the STL hasn't implemented the observer interface.

Obviously the code of the CCL is probably compatible with
C++ unless you use C99 for flexible structures that C++ doesn't have.

 

[Malcolm McLean]

Only if you believe memory is the only resource that requires
reclamation.

A Turing machine consists of a rubber, a pencil, a contraption to erase, draw
and shift state, and an infinite tape.
The infinite tape can't really be provided. But memory is the only resource
you need for a computation. If you do IO, of course, you need other resources,
be each one has its own quirks. So you should separate IO from bit shuffling.

 

[Martin Shobe]

Le 20/12/2013 01:49, Martin Shobe a écrit :

Le 19/12/2013 18:26, Gareth Owen a écrit : [snip]
[snip]

Can we see the full function, including all the code please in one
function, so we can see how straightforward it is?
i.e. put your Cleanup code into the NoMem: label above.


You are used to C++. In C++ there is only ONE soution since the language
forces it into you if you wznt it or not.

In C there are several solutions, and you can CHOOSE which is the one
you prefer. I outlined some of them, with advantages and drawbacks.

I'm pretty sure that all the C solutions are available in C++ as well.

[snip]

Martin Shobe

For reasons unknown, the STL hasn't implemented the observer interface.

I suspect the reason is not enough demand. I certainly don't want it
very often, and it's not usually that difficult to wrap an STL container
with something that implement the observer interface when I do.

Obviously the code of the CCL is probably compatible with
C++ unless you use C99 for flexible structures that C++ doesn't have.

Is this a retraction of your claim that C++ forces one solution whether
we want it or not?

Martin Shobe

 

[jacob navia]

Le 20/12/2013 19:34, Martin Shobe a écrit :

Le 20/12/2013 01:49, Martin Shobe a écrit :

On 12/19/2013 3:12 PM, jacob navia wrote:
Le 19/12/2013 18:26, Gareth Owen a écrit :
[snip]
[snip]

Can we see the full function, including all the code please in one
function, so we can see how straightforward it is?
i.e. put your Cleanup code into the NoMem: label above.


You are used to C++. In C++ there is only ONE soution since the
language
forces it into you if you wznt it or not.

In C there are several solutions, and you can CHOOSE which is the one
you prefer. I outlined some of them, with advantages and drawbacks.

I'm pretty sure that all the C solutions are available in C++ as well.

[snip]

Martin Shobe

For reasons unknown, the STL hasn't implemented the observer interface.

I suspect the reason is not enough demand.

That is wrong. Other similar container libraries like Apple's Core
Foundation have that interface. It is described in that famous book

"Design Patterns" by Gamma, Helm, Johnson, and Vlissides

that is one of the foundations of object oriented programming, under
"Behavioral Patterns", together with the iterator pattern.

The applications are multiple and varied:

o Updating a user interface component when some list is changed

o Performing cleanup when some container disappears and you need
to get rid of obsolete pointers (This is a must really).

o etc!

I certainly don't want it
very often, and it's not usually that difficult to wrap an STL container
with something that implement the observer interface when I do.

No, it is. It took me several days of efforts to arrive at the
implementation of that interface and I could do it more easily since
I could (and did) modify the containers to emit the messages needed.

In C++ you can't modify the STL you use so easily, please let's get
serious.

Is this a retraction of your claim that C++ forces one solution whether
we want it or not?

????

Look, there is NO WAY to avoid destructors for instance, in C++. And
MANY other things. Of course that doesn't mean that C++ has
everything. It doesn't even have a garbage collector, or overflow
handling, and many other simple things.

It does have lambdas though

 

[Jorgen Grahn]

Le 20/12/2013 19:34, Martin Shobe a écrit :

That is wrong. Other similar container libraries like Apple's Core
Foundation have that interface. It is described in that famous book

"Design Patterns" by Gamma, Helm, Johnson, and Vlissides

Then that Apple library is not similar. The STL was designed to
provide (among other things, notably algorithms) the datatypes built
into other languages: lists, maps/hashes and so on. I don't think
e.g. a Perl array or a Haskell list comes with the observer pattern.

In that sense the STL is more low-level than what you want to do.

/Jorgen

 

[Ian Collins]

Only if you believe memory is the only resource that requires
reclamation.

That, along with garbage collection's lack of deterministic behavior
tends to a be a common mistake in this kind of argument. Another is
there are GC libraries that can be linked to both C and C++ code.

 

[James Kuyper]

Of course there is. Remember, you can use CCL in C++, and those objects
have no destructors.

Ridiculous claims like that are part of the reason why I have jacob
kill-filed, but as a result I've no idea how he responded. Jacob is
technically correct when he says you can't avoid destructors in C++. A C
struct translated to C++ will have no user-declared destructor, and
therefore "a destructor is implicitly declared as defaulted" (C++
12.4p4), which "is implicitly defined when it is odr-used" (12.4p6).

However, that implicitly defined destructor will be trivial (12.4p5),
and therefore has no tasks it actually needs to perform. This was a
feature deliberately designed into C++ from the very beginning for the
purpose of enabling compatibility with C code. It long predates the
invention of the term "trivial destructor" which is used by the current
standard to explain this feature. Any C++ compiler which implements a
trivial destructor by generating any actual code that takes time or
memory to execute is very poorly implemented. I'm curious - has jacob
given any response yet to acknowledge that point?

 

[jacob navia]

Le 23/12/2013 16:33, James Kuyper a écrit :

Ridiculous claims like that are part of the reason why I have jacob
kill-filed, but as a result I've no idea how he responded.

This pompous attitude of saying "I have this one kill filed" but somehow
participating in the threads I start...

Can someone help this poor guy?

I can't, of course.

 

[Ian Collins]

Ridiculous claims like that are part of the reason why I have jacob
kill-filed, but as a result I've no idea how he responded. Jacob is
technically correct when he says you can't avoid destructors in C++. A C
struct translated to C++ will have no user-declared destructor, and
therefore "a destructor is implicitly declared as defaulted" (C++
12.4p4), which "is implicitly defined when it is odr-used" (12.4p6).

However, that implicitly defined destructor will be trivial (12.4p5),
and therefore has no tasks it actually needs to perform. This was a
feature deliberately designed into C++ from the very beginning for the
purpose of enabling compatibility with C code. It long predates the
invention of the term "trivial destructor" which is used by the current
standard to explain this feature. Any C++ compiler which implements a
trivial destructor by generating any actual code that takes time or
memory to execute is very poorly implemented. I'm curious - has jacob
given any response yet to acknowledge that point?

He tends to ignore the parts of a post that contradict his claims.

 

[James Kuyper]

He tends to ignore the parts of a post that contradict his claims.

That's pretty much what I expected. However, I was curious - it's such
an elementary aspect of C++ that I hoped there was a possibility he
might acknowledge his mistake.

 

[Keith Thompson]

Ridiculous claims like that are part of the reason why I have jacob
kill-filed, but as a result I've no idea how he responded.

[...]

James, I suggest you look up his post if you're curious about it.
I have him killfiled myself; if I'm curious about something he's
written, I can still find and read what he's posted. How to do
this will vary depending on your newsreader, but usually killfiling
a poster merely means that his posts are automatically marked as
read, not deleted. (In my newsreader, there's a command to go to
the parent of the current article; it works as long as the parent
article can be found on the server.)

 

[James Kuyper]

On 12/23/2013 02:53 PM, Keith Thompson wrote:
....

James, I suggest you look up his post if you're curious about it.
I have him killfiled myself; if I'm curious about something he's
written, I can still find and read what he's posted. How to do
this will vary depending on your newsreader, but usually killfiling
a poster merely means that his posts are automatically marked as
read, not deleted.

I've got my message filters set up to delete the messages; not merely to
mark them unread. Sometimes, as in this case, I see responses to a
message that make me want to go back to the original, but that comes up
so rarely that I don't want to change that setting.

I could have gone to Google to see his messages, but it's been so
frustrating seeing so many people point out the same flaw in what he's
said, that I also wanted to express that frustration, and not merely
confirm that he's dealing with it precisely the way I've come to expect
of him.

 

[Noob]

I've got my message filters set up to delete the messages; not merely to
mark them unread. Sometimes, as in this case, I see responses to a
message that make me want to go back to the original, but that comes up
so rarely that I don't want to change that setting.

For the record, to "undelete" in Thunderbird, one way is to:

1) disable the relevant filter
2) close Thunderbird
3) delete comp.lang.c.msf from your profile

Then all headers will be downloaded again...

 

[Malcolm McLean]

James, I suggest you look up his post if you're curious about it.
I have him killfiled myself; if I'm curious about something he's
written, I can still find and read what he's posted.

Killfiling people who annoy you is often a good idea. But discussing the
contents of killfiles leads to upset, antagonism, and lowers the tone
of the newsgroup.
If you decide to peep at the post of a person you normally keep killfiled
and respond to it, very few people are likely to judge you negatively, it's
your business. But if you say you have someone killfiled whilst responding
t points made by the killfiled poster, then I for one take a pretty dim view
of it. I'm actually interested in the technical merits of Jacob's container
library, and I'd like the discussion to be kept to those technical merits
or technical objections.