ThinkC Creating dynamic lists in ThinkC

[eric]

Say, i have a list of things like a struct that has a name and a size field. I want the user to add (or remove) any number of these items in a List control.

The basic way I've been doing this is with two 2d array char names[20][20], int size[20]; which has obvious problems, allocates memory for 20 items even if there's 0, and can only have 20 items.

I'm assuming it's something with linked lists - which I remember doing in a data structures class in college... many years ago.

Any pointers on a library, examples, or good tutorial on how I could go about this would be appreciated!

Thanks,

 

[Eric's Edge]

I’m sure I can find a reference. I remember doing this in college and at work for a “database” I created for a program - back before we had relational databases for DOS programming. You essentially allocate memory for each structure. You add a couple of pointers to your structure, one for the next “node” and one for the previous to create a double linked list. The first node has a null value in “prev” and the last has null in “next”. You create functions for manipulating the list.

 

[Eric's Edge]

I’m sure I can find a reference. I remember doing this in college and at work for a “database” I created for a program - back before we had relational databases for DOS programming. You essentially allocate memory for each structure. You add a couple of pointers to your structure, one for the next “node” and one for the previous to create a double linked list. The first node has a null value in “prev” and the last has null in “next”. You create functions for manipulating the list.

I’m camping this weekend. When I get back I’ll see what I can find. I’m sure there are many data structures and algorithms in C texts out there.

 

[YMK]

Dynamically allocating items that small is inefficient in a different way.

A good middle ground is dynamically allocating blocks of static elements. For example, allocate a block of names[20][20], then when you need your twenty-first element, allocate and link another block, and again when you need your forty-first element.

Also, if you have multiple attributes, like name and size, that belong to the same entity, consider using a struct.

 

[Crutch]

Agree with YMK, but just for fun/hobby purposes, if the number of it items will be reasonably small, a linked list of structs is probably your answer. Something like this.

typedef struct Foo {
char name[20];
int size;
struct Foo *next;
} Foo;

…

Foo *GetNewFoo(char *name, int size)
// returns a new Foo to add to the end of the list
{
Foo *newFoo = NewPtr((sizeof) Foo);
BlockMove(name, newFoo.name, name[0]); // assumes name is a valid Pascal string <= 19 chars long
newFoo.size = size;
newFoo.next = NULL;
return newFoo;
}

…

Foo *firstFoo = GetNewFoo(…..); // first item in list

 

[eric]

Thanks for both the pointers.

When you say dynamically allocate chunks how would you go about that? I'm not sure how to resize an array like that.

One complicating factor I forgot to mention is I'd need a way to get an element by index. I suppose I could loop and count.

Interesting problem to solve and lots of ways to go about it. I'll try to put together a small example app showing both recommendations so I can understand them.

 

[YMK]

Macintosh_C_Programming_By_Example_1991.pdf, pg 105:

You allocate the free blocks to your application using the Memory Manager function
NewPtr or NewHandle. Either function accepts a parameter that specifies the size, in
. bytes, of the block you need. When your application is finished with the block, you
call either DisposPtr or DisposHandle to free the block. (Apple left the "e" off
"dispose," by the way-that's not a typo.) Using either DisposPtr or DisposHandle
returns the block of memory in RAM to the free pool.

If you need indexed addressing and flat access times, keep your block pointers in an array rather than a linked list.

Yes, this will put an upper bound on the size of the list, but allowing for more memory than you'll ever need this way is cheap.

Also, make your elements per block a power of two.

 

[Crutch]

Yeah we are well into sophomore year computer science stuff here but …

You can’t really resize an array. But you could:

1. Allocate a “probably big enough but not too big” array, then if you need more space, reallocate a new, somewhat bigger array, copy everything over, then dispose of the old array. This makes things fast most of the time, with occasional slower processing when you breach a size limit.
2. Or - You could preallocate say 20 linked list elements in a contiguous block of memory, pointing to each other. When you add an item to the list, check if you have used all of your preallocated block. If so, instead of calling NewPtr/Handle to create the next list element, just construct a pointer to the next unused slot in the block …. If not, allocate a new block and point to the first element in the new block. This preserves linked list semantics for walking down the list, while reducing memory fragmentation from allocating list elements all over the place. However I don’t really recommend bothering with this unless you really need to worry about memory consumption (e.g. you want to run on a 128k Mac, or you might really have a ton of elements in your list).

When your application is finished with the block, you
call either DisposPtr or DisposHandle to free the block. (Apple left the "e" off
"dispose," by the way-that's not a typo.)

By the THINK C 6 era, it’s OK to spell DisposeHandle/DisposePtr with an ‘e’. (The ‘e’ was originally left off because Lisa Pascal only recognized the first 7 characters of an identifier, thus we have DisposP(tr), DisposH(andle), DisposD(ialog) etc …. THINK C and MPW didn’t have this limitation so introduced fully-spelled-out synonym macros.)