Need help with initializing items in linked list in a new way

[andyT]

Hello, I'm trying to find some help with code that I've been maintaining and currently trying to modify.

Basically, I am working with a single array of length "m", call it the "max" array. Other than knowing that each entry in the "max" array is nonnegative, I have no other information on this array until runtime (including the length "m"). I want to create a linked list of structs, with each struct containing two integer values, lbval and ubval.

struct item {
  int lbval;
  int ubval;
};

Each list item is a struct, corresponds to each array beneath (more precisely, lexicographically smaller than) the "max" array (up until the origin of 0 in all entries). So, for example, if m = 3, and the max array is [9 9 9], then I need (9+1)*(9+1)*(9+1) = 1000 structs in my linked list.

So, my first function CreateList attempts to create this linked list. It takes in the address of an item** (originally set to NULL). It then calls itself recursively until recurseLevel is one less than "m" (the length of the array). It then allocates space for items on the list. In a nutshell, the function starts with [0 ... ], goes to [0 0 ... ], etc., and eventually drills down to [0 0 0 x], where it initializes all arrays [0 0 0 0], [0 0 0 1], [0 0 0 2], etc. It then proceeds to [0 1 ... ], and so on...

void CreateList(int arrayLength, int recurseLevel, int* maxArray, item ***current)
{
	int i;
	int size = (int) maxArray[recurseLevel] + 1;
  
	if (recurseLevel == arrayLength - 1)
    {
		*current = (item **) malloc (size * sizeof(item *));  
		for (i = 0; i < size; i++)
		{
			(*current)[i] = (item* ) malloc (sizeof(item));
			(*current)[i]->lbval = 0;
			(*current)[i]->ubval = 1000;
		}
	}
	else
    {
		*current = (item **) malloc(size * sizeof(item *));
		for (i = 0; i < size; i++)
		{
			CreateRhs(arrayLength, recurseLevel + 1, maxArray, (item ***) (*current + i));
		}
	}
}

The function FindItem is used to access items on the list, returning a pointer to that item.

item* FindItem(int arrayLength, int *target, item **itemList)
{
	int i;
	item **current;
	item *tempPtr;

	current = itemList;

	for (int i = 0; i < arrayLength - 1; i++)
	{
		current = (item**) current[target[i]];
	}
	*tempPtr = (item*) current[target[i]];

	return(*tempPtr);
}

So, this approach allocates a LOT of memory if the size "m", as well as the entry values, are large, and this allocation is accomplished during the list's initialization. So instead of allocating all of the memory up front for every array in CreateList, I would like to just create the skeleton of the list -- meaning that in the last step of each recursion, I want to do:

(*current)[i] = NULL;

instead of allocating and setting the lbval and ubval values there. Then, when FindItem is called later in my code to look up an item, I would like to add a test to see if "tempPtr == NULL", and if so, to initialize that item there, something like:

if (tempPtr == NULL)
{
  tempPtr = (item* ) malloc (sizeof(item));
  tempPtr->lbval = 0;
  tempPtr->ubval = 1000;
}

My question is, would the above changes work - or am I off somewhere? I've tried to implement this idea, and though the logic seems correct to me, It's not running correctly (in particular, though a particular item will be initialized in FindItem, later it will again point to NULL (so it seems that the initialization was only done locally?).

Just not sure why it's happening - maybe someone more experienced can lend a hand here! Also, if there is a better way to do what I'm doing, or I can explain anything furher, please let me know.

Thanks for reading, and for your help!

[Murtan]

At least part of the problem is in your last set of code...

The tempptr was null, so you allocated and initialized it, but tempptr was just a copy of the pointer from current[target[i]] you made no effort to set the original array entry to the newly allocated item.

Also (I'm actually presuming this is a copy/paste error) the call to the function to recurse calls a function of a different name. (In the function CreateList , it calls CreateRhs )

I can think of other ways to write CreateList, but what you have appears to work. Given a preference, I would have written CreateList something like:

item ** CreateList(int arrayLength, int * maxArray)
{
    int ii;
    int mymax;
    item ** rval;

    if (arrayLength < 1)
        return null;
    mymax = maxArray[0] + 1;
    rval = (item **)malloc( mymax * sizeof(item *));
    for (ii = 0; ii < mymax; ii++)
    {
        rval[ii] = (item *)CreateList(arrayLength - 1, maxArray + 1);
    }
    return rval;
}

This makes an extra recursion to initialze the item pointers to null, but it made the code slightly easier to read. (Feel free to add a test and eliminate the last recursion level.)

I also didn't like doing the cast in rval[ii] = (item *)CreateList but the return type was not compatible with the array type. In order to do that assignment without the cast, we would need to create a union type for the list pointer. The union would either point to another instance of the union or to an item.

[andyT]

Murtan,

Your suggestion to initialize the original array entry (and not just the copy) did the trick. Thanks a ton, it's hard to describe how much this has been weighing on me lately. I thought that initializing the copy was the same as initializing the original, but now I understand it's not so.

Again, I really appreciate you taking the time to lend a hand here - I hope it comes back to you really soon!

At least part of the problem is in your last set of code...

The tempptr was null, so you allocated and initialized it, but tempptr was just a copy of the pointer from current[target[i]] you made no effort to set the original array entry to the newly allocated item.

Also (I'm actually presuming this is a copy/paste error) the call to the function to recurse calls a function of a different name. (In the function CreateList , it calls CreateRhs )

I can think of other ways to write CreateList, but what you have appears to work. Given a preference, I would have written CreateList something like:

item ** CreateList(int arrayLength, int * maxArray)
{
    int ii;
    int mymax;
    item ** rval;

    if (arrayLength < 1)
        return null;
    mymax = maxArray[0] + 1;
    rval = (item **)malloc( mymax * sizeof(item *));
    for (ii = 0; ii < mymax; ii++)
    {
        rval[ii] = (item *)CreateList(arrayLength - 1, maxArray + 1);
    }
    return rval;
}

This makes an extra recursion to initialze the item pointers to null, but it made the code slightly easier to read. (Feel free to add a test and eliminate the last recursion level.)

I also didn't like doing the cast in rval[ii] = (item *)CreateList but the return type was not compatible with the array type. In order to do that assignment without the cast, we would need to create a union type for the list pointer. The union would either point to another instance of the union or to an item.