1
\$\begingroup\$

I have a list of key value pairs, that is used as an intermediate store for building URL parameters or JSON data. Currently this is done with a linked list:

struct _kvp {
    char *key;
    struct _v *value; /* the implementation of _v does not matter right now */
    unsigned char is_array;
    struct _kvp *next;
};

struct _kvp_store {
    t_object x_ob;
    struct _kvp *first_data;
    struct _kvp *last_data;
};

Now I want to be able to do several things with the key value pairs:

  • Add a value identified with a key, that is not an array member: If an item with the same key already exists, I will replace that. If that item is currently an array, all array members have to be deleted first. Otherwise, append the data to the list.
  • Add an array member to the linked list: if an item with the same key exists and is not an array member, then replace that with the new key value pair, else if an item with the same key already exists and is an array member, add the new key value pair after all other items with the same key, otherwise append to the list.

This means, that for every added or replaced item, the whole list has to be scanned, running it in O(n) for each item or O(n²) for building a list from scratch. Is there a better data structure in C to use for that, that is just as simple to implement?

static void kvp_replace_single(
        struct _kvp *const item, 
        struct _v *const value, 
        const unsigned char is_array) {
    kvp_val_free(item->value);
    item->value = value;
    item->is_array = is_array;
}

static void kvp_replace_array(
        struct _kvp *const item, 
        const char *const key, 
        struct _v *const value) {
    struct _kvp *to_free;

    kvp_val_free(item->value);
    item->value = value;
    item->is_array = 0;
    while (item->next != NULL && strcmp(item->next->key, key) == 0) {
        to_free = item->next;
        item->next = to_free->next;
        kvp_free(to_free);
    }   
}

static void kvp_add_array(
        struct _kvp_store *const store, 
        struct _kvp *const item, 
        char *const key, 
        struct _v *const value) {
    struct _kvp *it = item;
    struct _kvp *new;

    while (it->next != NULL && strcmp(it->next->key, key) == 0) {
        it = it->next;
    }
    new = kvp_create(key, value, 1);
    kvp_insert(store, it, new);
}

static void kvp_add(
        struct _kvp_store *const store, 
        char *const key, 
        struct _v *const value, 
        const unsigned char is_array) {
    struct _kvp *it = store->first_data;
    unsigned char found = 0;

    while (it != NULL) {
        if (strcmp(it->key, key) == 0) {
            found = 1;
            if (!it->is_array) {
                kvp_replace_single(it, value, is_array);
            } else if (!is_array) {
                kvp_replace_array(it, key, value);
            } else {
                kvp_add_array(store, it, key, value);
            }
            break;
        }
        it = it->next;
    }

    if (!found) {
        struct _kvp *new = kvp_create(key, value, is_array);
        kvp_insert(store, store->last_data, new);
    }
}
\$\endgroup\$
1
\$\begingroup\$

A hashtable sounds like a better fit for your problem than using a linked list like this, giving you O(1) lookup time in the average case (O(n) for worst case).

You can find a popular hashing algorithm here: djb2

Also are you sure of your use of const?

struct _kvp *const item;
const struct _kvp *item;
\$\endgroup\$
  • \$\begingroup\$ I first said you need to collision resolution (edited my reply), this is pretty much always needed, unless you know all the keys in advance and can use a perfect hash \$\endgroup\$ – Joakim Feb 23 '15 at 15:31

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.