diff options
Diffstat (limited to 'libglusterfs/src/rbthash.c')
| -rw-r--r-- | libglusterfs/src/rbthash.c | 663 |
1 files changed, 323 insertions, 340 deletions
diff --git a/libglusterfs/src/rbthash.c b/libglusterfs/src/rbthash.c index 4d654066e13..0068b7b881e 100644 --- a/libglusterfs/src/rbthash.c +++ b/libglusterfs/src/rbthash.c @@ -8,7 +8,6 @@ cases as published by the Free Software Foundation. */ - #include "rbthash.h" #include "rb.h" #include "locking.h" @@ -19,59 +18,57 @@ #include <pthread.h> #include <string.h> - int -rbthash_comparator (void *entry1, void *entry2, void *param) +rbthash_comparator(void *entry1, void *entry2, void *param) { - int ret = 0; - rbthash_entry_t *e1 = NULL; - rbthash_entry_t *e2 = NULL; + int ret = 0; + rbthash_entry_t *e1 = NULL; + rbthash_entry_t *e2 = NULL; - if ((!entry1) || (!entry2) || (!param)) - return -1; + if ((!entry1) || (!entry2) || (!param)) + return -1; - e1 = (rbthash_entry_t *)entry1; - e2 = (rbthash_entry_t *)entry2; + e1 = (rbthash_entry_t *)entry1; + e2 = (rbthash_entry_t *)entry2; - if (e1->keylen != e2->keylen) { - if (e1->keylen < e2->keylen) - ret = -1; - else if (e1->keylen > e2->keylen) - ret = 1; - } else - ret = memcmp (e1->key, e2->key, e1->keylen); + if (e1->keylen != e2->keylen) { + if (e1->keylen < e2->keylen) + ret = -1; + else if (e1->keylen > e2->keylen) + ret = 1; + } else + ret = memcmp(e1->key, e2->key, e1->keylen); - return ret; + return ret; } - int -__rbthash_init_buckets (rbthash_table_t *tbl, int buckets) +__rbthash_init_buckets(rbthash_table_t *tbl, int buckets) { - int i = 0; - int ret = -1; - - if (!tbl) - return -1; - - for (; i < buckets; i++) { - LOCK_INIT (&tbl->buckets[i].bucketlock); - tbl->buckets[i].bucket = rb_create ((rb_comparison_func *)rbthash_comparator, tbl, NULL); - if (!tbl->buckets[i].bucket) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RB_TABLE_CREATE_FAILED, "Failed to " - "create rb table bucket"); - ret = -1; - goto err; - } + int i = 0; + int ret = -1; + + if (!tbl) + return -1; + + for (; i < buckets; i++) { + LOCK_INIT(&tbl->buckets[i].bucketlock); + tbl->buckets[i].bucket = rb_create( + (rb_comparison_func *)rbthash_comparator, tbl, NULL); + if (!tbl->buckets[i].bucket) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RB_TABLE_CREATE_FAILED, + "Failed to " + "create rb table bucket"); + ret = -1; + goto err; } + } - ret = 0; + ret = 0; err: - return ret; + return ret; } - /* * rbthash_table_init - Initialize a RBT based hash table * @buckets - Number of buckets in the hash table @@ -83,391 +80,377 @@ err: */ rbthash_table_t * -rbthash_table_init (glusterfs_ctx_t *ctx, int buckets, rbt_hasher_t hfunc, - rbt_data_destroyer_t dfunc, - unsigned long expected_entries, - struct mem_pool *entrypool) +rbthash_table_init(glusterfs_ctx_t *ctx, int buckets, rbt_hasher_t hfunc, + rbt_data_destroyer_t dfunc, unsigned long expected_entries, + struct mem_pool *entrypool) { - rbthash_table_t *newtab = NULL; - int ret = -1; - - if (!hfunc) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_HASH_FUNC_ERROR, - "Hash function not given"); - return NULL; + rbthash_table_t *newtab = NULL; + int ret = -1; + + if (!hfunc) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_HASH_FUNC_ERROR, + "Hash function not given"); + return NULL; + } + + if (!entrypool && !expected_entries) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_INVALID_ENTRY, + "Both mem-pool and expected entries not provided"); + return NULL; + } + + if (entrypool && expected_entries) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_INVALID_ENTRY, + "Both mem-pool and expected entries are provided"); + return NULL; + } + + newtab = GF_CALLOC(1, sizeof(*newtab), gf_common_mt_rbthash_table_t); + if (!newtab) + return NULL; + + newtab->buckets = GF_CALLOC(buckets, sizeof(struct rbthash_bucket), + gf_common_mt_rbthash_bucket); + if (!newtab->buckets) { + goto free_newtab; + } + + if (expected_entries) { + newtab->entrypool = mem_pool_new_ctx(ctx, rbthash_entry_t, + expected_entries); + if (!newtab->entrypool) { + goto free_buckets; } - - if (!entrypool && !expected_entries) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_INVALID_ENTRY, - "Both mem-pool and expected entries not provided"); - return NULL; - } - - if (entrypool && expected_entries) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_INVALID_ENTRY, - "Both mem-pool and expected entries are provided"); - return NULL; - } - - - newtab = GF_CALLOC (1, sizeof (*newtab), - gf_common_mt_rbthash_table_t); - if (!newtab) - return NULL; - - newtab->buckets = GF_CALLOC (buckets, sizeof (struct rbthash_bucket), - gf_common_mt_rbthash_bucket); - if (!newtab->buckets) { - goto free_newtab; - } - - if (expected_entries) { - newtab->entrypool = - mem_pool_new_ctx (ctx, rbthash_entry_t, - expected_entries); - if (!newtab->entrypool) { - goto free_buckets; - } - newtab->pool_alloced = _gf_true; - } else { - newtab->entrypool = entrypool; - } - - LOCK_INIT (&newtab->tablelock); - INIT_LIST_HEAD (&newtab->list); - newtab->numbuckets = buckets; - ret = __rbthash_init_buckets (newtab, buckets); - - if (ret == -1) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_INIT_BUCKET_FAILED, - "Failed to init buckets"); - if (newtab->pool_alloced) - mem_pool_destroy (newtab->entrypool); - } else { - gf_msg_trace (GF_RBTHASH, 0, "Inited hash table: buckets:" - " %d", buckets); - } - - newtab->hashfunc = hfunc; - newtab->dfunc = dfunc; + newtab->pool_alloced = _gf_true; + } else { + newtab->entrypool = entrypool; + } + + LOCK_INIT(&newtab->tablelock); + INIT_LIST_HEAD(&newtab->list); + newtab->numbuckets = buckets; + ret = __rbthash_init_buckets(newtab, buckets); + + if (ret == -1) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INIT_BUCKET_FAILED, + "Failed to init buckets"); + if (newtab->pool_alloced) + mem_pool_destroy(newtab->entrypool); + } else { + gf_msg_trace(GF_RBTHASH, 0, + "Inited hash table: buckets:" + " %d", + buckets); + } + + newtab->hashfunc = hfunc; + newtab->dfunc = dfunc; free_buckets: - if (ret == -1) - GF_FREE (newtab->buckets); + if (ret == -1) + GF_FREE(newtab->buckets); free_newtab: - if (ret == -1) { - GF_FREE (newtab); - newtab = NULL; - } + if (ret == -1) { + GF_FREE(newtab); + newtab = NULL; + } - return newtab; + return newtab; } rbthash_entry_t * -rbthash_init_entry (rbthash_table_t *tbl, void *data, void *key, int keylen) +rbthash_init_entry(rbthash_table_t *tbl, void *data, void *key, int keylen) { - int ret = -1; - rbthash_entry_t *entry = NULL; - - if ((!tbl) || (!data) || (!key)) - return NULL; - - entry = mem_get (tbl->entrypool); - if (!entry) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_GET_ENTRY_FAILED, - "Failed to get entry from mem-pool"); - goto ret; - } - - entry->data = data; - entry->key = GF_MALLOC (keylen, gf_common_mt_char); - if (!entry->key) { - goto free_entry; - } - - INIT_LIST_HEAD (&entry->list); - memcpy (entry->key, key, keylen); - entry->keylen = keylen; - entry->keyhash = tbl->hashfunc (entry->key, entry->keylen); - gf_msg_trace (GF_RBTHASH, 0, "HASH: %u", entry->keyhash); - - ret = 0; + int ret = -1; + rbthash_entry_t *entry = NULL; + + if ((!tbl) || (!data) || (!key)) + return NULL; + + entry = mem_get(tbl->entrypool); + if (!entry) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_ENTRY_FAILED, + "Failed to get entry from mem-pool"); + goto ret; + } + + entry->data = data; + entry->key = GF_MALLOC(keylen, gf_common_mt_char); + if (!entry->key) { + goto free_entry; + } + + INIT_LIST_HEAD(&entry->list); + memcpy(entry->key, key, keylen); + entry->keylen = keylen; + entry->keyhash = tbl->hashfunc(entry->key, entry->keylen); + gf_msg_trace(GF_RBTHASH, 0, "HASH: %u", entry->keyhash); + + ret = 0; free_entry: - if (ret == -1) { - mem_put (entry); - entry = NULL; - } + if (ret == -1) { + mem_put(entry); + entry = NULL; + } ret: - return entry; + return entry; } - void -rbthash_deinit_entry (rbthash_table_t *tbl, rbthash_entry_t *entry) +rbthash_deinit_entry(rbthash_table_t *tbl, rbthash_entry_t *entry) { + if (!entry) + return; - if (!entry) - return; - - GF_FREE (entry->key); - - if (tbl) { - if ((entry->data) && (tbl->dfunc)) - tbl->dfunc (entry->data); + GF_FREE(entry->key); - LOCK (&tbl->tablelock); - { - list_del_init (&entry->list); - } - UNLOCK (&tbl->tablelock); + if (tbl) { + if ((entry->data) && (tbl->dfunc)) + tbl->dfunc(entry->data); - mem_put (entry); + LOCK(&tbl->tablelock); + { + list_del_init(&entry->list); } + UNLOCK(&tbl->tablelock); - return; -} + mem_put(entry); + } + return; +} static struct rbthash_bucket * -rbthash_entry_bucket (rbthash_table_t *tbl, rbthash_entry_t * entry) +rbthash_entry_bucket(rbthash_table_t *tbl, rbthash_entry_t *entry) { - int nbucket = 0; + int nbucket = 0; - nbucket = (entry->keyhash % tbl->numbuckets); - gf_msg_trace (GF_RBTHASH, 0, "BUCKET: %d", nbucket); - return &tbl->buckets[nbucket]; + nbucket = (entry->keyhash % tbl->numbuckets); + gf_msg_trace(GF_RBTHASH, 0, "BUCKET: %d", nbucket); + return &tbl->buckets[nbucket]; } - int -rbthash_insert_entry (rbthash_table_t *tbl, rbthash_entry_t *entry) +rbthash_insert_entry(rbthash_table_t *tbl, rbthash_entry_t *entry) { - struct rbthash_bucket *bucket = NULL; - int ret = -1; - - if ((!tbl) || (!entry)) - return -1; - - bucket = rbthash_entry_bucket (tbl, entry); - if (!bucket) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_GET_BUCKET_FAILED, - "Failed to get bucket"); - goto err; + struct rbthash_bucket *bucket = NULL; + int ret = -1; + + if ((!tbl) || (!entry)) + return -1; + + bucket = rbthash_entry_bucket(tbl, entry); + if (!bucket) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED, + "Failed to get bucket"); + goto err; + } + + ret = 0; + LOCK(&bucket->bucketlock); + { + if (!rb_probe(bucket->bucket, (void *)entry)) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INSERT_FAILED, + "Failed to insert" + " entry"); + ret = -1; } - - ret = 0; - LOCK (&bucket->bucketlock); - { - if (!rb_probe (bucket->bucket, (void *)entry)) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_INSERT_FAILED, "Failed to insert" - " entry"); - ret = -1; - } - } - UNLOCK (&bucket->bucketlock); + } + UNLOCK(&bucket->bucketlock); err: - return ret; + return ret; } - int -rbthash_insert (rbthash_table_t *tbl, void *data, void *key, int keylen) +rbthash_insert(rbthash_table_t *tbl, void *data, void *key, int keylen) { - rbthash_entry_t *entry = NULL; - int ret = -1; - - if ((!tbl) || (!data) || (!key)) - return -1; - - entry = rbthash_init_entry (tbl, data, key, keylen); - if (!entry) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_INIT_ENTRY_FAILED, - "Failed to init entry"); - goto err; - } + rbthash_entry_t *entry = NULL; + int ret = -1; - ret = rbthash_insert_entry (tbl, entry); + if ((!tbl) || (!data) || (!key)) + return -1; - if (ret == -1) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_INSERT_FAILED, - "Failed to insert entry"); - rbthash_deinit_entry (tbl, entry); - } + entry = rbthash_init_entry(tbl, data, key, keylen); + if (!entry) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INIT_ENTRY_FAILED, + "Failed to init entry"); + goto err; + } - LOCK (&tbl->tablelock); - { - list_add_tail (&entry->list, &tbl->list); - } - UNLOCK (&tbl->tablelock); + ret = rbthash_insert_entry(tbl, entry); + + if (ret == -1) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_INSERT_FAILED, + "Failed to insert entry"); + rbthash_deinit_entry(tbl, entry); + } + + LOCK(&tbl->tablelock); + { + list_add_tail(&entry->list, &tbl->list); + } + UNLOCK(&tbl->tablelock); err: - return ret; + return ret; } static struct rbthash_bucket * -rbthash_key_bucket (rbthash_table_t *tbl, void *key, int keylen) +rbthash_key_bucket(rbthash_table_t *tbl, void *key, int keylen) { - uint32_t keyhash = 0; - int nbucket = 0; + uint32_t keyhash = 0; + int nbucket = 0; - if ((!tbl) || (!key)) - return NULL; + if ((!tbl) || (!key)) + return NULL; - keyhash = tbl->hashfunc (key, keylen); - gf_msg_trace (GF_RBTHASH, 0, "HASH: %u", keyhash); - nbucket = (keyhash % tbl->numbuckets); - gf_msg_trace (GF_RBTHASH, 0, "BUCKET: %u", nbucket); + keyhash = tbl->hashfunc(key, keylen); + gf_msg_trace(GF_RBTHASH, 0, "HASH: %u", keyhash); + nbucket = (keyhash % tbl->numbuckets); + gf_msg_trace(GF_RBTHASH, 0, "BUCKET: %u", nbucket); - return &tbl->buckets[nbucket]; + return &tbl->buckets[nbucket]; } - void * -rbthash_get (rbthash_table_t *tbl, void *key, int keylen) +rbthash_get(rbthash_table_t *tbl, void *key, int keylen) { - struct rbthash_bucket *bucket = NULL; - rbthash_entry_t *entry = NULL; - rbthash_entry_t searchentry = {0, }; - - if ((!tbl) || (!key)) - return NULL; - - bucket = rbthash_key_bucket (tbl, key, keylen); - if (!bucket) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_GET_BUCKET_FAILED, - "Failed to get bucket"); - return NULL; - } - - searchentry.key = key; - searchentry.keylen = keylen; - LOCK (&bucket->bucketlock); - { - entry = rb_find (bucket->bucket, &searchentry); - } - UNLOCK (&bucket->bucketlock); - - if (!entry) - return NULL; - - return entry->data; + struct rbthash_bucket *bucket = NULL; + rbthash_entry_t *entry = NULL; + rbthash_entry_t searchentry = { + 0, + }; + + if ((!tbl) || (!key)) + return NULL; + + bucket = rbthash_key_bucket(tbl, key, keylen); + if (!bucket) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_GET_BUCKET_FAILED, + "Failed to get bucket"); + return NULL; + } + + searchentry.key = key; + searchentry.keylen = keylen; + LOCK(&bucket->bucketlock); + { + entry = rb_find(bucket->bucket, &searchentry); + } + UNLOCK(&bucket->bucketlock); + + if (!entry) + return NULL; + + return entry->data; } - void * -rbthash_remove (rbthash_table_t *tbl, void *key, int keylen) +rbthash_remove(rbthash_table_t *tbl, void *key, int keylen) { - struct rbthash_bucket *bucket = NULL; - rbthash_entry_t *entry = NULL; - rbthash_entry_t searchentry = {0, }; - void *dataref = NULL; - - if ((!tbl) || (!key)) - return NULL; - - bucket = rbthash_key_bucket (tbl, key, keylen); - if (!bucket) { - gf_msg (GF_RBTHASH, GF_LOG_ERROR, 0, - LG_MSG_RBTHASH_GET_BUCKET_FAILED, - "Failed to get bucket"); - return NULL; - } - - searchentry.key = key; - searchentry.keylen = keylen; - - LOCK (&bucket->bucketlock); - { - entry = rb_delete (bucket->bucket, &searchentry); - } - UNLOCK (&bucket->bucketlock); - - if (!entry) - return NULL; - - GF_FREE (entry->key); - dataref = entry->data; - - LOCK (&tbl->tablelock); - { - list_del_init (&entry->list); - } - UNLOCK (&tbl->tablelock); - - mem_put (entry); - - return dataref; + struct rbthash_bucket *bucket = NULL; + rbthash_entry_t *entry = NULL; + rbthash_entry_t searchentry = { + 0, + }; + void *dataref = NULL; + + if ((!tbl) || (!key)) + return NULL; + + bucket = rbthash_key_bucket(tbl, key, keylen); + if (!bucket) { + gf_msg(GF_RBTHASH, GF_LOG_ERROR, 0, LG_MSG_RBTHASH_GET_BUCKET_FAILED, + "Failed to get bucket"); + return NULL; + } + + searchentry.key = key; + searchentry.keylen = keylen; + + LOCK(&bucket->bucketlock); + { + entry = rb_delete(bucket->bucket, &searchentry); + } + UNLOCK(&bucket->bucketlock); + + if (!entry) + return NULL; + + GF_FREE(entry->key); + dataref = entry->data; + + LOCK(&tbl->tablelock); + { + list_del_init(&entry->list); + } + UNLOCK(&tbl->tablelock); + + mem_put(entry); + + return dataref; } - void -rbthash_entry_deiniter (void *entry, void *rbparam) +rbthash_entry_deiniter(void *entry, void *rbparam) { - if (!entry) - return; + if (!entry) + return; - rbthash_deinit_entry (rbparam, entry); + rbthash_deinit_entry(rbparam, entry); } - void -rbthash_table_destroy_buckets (rbthash_table_t *tbl) +rbthash_table_destroy_buckets(rbthash_table_t *tbl) { - int x = 0; - if (!tbl) - return; + int x = 0; + if (!tbl) + return; - for (;x < tbl->numbuckets; x++) { - LOCK_DESTROY (&tbl->buckets[x].bucketlock); - rb_destroy (tbl->buckets[x].bucket, rbthash_entry_deiniter); - } + for (; x < tbl->numbuckets; x++) { + LOCK_DESTROY(&tbl->buckets[x].bucketlock); + rb_destroy(tbl->buckets[x].bucket, rbthash_entry_deiniter); + } - return; + return; } - void -rbthash_table_destroy (rbthash_table_t *tbl) +rbthash_table_destroy(rbthash_table_t *tbl) { - if (!tbl) - return; + if (!tbl) + return; - rbthash_table_destroy_buckets (tbl); - if (tbl->pool_alloced) - mem_pool_destroy (tbl->entrypool); + rbthash_table_destroy_buckets(tbl); + if (tbl->pool_alloced) + mem_pool_destroy(tbl->entrypool); - GF_FREE (tbl->buckets); - GF_FREE (tbl); + GF_FREE(tbl->buckets); + GF_FREE(tbl); } - void -rbthash_table_traverse (rbthash_table_t *tbl, rbt_traverse_t traverse, - void *mydata) +rbthash_table_traverse(rbthash_table_t *tbl, rbt_traverse_t traverse, + void *mydata) { - rbthash_entry_t *entry = NULL; + rbthash_entry_t *entry = NULL; - if ((tbl == NULL) || (traverse == NULL)) { - goto out; - } + if ((tbl == NULL) || (traverse == NULL)) { + goto out; + } - LOCK (&tbl->tablelock); + LOCK(&tbl->tablelock); + { + list_for_each_entry(entry, &tbl->list, list) { - list_for_each_entry (entry, &tbl->list, list) { - traverse (entry->data, mydata); - } + traverse(entry->data, mydata); } - UNLOCK (&tbl->tablelock); + } + UNLOCK(&tbl->tablelock); out: - return; + return; } |