C question: creating an array of NULL pointers?

Discussion in '3DS - Homebrew Development and Emulators' started by mashers, Oct 19, 2015.

  1. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    Hi guys

    I'm looking at the title scanning code in the grid launcher. Currently it works as follows:
    1. A for loop iterates across the titles on the device
    2. Within the loop, the details, title ID and smdh data are assigned to a static menu entry struct
    3. A pointer to a new menu entry is defined and malloc'ed
    4. The struct containing the title data is memcpy'ed to the new entry created in step 3
    5. The pointer to the menu entry copy is added to the array of menu entries
    interestingly, if I remove all of the code which reads the title details and smdh data, then populating the title menu takes just as long. So I think the memory operations are what is taking the bulk of the time.

    I'm thinking of changing the process so nothing is copied until it's actually needed. Here's the process I'm thinking of:
    1. A for loop iterates across the titles on the device
    2. For each title, a NULL pointer is added to the menu entry array
    3. When the title menu is being drawn, the appropriate item from the array is retrieved
    4. If the retrieved menu entry is NULL then the title info and smdh data are retrieved and written back to the array
    This way a maximum of 12 items will be read at a time (3 rows of 4 icons). My question is, how would I go about achieving something like this? I don't think you can actually add a NULL pointer to an array. Any ideas would be appreciated!
     


  2. Gocario

    Gocario GBAFail'd

    Member
    640
    560
    Sep 5, 2015
    France
    Bourg Palette
    Isn't a pointer just a value (of the memory address)?
     
  3. daxtsu

    daxtsu GBAtemp Guru

    Member
    5,490
    3,877
    Jun 9, 2007
    If you have an array of pointers, you can add null pointers just fine. Random example (C++):

    Code:
    #include <stdio.h>
    
    int main(int argc, char** argv)
    {
        int number1 = 5, number2 = 4, number3 = 7;
    
        const int arraySize = 4;
        int* arrayOfNumbers[arraySize] = { &number1, &number2, &number3, NULL };
    
        for (int i = 0; i < arraySize; ++i)
        {
            if (arrayOfNumbers[i] != NULL)
                printf("arrayOfNumbers[%d]: %d\n", i, *arrayOfNumbers[i]);
        }
    
        return 0;
    }
    
     
    Last edited by daxtsu, Oct 19, 2015
  4. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    Yes I believe so.

    Perfect, thanks! The problem I have now is that the menu entries array is of undetermined size so I can't allocate the values directly using square bracket notation. The entries are added as follows:

    Code:
    addMenuEntry(menu_s* m, menuEntry_s* me)
    {
        if(!m || !me)return;
    
        // add to the end of the list
        menuEntry_s** l = &m->entries;
        while(*l)l=&(*l)->next;
        *l = me;
        me->next = NULL;
        m->numEntries++;
    }
    
    This relies on the last entry in the array being NULL and all of the entries before it being non-NULL. Is there another way to skip to the end of the array and append a value?
     
  5. Gocario

    Gocario GBAFail'd

    Member
    640
    560
    Sep 5, 2015
    France
    Bourg Palette
    The only way I know to use dynamic array in C is the realloc function, (probably linked lists too?).

    Edit: Are you already using linked list (->next) ?
     
    Last edited by Gocario, Oct 19, 2015
  6. daxtsu

    daxtsu GBAtemp Guru

    Member
    5,490
    3,877
    Jun 9, 2007
    I don't think so, no. Linked lists typically have you go through the entire thing to find the end, as far as I know. I guess you could keep another variable somewhere that points to the current end of the list, but you'd have to remember to update it when you add or remove entries.
     
  7. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    That's no problem, the list is only populated in this one function. So I keep a pointer to the end of the list, and then for each title I add a NULL pointer and then update the end pointer to the new end of the list. Does that sound about right?
     
  8. MasterFeizz

    MasterFeizz GBAtemp Advanced Fan

    Member
    888
    826
    Oct 15, 2015
    United States
    Code:
    menuEntry_s** entries = (menuEntry_s *)malloc(sizeof(menuEntry_s*) * num_entries);
    
     
    shinyquagsire23 likes this.
  9. daxtsu

    daxtsu GBAtemp Guru

    Member
    5,490
    3,877
    Jun 9, 2007
    I think that will work, yeah. I've not used linked lists a lot, so I can't say that with 100% confidence.
     
  10. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    Would that allow the list to remain linked using menuEntry_s.next?

    I'll give it a go, thanks :)

    Edit - oh wait, filling the away with null pointers won't work either. Each menuEntry_s struct needs its 'next' variable set to point to the next entry otherwise iterating through the linked list won't work.
     
    Last edited by mashers, Oct 19, 2015
  11. MasterFeizz

    MasterFeizz GBAtemp Advanced Fan

    Member
    888
    826
    Oct 15, 2015
    United States
    If you want to use an array then you don't need menuEntry_s.next.
    If you want a linked list you don't need an array.
     
  12. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    Ok, so if I use an array then I either need to know how big it will be before creating it or realloc it when adding items. And if I use a linked list then I have to add the pointers in order to create the links between the pointers. Since I don't want to create all of the menuEntry_s structs at once then I guess my only choice is to count how many entries will be needed, then malloc enough space for them all. Does that sound about right?
     
  13. MasterFeizz

    MasterFeizz GBAtemp Advanced Fan

    Member
    888
    826
    Oct 15, 2015
    United States
    No, you have the right idea with the linked lists. Just store the pointer of the last item, that way you don't have to iterate through the whole list every time you add something.

    Edit - The code i showed above creates an array of pointers, not an array of actual entries.
     
    Last edited by MasterFeizz, Oct 19, 2015
  14. norips

    norips Member

    Newcomer
    32
    38
    Aug 13, 2012
    France
    I think you need to use vector for stocking pointer, it's easier to use
     
  15. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    The problem is that I'm attempting to begin with an array of NULL pointers so how can I link them? Here is the code which walks through the list to draw the menu entries:

    Code:
    menuEntry_s* me=m->entries;
        int i=0;
        int h=0;
        while(me) {
            if (!me->hidden && me->page == m->pagePosition) {
                h+=drawMenuEntry(me, GFX_BOTTOM, (i==m->selectedEntry && m->rowPosition>-1), m);
                totalDrawn++;
            }
           
            me=me->next;
            i++;
        }
        
    So if I populate the list only one page at a time, then the last entry on each page won't be linked to the first entry on the next page. So when drawMenu() is walking through the list, it will reach the last entry of the first page, check its 'next' pointer, find it to be NULL, and stop drawing. That means nothing beyond the first page will ever be drawn.

    — Posts automatically merged - Please don't double post! —

    I'd love to use vectors, but unfortunately dynamically sized vectors don't work well with ctrulib :(
     
  16. norips

    norips Member

    Newcomer
    32
    38
    Aug 13, 2012
    France
    Weird, I'm using it and for now don't have weird behavior
     
  17. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    For me they overflow if they are globally defined (which in my case they need to be).
     
  18. MasterFeizz

    MasterFeizz GBAtemp Advanced Fan

    Member
    888
    826
    Oct 15, 2015
    United States
    You don't want NULL pointers, you want pointers to empty structs. You have to malloc(sizeof(menuentry)) for each "next" you need empty.
     
  19. norips

    norips Member

    Newcomer
    32
    38
    Aug 13, 2012
    France
    For the initial post, you can check if the last element is NULL, launch the population function, if more page concat the new list, else if there is no more page return NULL
     
  20. mashers
    OP

    mashers Stubborn ape

    Member
    3,837
    5,153
    Jun 10, 2015
    Kongo Jungle
    But would that be any faster than memcpy'ing the actual struct which will be used? Remember as I said it seems to take just as long to create and add empty structs as it does to create, populate and add them. Would memalloc'ing the space for them be faster than this?