How to create a linked list from a binary input file? With first few bytes being an int and the next few a char and so on

Question

I want to create a linked list from an input binary file. The first sizeof(int) bytes is an int and the next sizeof(char) bytes is a char and it keeps going like that. What I want to do is create a linked list from this file where each node in the linked list contains a character and a tree node that contains this int value.

I am stuck when it comes to creating a linked list out of this file. If it was just a regular file with ints and no binary and no chars, I would have used fscanf to read the file and stored its contents into an array, and then I would have traversed through the array and made the nodes. However, I am confused when these chars are present in the file. Could anyone please help me and tell me if there is a way to create a linked list?

Edits ->

ListNode *head = malloc(sizeof(ListNode)*sizeoffile);

//how do i find the size of the file.
//if it was a file with just integers, I would have done something like this
// int value;
// int count = 0;
//while(fscanf(fptr, "%d", &value)==1)
//{
//  count++;
//}
//But now that there is chars, I am really confused how I would determine  
//the size of the file.

while(!feof(fptr))
{
  fread(head, sizeof(int)+sizeof(char), 1, fptr);
}

I know this is not right. ^

Answer 1

Step 1: Assume all data from an external source (e.g. from a file) is potentially malicious and/or corrupted and/or came from a different computer (with different sizeof(int) and different endianness).

Step 2: Define your file format properly (taking step 1 into account). E.g. maybe it's supposed to be a value in the range 123 to 123456 that's stored as 4 consecutive bytes in little endian order (it should never be an int); and maybe it's a byte containing an ASCII character (it should never be a "random whatever character set the compiler felt like using char").

Step 3: Write some code to load data from the file into an array of bytes. If the file is expected to be small you can use realloc() to increase the size of the buffer if the buffer wasn't big enough (but make sure there's a "max. file size" so that a malicious attacker can't trick you into consuming all available RAM and crashing due to "out of memory"). If the file is expected to be larger; look into functions like mmap(). Alternatively, you can have a "read next part of file; parse next part of file" loop that recycles a fixed sized buffer.

Step 4: Write code to parse the "array of bytes" data and check that it actually complies with the file format specs in every way possible. For example, unsigned long value = buffer[0] + (buffer[1] << 8) + (buffer[2] << 16) + (buffer[3] << 24) and if( (value < 123) || (value > 123456) ) { // Data is malformed.

Step 5: Once you've parsed the data (and written code to handle every conceivable error condition in an appropriate manner, and know for a fact that it must be valid data), you can store the data in a structure and add that structure to a linked list. E.g.

    // Parse and check it

    if(bufferSize < position + 5) {
        return "File ends in the middle of a record";
    }
    unsigned long value = buffer[position] + (buffer[position+1] << 8) + (buffer[position+2] << 16) + (buffer[position+3] << 24);
    if( (value < 123) || (value > 123456) ) {
        return "Data was malformed (integer out of range)";
     }

    if( (buffer[position+4] < 0x20) || (buffer[position+4] >= 0x7F) ) {
        return "Data was malformed (character not printable ASCII)";
    }

    // Create a structure

    myStructureType * myStruct = malloc(sizeof(myStructureType));
    if(myStruct == NULL) {
        return "Failed to allocate memory for structure";
    }
    myStruct->value = value;
    myStruct->character = buffer[position+4];
    position += 5;

    // Add structure to singly linked list

    myStruct->next = NULL;
    if(listFirst == NULL) {
       listFirst =  myStruct;
    } else {
       listLast->next =  myStruct;
    }
    listLast =  myStruct;

Answer 2

Ok, so I suggest that you forget about linked lists. Just stick to the first problem: reading data from a binary file.

The text of the problem is unclear about the size of the objects, so let's assume that it says: "There is a binary file which contains widgets composed by a 32 bit integer (little endian) and an 8 bit number representing an ASCII character. Dump all the widgets to stdout one per line representing the integer in base 10 followed by a space and then the character".

Let's assume that your int is 32 bit little endian and your char is a signed byte, i.e. let's assume you are on one of the 99.9% of the machines in the world.

Now you have to read the widgets, that is an int and a char. There are usually two functions you have to chose from when reading: fscanf and fread. The first one reads from data formatted for humans to read, while the second one reads bytes as they are from a file. Which one do you need now? the second one, so we need to use that.

In your code you write

while (!feof(fptr))

This is always wrong. The only correct way for reading a file is:

while (1) {
    // Read
    // Check
    // Use
}

Then you can find a way to read and check in the while condition, but believe me: write it this way the first time.

So lets populate the above template. To check if fread succeeded you need to check if it returned the number of elements you asked for.

while (1) {
    int i;
    char c;
    // Read
    int ok1 = fread(&i, 4, 1, fptr);
    int ok2 = fread(&c, 1, 1, fptr);
    // Check
    if (ok1 != 1 || ok2 != 1)
        break;
    // Use
    printf("%d %c\n", i, c);
}

Of course you can pack this in the while condition, but I don't see a reason for that.

Now I'd test this with your input and with a good debugger and check if all the data in the file gets printed out. If everything is ok, you can move on to the rest of the problem, that is putting these widgets in a linked list.

Here I assumed that you didn't learn structs yet. If this is not the case, you can work with them:

struct widget {
    int i;
    char c;
};

[...]

while (1) {
    struct widget w;
    // Read
    int ok1 = fread(&w.i, 4, 1, fptr);
    int ok2 = fread(&w.c, 1, 1, fptr);
    // Check
    if (ok1 != 1 || ok2 != 1)
        break;
    // Use
    printf("%d %c\n", w.i, w.c);
}

Don't be deluded by the fact that the widget has the same structure of your data on file. You cannot trust that

fread(&w, 5, 1, fptr); // No! Don't do this

will read your data correctly. When making a struct, the compiler can put all the space it want between fields, so I wouldn't be surprised if sizeof(widget) returned 8.

Disclaimer: I wrote the code directly on the browser and didn't check it!

Answer 3

I think you are getting a little too caught up in something that isn't really a fundamental problem. if you need to create a linked list from a file, you could use fscanf() or fread() or whatever you like to read a file into a buffer and manipulate that buffer as you wish. The same logic for parsing an array of ints (read in from a file) can be applied to parsing a buffer of strings from a binary file (you say binary file with sizeof(int), sizeof(char) consecutively so I'm going to assume you mean it can be read into a buffer)

You say

"If it was just a regular file with ints and no binary and no chars, I would have used fscanf to read the file and stored its contents into an array, and then I would have traversed through the array and made the nodes"

you can traverse a string, or list of strings (however you decide to parse your buffer) using the same logic to make nodes. That's the beauty of a data structure, or struct if you will, in C.