Forum

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.

Moderator: InsideQC Admins

Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 5:22 am

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby DolphinsOfCydonia » Wed Feb 22, 2012 8:24 am

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.
DolphinsOfCydonia
 
Posts: 21
Joined: Tue Nov 08, 2011 4:01 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 12:49 pm

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby mh » Wed Feb 22, 2012 12:56 pm

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
User avatar
mh
 
Posts: 2283
Joined: Sat Jan 12, 2008 1:38 am

Re: Function Returning Array Of Pointers Concept

Postby DolphinsOfCydonia » Wed Feb 22, 2012 3:27 pm

Baker wrote:That would require a struct. ...I would prefer a pure data type,


Are you scared of the overhead in mallocing n nodes?
DolphinsOfCydonia
 
Posts: 21
Joined: Tue Nov 08, 2011 4:01 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 3:32 pm

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 5:02 pm

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[i] != NULL ; i++)
printf ("This prime is %f", *myList[i]); // 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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 6:59 pm

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 7:58 pm

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 8:38 pm

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby Baker » Wed Feb 22, 2012 9:26 pm

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 ..
User avatar
Baker
 
Posts: 3639
Joined: Tue Mar 14, 2006 5:15 am

Re: Function Returning Array Of Pointers Concept

Postby Jay Dolan » Tue Dec 17, 2013 1:53 pm

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/
User avatar
Jay Dolan
 
Posts: 58
Joined: Tue Jan 22, 2008 7:16 pm
Location: Naples, FL


Return to General Programming

Who is online

Users browsing this forum: No registered users and 1 guest