Homebrew C question: creating an array of NULL pointers?

[mashers]

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!

 

[Gocario]

Isn't a pointer just a value (of the memory address)?

 

[daxtsu]

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!

If you have an array of pointers, you can add null pointers just fine. Random example (C++):

#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;
}

 

[mashers]

Isn't a pointer just a value (of the memory address)?

Yes I believe so.

If you have an array of pointers, you can add null pointers just fine. Random example (C++):

#include <stdio.h>
#include <stdint.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;
}

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:

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?

 

[Gocario]

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) ?

 

[daxtsu]

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.

 

[mashers]

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.

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?

 

[MasterFeizz]

menuEntry_s** entries = (menuEntry_s *)malloc(sizeof(menuEntry_s*) * num_entries);

 

[daxtsu]

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?

I think that will work, yeah. I've not used linked lists a lot, so I can't say that with 100% confidence.

 

[mashers]

menuEntry_s** entries = (menuEntry_s *)malloc(sizeof(menuEntry_s*) * num_entries);

Would that allow the list to remain linked using menuEntry_s.next?

I think that will work, yeah. I've not used linked lists a lot, so I can't say that with 100% confidence.

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.

 

[MasterFeizz]

Would that allow the list to remain linked using menuEntry_s.next?

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.

 

[mashers]

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.

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?

 

[MasterFeizz]

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?

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.

 

[norips]

I think you need to use vector for stocking pointer, it's easier to use

 

[mashers]

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.

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:

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.

--------------------- MERGED ---------------------------

I think you need to use vector for stocking pointer, it's easier to use

I'd love to use vectors, but unfortunately dynamically sized vectors don't work well with ctrulib

 

[norips]

Spoiler

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:

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.

--------------------- MERGED ---------------------------


I'd love to use vectors, but unfortunately dynamically sized vectors don't work well with ctrulib

Weird, I'm using it and for now don't have weird behavior

 

[mashers]

Weird, I'm using it and for now don't have weird behavior

For me they overflow if they are globally defined (which in my case they need to be).

 

[MasterFeizz]

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:

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.

--------------------- MERGED ---------------------------


I'd love to use vectors, but unfortunately dynamically sized vectors don't work well with ctrulib

You don't want NULL pointers, you want pointers to empty structs. You have to malloc(sizeof(menuentry)) for each "next" you need empty.

 

[norips]

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

 

[mashers]

You don't want NULL pointers, you want pointers to empty structs. You have to malloc(sizeof(menuentry)) for each "next" you need empty.

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?