Function Returning Array Of Pointers Concept

Discuss programming topics for any language, any source base. If it is programming related but doesn't fit in one of the below categories, it goes here.
Post Reply
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Function Returning Array Of Pointers Concept

Post by Baker »

I have a rough concept of being able to return a variable length array of pointers (allocated by calloc) with the data (also allocated by calloc) where the pointer list ends with NULL.

So a <do .. while> could traverse the data and stop when it hits null, just like a string.

But I'm not 100% on how to dealloc the array of data (yet), dealloc on the array of pointers (+1 with last member) = NULL seems easy enough.

I guess maybe I could calloc each member of the array of data and use the pointer array to pass the right memory address to free. Then write a function to possible conveniently wrap this using type (void *) and passing size_t. Then possibly wrapping the entire calloc bit into a similar type void function to easy the actual return of data.

This seems obvious enough that I feel it has been done before. This is just a morph of the concept of returning a malloc allocated null-terminated string.

The reason I want to do this is to be able to possibly return a set of matching points for geometry functions, where the number of points (vertices) maybe be anything from 0 matches to N matches.

(Will have to write and test this, but I'm rather sure I can make this work. I do not like the idea I cannot return an array of unknown size in C.)

/End rant ...
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
DolphinsOfCydonia
Posts: 21
Joined: Tue Nov 08, 2011 4:01 am

Re: Function Returning Array Of Pointers Concept

Post by DolphinsOfCydonia »

Why not a linked list? Traversal time is going to be the same O(n), unless you already know the size of the array at access time.
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

That would require a struct. And you'd still have to make the final match unlinked. Still you could dynamically allocate each return result on the fly. I don't know. I would prefer a pure data type, but maybe that isn't the best way.
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Re: Function Returning Array Of Pointers Concept

Post by mh »

Code: Select all

void DoStuffWithStuff (void)
{
    stuff_t **stuffptrs = NULL;
    int hunkmark = Hunk_LowMark ();

    // this function uses Hunk_Alloc to allocate it's array
    stuffptrs = FunctionThatReturnsArrayOfPointers ();

    do {...blah...} while (condition);

    Hunk_FreeToLowMark (hunkmark);
}
Alternatively if you're happy to be Windows only and if you don't like Hunk_Alloc, use HeapCreate to get a new heap, HeapAlloc from that heap as required, and HeapDestroy to just throw away all the memory when done (did I ever mention how awesome the Windows memory APIs were?) - malloc, calloc, realloc, etc are fine and cutesy for a purist, but they completely lack the extra flexibility to do this kind of thing cleanly and robustly (translation: CRT memory management is a joke and needs to be taken outside and shot).

With C++ you'd just use an std::vector.
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
DolphinsOfCydonia
Posts: 21
Joined: Tue Nov 08, 2011 4:01 am

Re: Function Returning Array Of Pointers Concept

Post by DolphinsOfCydonia »

Baker wrote:That would require a struct. ...I would prefer a pure data type,
Are you scared of the overhead in mallocing n nodes?
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

It makes the implementation really ugly looking. Yet apparently, this is what I am going to do as I worked through the planning.

I wasn't really looking to make a custom return type just for this. But it solves some other issues.
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

Now I can have a geometry function intersecting a polygon and return a set of vertices (need to change data type of course):

Simple implementaion (could make even simpler reducing it to 2 defines). Re-entrant friendly!!! :D Verified the 2 step memory free. Mechanics are simple.
float** myList = myPrimesList (); // Returns a null terminated list :D

for (int i = 0; myList != NULL ; i++)
printf ("This prime is %f", *myList); // Prints 2 then 3, 5, 7 ... note that for loop stops on null terminator

pArrayFree (myList); // free calloc memory

Code: Select all

//----------------------------------------------------------------------------
float** myPrimesList (void)
{
	float myPrimes[] = {2, 3, 5, 7};
	const int numMyPrimes = sizeof(myPrimes)/sizeof(myPrimes[0]);
	
	float*	myReturnData	= Memory_calloc (numMyPrimes + 0, sizeof(myPrimes[0]), "Array data");	// Malloc return data block
	float** myReturnPointer	= Memory_calloc (numMyPrimes + 1, sizeof(float*), "Array of pointers");			// Malloc return pointer block
	

	for (int i = 0; i < numMyPrimes; i++)
	{
		myReturnData[i] 	= myPrimes[i];
		myReturnPointer[i] 	= &myReturnData[i]; 
	}
	myReturnPointer[numMyPrimes] = NULL;	
	
	return myReturnPointer;
}

// -------------------------------------------------------------------------------------
void pArrayFree (float** myArray)
{
	Memory_free (*myArray);
	Memory_free (myArray);
	
}
I could probably modify all the above to use type void and make pArrayFree just a define. And then make the thing that builds the variable length array a define ... reducing implementation into a compact and simple insertion of a couple of lines of user-friendly looking code.

But I'll settle for this proof of concept for now.
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

Version 2: Any data type :D

Works like this. Simple to for receiving function to look through return results. Simple for sending function to make those results.

No unusual data types. Just use whatever data type you already were using.

Code: Select all

main ()
{
	float** myList = myPrimesList2 ();
	
	for (int i = 0; myList[i]; i++)
		printf ("This prime is %f", *myList[i]);
	
	pArrayFree (myList);
}

float** myPrimesList2 (void) // Function that returns a list of something
{
	const float myPrimes[] = {2, 3, 5, 7};
	const int numMyPrimes = sizeof(myPrimes)/sizeof(myPrimes[0]);
	
	return pReturnArray(myPrimes, numMyPrimes, sizeof(myPrimes[0]) );
}
Simple supporting functions x 2:

1) One to generate the list in the function returning the array of results (allocates the memory).
2) One to free the memory and discard that list of results (so memory is reclaimed).

Code: Select all

void** pReturnArray (const void* sourceItems, const int numItems, const size_t itemSizeBytes)
{
	void*	myReturnData	= Memory_calloc (numItems + 0, itemSizeBytes, "Array data");	// Malloc return data block
	void** myReturnPointer	= Memory_calloc (numItems + 1, sizeof(void*), "Array of pointers");			// Malloc return pointer block
	
	myReturnPointer[numItems] = NULL;	// NULL terminate list
	
	for (int n = 0; n < numItems; n++)
	{
		int addy = n * itemSizeBytes;
		memcpy (&myReturnData[addy], &sourceItems[addy], itemSizeBytes);
		myReturnPointer[n] = &myReturnData[addy];
		
	}
	
	return myReturnPointer;
}

void pArrayFree (void** myArray)
{
	Memory_free (*myArray);
	Memory_free (myArray);
	
}
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

Applied to vertices:

Code: Select all

typedef struct { float x, y, z; } vert_t;

int main (void)
{
	vert_t** myVertList = Triangle_Vertices ();
	
	for (int i = 0; myVertList[i]; i++)   printf ("Vert is %f %f %f\n", myVertList[i]->x, myVertList[i]->y, myVertList[i]->z);
		
	pArrayFree (myVertList);
}

vert_t* Triangle_Vertices (void)
{
	vert_t myTriangle [] = {  {24, 25, 26},  {52, 51, 50},  {0,  21, 83} };
	
	const int sizeOfItem = sizeof(myTriangle[0]);
	const int numItems = sizeof(myTriangle)/sizeOfItem;
	
	return pReturnArray(myTriangle, numItems, sizeOfItem );
}
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

Applied to vec3_t ... looks a bit different dereferencing an array of arrays pointers

Code: Select all

int main (void)
{
	vec3_t** myVertList = Triangle_Vertices ();
	
	for (int i = 0; myVertList[i]; i++) //Awkward looking double dereferencing of Array of X Y Z floats that is vec3_t
		printf ("This vert is %f %f %f\n", myVertList[0][i][0], myVertList[0][i][1], myVertList[0][i][2]);  
		
	pArrayFree (myVertList);
}

vec3_t** Triangle_Vertices (void)
{
	vec3_t myTriangle [] = { {24, 25, 26}, {52, 51, 50}, {0,  21, 83}, };
	
	const int sizeOfItem = sizeof(myTriangle[0]);
	const int numItems = sizeof(myTriangle)/sizeOfItem;
	
	return pReturnArray(myTriangle, numItems, sizeOfItem );
}
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Post by Baker »

And vec3_t, make the awkward looking stuff look normalize for array of pointers to arrays:

Code: Select all

	vec3_t** myVertList = Triangle_Vertices ();
	
	for (int i = 0; myVertList[i]; i++) 
	{
		vec_t* thisVert = myVertList[0][i]; // <--Awkward double dereferencing
		printf ("This vert is %f %f %f\n", thisVert[0], thisVert[1], thisVert[2]);  
	}	
	
	pArrayFree (myVertList);
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Jay Dolan
Posts: 59
Joined: Tue Jan 22, 2008 7:16 pm
Location: Naples, FL
Contact:

Re: Function Returning Array Of Pointers Concept

Post by Jay Dolan »

I started using glib for collections management in Quake2World. It provides single and double linked lists, hash tables, and pointer arrays, all with a very complete API for allocating, extending, removing and freeing elements. Glib's memory allocator also uses slice management by default, which can rival the performance of Quake's "gimme a big heap and I'll take it from here" approach. Basically, my code is a lot smaller and tighter now, and I don't waste any time implementing or debugging ad-hoc collections (unless it's truly warranted for performance, like particles lists).

There are a dozen or so other great uses for glib in a Quake engine, too. Look at all the stuff you get for free:
https://developer.gnome.org/glib/2.37/
Post Reply