plist_to_bin optimization

[xdeng]

The performance of the plist_to_bin function is poor when the plist file has 320000 nodes， I tried to modify the hashtable function and it was half faster.

hashtable.h

typedef struct hashentry_t {
    void *key;
    void *value;
} hashentry_t;

typedef unsigned int(*hash_func_t)(const void* key);
typedef int (*compare_func_t)(const void *a, const void *b);
typedef void (*free_func_t)(void *ptr);

typedef struct he_array_t {
    hashentry_t *pdata;
    long len;
    long capacity;
    long capacity_step;
} he_array_t;

typedef struct hashtable_t {
    he_array_t *entries[4096];
    size_t count;
    hash_func_t hash_func;
    compare_func_t compare_func;
    free_func_t free_func;
} hashtable_t;

hashtable_t* hash_table_new(hash_func_t hash_func, compare_func_t compare_func, free_func_t free_func);
void hash_table_destroy(hashtable_t *ht);

void hash_table_insert(hashtable_t* ht, void *key, void *value);
void* hash_table_lookup(hashtable_t* ht, void *key);
void hash_table_remove(hashtable_t* ht, void *key);

hashtable.c

he_array_t *he_array_new(int capacity)
{
    he_array_t *ha = (he_array_t*)malloc(sizeof(he_array_t));
    ha->pdata = (hashentry_t*)malloc(sizeof(hashentry_t) * capacity);
    ha->capacity = capacity;
    ha->capacity_step = (capacity > 4096) ? 4096 : capacity;
    ha->len = 0;
    return ha;
}

void he_array_free(he_array_t *ha)
{
    if (!ha) return;
    if (ha->pdata) {
        free(ha->pdata);
    }
    free(ha);
}

void he_array_insert(he_array_t *ha, hashentry_t *data, long array_index)
{
    long remaining;
    if (!ha || !ha->pdata) return;
    remaining = ha->capacity-ha->len;
    if (remaining == 0) {
        ha->pdata = realloc(ha->pdata, sizeof(hashentry_t) * (ha->capacity + ha->capacity_step));
        ha->capacity += ha->capacity_step;
    }
    if (array_index < 0 || array_index >= ha->len) {
        memcpy(&ha->pdata[ha->len], data, sizeof(hashentry_t));
    } else {
        memmove(&ha->pdata[array_index+1], &ha->pdata[array_index], (ha->len-array_index) * sizeof(hashentry_t));
        memcpy(&ha->pdata[array_index], data, sizeof(hashentry_t));
    }
    ha->len++;
}

void he_array_add(he_array_t *ha, hashentry_t *data)
{
    he_array_insert(ha, data, -1);
}

void he_array_remove(he_array_t *ha, long array_index)
{
    if (!ha || !ha->pdata || array_index < 0) return;
    if (ha->len == 0 || array_index >= ha->len) return;
    if (ha->len == 1) {
        memset(&ha->pdata[0], 0, sizeof(hashentry_t));
    } else {
        memmove(&ha->pdata[array_index], &ha->pdata[array_index+1], (ha->len-array_index-1) * sizeof(hashentry_t));
    }
    ha->len--;
}

void he_array_set(he_array_t *ha, hashentry_t *data, long array_index)
{
    if (!ha || !ha->pdata || array_index < 0) return;
    if (ha->len == 0 || array_index >= ha->len) return;
    memcpy(&ha->pdata[array_index], data, sizeof(hashentry_t));
}

hashentry_t* he_array_index(he_array_t *ha, long array_index)
{
    if (!ha) return NULL;
    if (array_index < 0 || array_index >= ha->len) {
        return NULL;
    }
    return &ha->pdata[array_index];
}

long he_array_size(he_array_t *ha)
{
    return ha->len;
}

hashtable_t* hash_table_new(hash_func_t hash_func, compare_func_t compare_func, free_func_t free_func)
{
    hashtable_t* ht = (hashtable_t*)malloc(sizeof(hashtable_t));
    int i;
    for (i = 0; i < 4096; i++) {
        ht->entries[i] = he_array_new(8);
    }
    ht->count = 0;
    ht->hash_func = hash_func;
    ht->compare_func = compare_func;
    ht->free_func = free_func;
    return ht;
}

void hash_table_destroy(hashtable_t *ht)
{
    int i = 0;

    if (!ht) return;

    for (i = 0; i < 4096; i++) {
        he_array_t* a = ht->entries[i];
        if(ht->free_func){
            int j;
            for (j = 0; j < he_array_size(a); j++)
            {
                hashentry_t* e = he_array_index(a, j);
                ht->free_func(e->value);
            }
        }
        he_array_free(a);
    }
    free(ht);
}

void hash_table_insert(hashtable_t* ht, void *key, void *value)
{
    unsigned int hash;
    int idx0, i;
    he_array_t* a;
    hashentry_t entry;

    if (!ht || !key) return;

    hash = ht->hash_func(key);

    idx0 = hash & 0xFFF;

    // get the idx0 list
    a = ht->entries[idx0];
    for (i = 0; i < he_array_size(a); i++)
    {
        hashentry_t* e = he_array_index(a, i);
        if(ht->compare_func(e->key, key)){
            // element already present. replace value.
            e->value = value;
            return;
        }
    }

    // if we get here, the element is not yet in the list.

    // make a new entry.
    entry.key = key;
    entry.value = value;
    he_array_add(a, &entry);
    ht->count++;
}

void* hash_table_lookup(hashtable_t* ht, void *key)
{
    unsigned int hash;
    int idx0, i;
    he_array_t* a;

    if (!ht || !key) return NULL;
    hash = ht->hash_func(key);

    idx0 = hash & 0xFFF;

    a = ht->entries[idx0];
    for (i = 0; i < he_array_size(a); i++)
    {
        hashentry_t* e = he_array_index(a, i);
        if(ht->compare_func(e->key, key)){
            return e->value;
        }
    }
    return NULL;
}

void hash_table_remove(hashtable_t* ht, void *key)
{
    unsigned int hash;
    int idx0, i;
    he_array_t* a;

    if (!ht || !key) return;

    hash = ht->hash_func(key);

    idx0 = hash & 0xFFF;

    // get the idx0 list
    a = ht->entries[idx0];
    for (i = 0; i < he_array_size(a); i++)
    {
        hashentry_t* e = he_array_index(a, i);
        if(ht->compare_func(e->key, key)){
            // found element, remove it from the list
            if(ht->free_func){
                ht->free_func(e->value);
            }
            he_array_remove(a, i);
            return;
        }
    }
}

[xdeng]

The code is very poorly written for reference only. you can try try

[Artoria2e5]

Any interest in finishing this? The array thing looks interesting.

[nikias]

Yes. This will be addressed after the next release which is due in a few days.