2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
0
\$\begingroup\$

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 ...

\$\endgroup\$
  • \$\begingroup\$ It's not uncommon to do this while parsing a buffer though, so long as the buffer is kept unchanged until you've finished parsing it. You only need to copy when a value should live longer than that. \$\endgroup\$ – Useless Mar 16 '12 at 15:36
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.