Iterator-like interface for extracting records from a blob

Question

I have a blob whose format is something like:

(id1,key1,value1)(id2,key2,value2)....

where id is a uint32_t, and key and value are null-terminated strings. I am looking for an iterator-like interface that will extract records from the blob.

This is what I have come up with:

typedef struct blob_ {  
    uint32_t size;  // length of the buffer
    char buf[]; 
}blob;

typedef struct record_ {
    uint32_t id;    // id
    char *key;      // pointer to key in the blob
    char *value;    // pointer to value in the blob
    char *next;    // pointer to where the next record starts
} record;  

static record
get_next_obj(const char* begin, const char* end)
{
    record obj; 
    if (begin == end) {
        obj.id = 0;
        obj.key = NULL;
        obj.value = NULL;
        obj._next = NULL;
    } else {

        memcpy(&obj.id, begin, sizeof(uint32_t));
        begin += sizeof(uint32_t);

        obj.key = begin;
        while(begin < end && *begin != '\0')
            ++begin;

        ++begin;

        obj.value = begin;
        while(begin < end && *begin != '\0')
            ++begin;
        ++begin;

        obj.next = begin;
    }
    return obj;
}

record
blob_list_next(const blob *data, const record *prev)
{
    const char *begin, *end;

    begin = prev->next;
    end = data->buf + data->size;

    return get_next_obj(begin, end);
}

record
blob_list_begin(const blob *data)
{
    const char *begin, *end;

    begin = data->buf;
    end = data->buf + data->size;
    return get_next_obj(begin, end);
}

record
blob_list_end(const blob *data)
{
    record obj;
    obj.id = 0;
    obj.key = NULL;
    obj.value = NULL;
    obj.next = NULL;
    return obj;
}

Then the API will be accessed with something like this:

record obj;  
record obj_end;
// comp is a comparison operator of two record objects  
for (obj = blob_list_begin(data), obj_end = blob_list_end(data); 
    comp(obj, obj_end) == false; obj = blob_list_next(data, &obj))  {   
   // access the obj
}  

I used return-by-value semantics because I wanted to avoid calling malloc(). There will be a maximum of 4096 records in a tuple.

Answer 1

Some random comments:

1. The behaviour of flexible array members are defined in the C99 standard, but undefined in C90. Because of that reason, you might want to add a compiler switch guard against C90 compilers:

   #if !defined __STDC_VERSION__ || (__STDC_VERSION__ < 199901L)
     #error Code must be compiled as C99 or later.
   #endif
   

2. Why is the data binary data char and not uint8_t? char may or may not be signed, depending on the compiler.

3. Consider inlining get_next_obj(). Since you return the struct by value, even good C compilers will generate a lot of overhead code from that. If you can weed out at least the internal return-by-value, the algorithm will be a bit faster.

4. Any reason why the record objects can't hold a prev pointer? That is, why can't they be a double-linked list instead of a single linked one? And on the topic of linked lists, you may want to consider changing the type of the next pointer:

   typedef struct record_ {
       uint32_t id;     // id
       char *key;       // pointer to key in the blob
       char *value;     // pointer to value in the blob
       record_ *next;   // pointer to the next record 
       record_ *prev;   // pointer to the previous record
   } record;  
   

   Or perhaps stuff all the record objects into a real linked list ADT.

Answer 2

Is a blob meant to be portable? If so consider endianness in the id - memcpy is not enough.

In get_next_obj:

• What if begin > end? Be defensive.

• Duplicate code in while loops needs extracting into a function. Consider using optimised library functions such as strchr(begin, '\0') or strlen(input) to find the terminator and check for over-running 'end'. Your loops stop at 'end' and ignore a missing '\0' before 'end'.

• You are returning non-static data 'record obj'. Better to pass-in a pointer to an empty record and return a pointer to it on success, NULL on failure (begin >= end) (instead of creating an empty object).

Your concept of a null object (containing 0,NULLs) to be used to terminate the loop is unnecessary. What is wrong with a NULL pointer returned from get_next_obj() when begin >= end ?

You main loop might be something like:

if (blob_list_begin(data, &obj)) {
    do {
        // access the obj
    } while (blob_list_next(data, &obj, &obj));
}

Or if you prefer:

record * pobj;
for (pobj = blob_list_begin(data, &obj); 
     pobj; 
     pobj = blob_list_next(data, &obj, &obj)) {
    // access the obj
}

Answer 3

You're just setting pointers in your function. If the original data changes, you will be accessing wrong data ...

char data[] = "\x01\x00\x00\x01key\0value";
p = get_next_obj(data, data + sizeof data);
if (p.id != 16777217) /* error */;
if (strcmp(p.key, "key")) /* error */;
if (strcmp(p.value, "value")) /* error */;

strcpy(data, "\x02\x00\x00\x02FOO\x00BAR");
if (p.id != 16777217) /* error */;             // same id as before
if (strcmp(p.key, "FOO")) /* error */;         // but different data!
if (strcmp(p.value, "BAR")) /* error */;

I think you will need to malloc and copy ...

Answer 4

If you're not totally wedded to emulating the STL interface, you could replace the obj_end ... comp(obj, obj_end) with a simple is_not_end(&obj). Passing both by value just to see if obj is filled with well-known magic values is unnecessary.

Oh, and if your input is incorrect, you can advance off the end:

    while(begin < end && *begin != '\0')
        ++begin;

    ++begin;

if the loop terminates because begin == end, you'll still increment begin again.

Other that that, it looks fine to me.