Thread: DMA function and Binary Search of an array of character strings

Hi there, two questions if you all don't mind.

First of all, I have a function that reads in a text file here, and I'm trying to figure out how to change it to use dynamic memory allocation to set the size of the dictionary array:

Code:

int main(){

char dict [10000][20];
int size;

size = get_dict(dict);

}


int get_dict(char dict[][20]) {
    
    FILE * ifp = fopen("dictionary.txt", "r");
    int size, i;
    fscanf(ifp, "%d", &size);
    
    for (i=0; i<size; i++)
        fscanf(ifp, "%s", dict[i]);

    fclose(ifp);

    return size;
}

I just don't know the small details of syntax and all my attempts to change it have not worked so far. Also I'm not entirely sure of the proper syntax to pass around the dictionary array "dict[][]" to other functions once it's converted to DMA...


Secondly, whether or not I can figure out how to dynamically set my array or not, I'd like to set up a function that will perform a binary search through the dictionary file.

The dictionary file is [10000] length and is in alphabetical order.

I understand how to perform a binary search with an array of integers, but I'm not really sure how that translates to an array of characters.

I've spent a lot of time searching google and this forum history on the topic of character binary searches, and I can't find anything but some fragmented broken code here and there. If I can just learn the syntax and concepts I can work it into my own project.

Thank you in advance to anyone who takes the time to consider my questions.
-d

And Welcome to the forum, decoyoctopus!

The basic way to create a dynamically allocated array you can grow when necessary, requires a pointer and one or two sizes: size used, and size allocated:

Code:

char  **word = NULL;
size_t  words = 0;
size_t  words_max = 0;

Above, word stores items of type char *, and must be a pointer to those, therefore it is a pointer to a pointer to a char. (Just read from right to left, starting at the name, to decipher the type).

When the pointer is initialized to NULL, and the sizes to zero, there is no special initialization needed. Whenever you need to add N items (usually N == 1), you first make sure there is enough room:

Code:

    if (words + N > words_max) {
        size_t  temp_max;
        char  **temp;

        temp_max = words + N + 50;
        temp = realloc(word, temp_max * sizeof (*word));
        if (!temp) {
            fprintf(stderr, "Out of memory!\n");
            exit(1);
        }

        word = temp;
        words_max = temp_max;
    }

As usual, you will want to allocate a bunch of word pointers at once, so you don't do this for every single entry you add. The above one uses 50 (in addition to the ones you need right now), but the actual number depends on the situation. (The best solution, actually, is to start with a small number like 4 or 8, defined as a constant in your code, and up to a limit also defined as a constant in your code, you double the existing size. After the limit, you just increase by the limit. I left that out in case the complexity would scare you, but it works really well in practice.)
At minimum, #define WORD_CHUNK 50 and use WORD_CHUNK instead of 50 in the above code. Saves you a lot of trouble when -- when, not if -- you wish to change it.

A subtle point to realize is that even when reallocation fails, the original data is still available. If your program exits immediately, then it does not matter, because the allocated memory is always returned to the operating system. (Some forms of shared memory are an exception to that rule.)
The above version only modifies the list size and pointer when reallocation succeeds, because after a failure the old contents are still valid, and you might not always choose to abort the program. When the reallocation succeeds, the old pointer (and size) are no longer valid, and must be updated; while reallocation often resizes the memory area without moving it, you cannot rely on that, and must assume the memory area has moved. The above code does it all correctly. (Assuming there are no typos.)

Finally, that only allocates the pointers to individual words. Unless you read the entire text file into memory, and tokenize the words in the huge in-memory copy, you may need to duplicate (strdup()) or allocate and copy each string you wish to put in the list.