Parse values from a text file in C

Question

Possible Duplicate:
Parsing text in C

Say I have written to a text file in this format:

key1/value1
key2/value2
akey/withavalue
anotherkey/withanothervalue

I have a linked list like:

struct Node
{
    char *key;
    char *value;
    struct Node *next;
};

to hold the values. How would I read key1 and value1? I was thinking of putting line by line in a buffer and using strtok(buffer, '/'). Would that work? What other ways could work, maybe a bit faster or less prone to error? Please include a code sample if you can!

Answer 1

You could also use fscanf to parse the input lines directly into keys and values:

char key[80], value[80];
fscanf (pFile, "%s/%s", key, value);

However, the drawback of this approach is that you need to allocate big enough buffers for the keys and values in advance (or use a temp buffer, then copy its value into its final destination, allocated with the right size). With strtok you can check the length of each key and value, then allocate a buffer of exactly the right size to store it.

Update: As commenters pointed out, another (potentially more serious) drawback of fscanf is that it doesn't work for strings containing whitespace.

Answer 2

If you wouldn't mind having aboth the key and the walue in one memory block (two strings), you can just read into a buffer, find the '/' change it into '\0' and point the value pointer just behind the '\0' character. Just don't forget to call free() only on the key value (this will free both the key and the value).

Answer 3

cycle through lines:
1) find '/'
2) devide pair key/value at the position '/'
3) fill key and value
in code:

char* p;
if(p = strchr(str,'/')
{
  *p++ = 0;
  key = strdup(str);
  value = strdup(p);
}

Answer 4

if you say hold the value 27878 / 989797 like that

char *p; fscanf("%s/%s",p,(p+1));

Answer 5

Since your problem is a very good candidate for optimizing memory fragmentation, here is an implementation that uses some simple arcane magic to allocate all strings and the structure itself in a single piece of memory.

When destroying the node, you need only a single call to free(), to the node itself.

struct Node *list = NULL, **nextp = &list;
char buffer[1024];

while (fgets(buffer, sizeof buffer, file) != NULL) {
    struct Node *node;

    node = malloc(sizeof(struct Node) + strlen(buffer) + 1);
    node->key = strtok(strcpy((char*)(node+1), buffer), "/\r\n");
    node->value = strtok(NULL, "\r\n");
    node->next = NULL;
    *nextp = node;
    nextp = &node->next;
}

Explanation:

With 20 comments and one unexplained downvote, I think that the code needs some explanation, specially with regards to the tricks employed:

1. Building a linked list:

   struct Node *list = NULL, **nextp = &list;
   ...
   *nextp = node;
   nextp = &node->next;
   

   This is a trick to create a linked list iteratively in forward order without having to special-case the head of the list. It uses a pointer-to-pointer to the next node. First the nextp pointer points to the list head pointer; in the first iteration, the list head is set through this pointer-to-pointer and then nextp is moved to the next pointer of that node. Subsequent iterations fill the next pointer of the last node.

2. Single allocation:

   node = malloc(sizeof(struct Node) + strlen(buffer) + 1);
   node->key = ... strcpy((char*)(node+1), buffer) ...
   

   We have to deal with three pointers: the node itself, the key string and the value string. This usually would require three separate allocations (malloc, calloc, strdup...), and consequently free separate releases (free). Instead, in this case, the spaces of the tree elements are summed in sizeof(struct Node) + strlen(buffer) + 1 and passed to a single malloc call, which returns a single block of memory. The beginning of this block of memory is assigned to node, the structure itself. The additional memory (strlen(buffer)+1) comes right after the node, and it's address is obtained using pointer arithmetic using node+1. It is used to make a copy of the entire string read from the file ("key/value\n").

   Since malloc is called a single time for each node, a single allocation is made. It means that you don't need to call free(node->key) and free(node->value). In fact, it won't work at all. Just a single free(node) will take care of deallocating the structure and both strings in one block.

3. Line parsing:

   node->key = strtok(strcpy((char*)(node+1), buffer), "/\r\n");
   node->value = strtok(NULL, "\r\n");
   

   The first call to strtok returns the pointer to the beginning of the buffer itself. It looks for a '/' (additionally for end-of-line markers) and breaks the string there with a NUL character. So the "key/value\n" is broken in "key" and "value\n" with a NUL character in between, and a pointer to the first is returned and stored in node->key. The second call to strtok will work upon the remaining "value\n", strip the end-of-line marker and returning a pointer to "value", which is stored in node->value.

I hope this cleans all questions about the above solution... it is too much for a closed question. The complete test code is here.