src/modules/sca/sca_hash.c
ce6a9ca2
 /*
  * Copyright (C) 2012 Andrew Mortensen
  *
313e77d3
  * This file is part of the sca module for Kamailio, a free SIP server.
ce6a9ca2
  *
  * The sca module is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation; either version 2 of the License, or
  * (at your option) any later version
  *
  * The sca module is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
c1e0ba69
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
ce6a9ca2
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with this program; if not, write to the Free Software
c1e0ba69
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA. 02110-1301 USA
ce6a9ca2
  */
d694ceba
 #include "sca_common.h"
 
 #include <assert.h>
 
 #include "sca.h"
 #include "sca_hash.h"
 
c1e0ba69
 int sca_hash_table_create(sca_hash_table **ht, unsigned int size)
d694ceba
 {
c1e0ba69
 	int i;
 
 	assert(ht != NULL);
 
 	*ht = shm_malloc(sizeof(sca_hash_table));
cf3c0132
 	if(*ht == NULL) {
c1e0ba69
 		LM_ERR("Failed to shm_malloc space for hash table\n");
 		return (-1);
d694ceba
 	}
 
c1e0ba69
 	(*ht)->size = size;
cf3c0132
 	(*ht)->slots = (sca_hash_slot *)shm_malloc(size * sizeof(sca_hash_slot));
 	if((*ht)->slots == NULL) {
c1e0ba69
 		LM_ERR("Failed to shm_malloc hash table slots\n");
 		shm_free(*ht);
 		*ht = NULL;
 		return (-1);
 	}
 	memset((*ht)->slots, 0, size * sizeof(sca_hash_slot));
 
cf3c0132
 	for(i = 0; i < (*ht)->size; i++) {
 		if(lock_init(&(*ht)->slots[i].lock) == NULL) {
c1e0ba69
 			LM_ERR("Failed to initialized lock in hash table slot %d\n", i);
 			shm_free(*ht);
 			*ht = NULL;
 			return (-1);
 		}
 	}
 
 	return (0);
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_slot_kv_insert_unsafe(sca_hash_slot *slot, void *value,
 		int (*e_compare)(str *, void *), void (*e_description)(void *),
 		void (*e_free)(void *))
d694ceba
 {
c1e0ba69
 	sca_hash_entry *new_entry;
 	sca_hash_entry **cur_entry;
 
 	assert(slot != NULL);
 	assert(value != NULL);
 	assert(e_free != NULL);
 
cf3c0132
 	new_entry = (sca_hash_entry *)shm_malloc(sizeof(sca_hash_entry));
 	if(new_entry == NULL) {
c1e0ba69
 		LM_ERR("Failed to shm_malloc new hash table entry for slot %p\n", slot);
 		return (-1);
 	}
 	new_entry->value = value;
 	new_entry->compare = e_compare;
 	new_entry->description = e_description;
 	new_entry->free_entry = e_free;
 	new_entry->slot = slot;
 
 	cur_entry = &slot->entries;
 	new_entry->next = *cur_entry;
 	*cur_entry = new_entry;
 
 	return (0);
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_slot_kv_insert(sca_hash_slot *slot, void *value,
 		int (*e_compare)(str *, void *), void (*e_description)(void *),
 		void (*e_free)(void *))
d694ceba
 {
c1e0ba69
 	int rc;
d694ceba
 
c1e0ba69
 	lock_get(&slot->lock);
d694ceba
 
cf3c0132
 	rc = sca_hash_table_slot_kv_insert_unsafe(
 			slot, value, e_compare, e_description, e_free);
d694ceba
 
c1e0ba69
 	lock_release(&slot->lock);
d694ceba
 
c1e0ba69
 	return (rc);
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_index_kv_insert(sca_hash_table *ht, int slot_idx,
 		void *value, int (*e_compare)(str *, void *),
 		void (*e_description)(void *), void (*e_free)(void *))
d694ceba
 {
c1e0ba69
 	assert(ht != NULL);
 	assert(ht->slots != NULL);
 	assert(slot_idx >= 0 && slot_idx < ht->size);
d694ceba
 
cf3c0132
 	return (sca_hash_table_slot_kv_insert(
 			&ht->slots[slot_idx], value, e_compare, e_description, e_free));
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_kv_insert(sca_hash_table *ht, str *key, void *value,
 		int (*e_compare)(str *, void *), void (*e_description)(void *),
 		void (*e_free)(void *))
d694ceba
 {
c1e0ba69
 	int hash_idx;
 	int rc;
d694ceba
 
c1e0ba69
 	assert(ht != NULL && !SCA_STR_EMPTY(key) && value != NULL);
d694ceba
 
c1e0ba69
 	hash_idx = sca_hash_table_index_for_key(ht, key);
cf3c0132
 	rc = sca_hash_table_index_kv_insert(
 			ht, hash_idx, value, e_compare, e_description, e_free);
d694ceba
 
c1e0ba69
 	return (rc);
d694ceba
 }
 
c1e0ba69
 void *sca_hash_table_slot_kv_find_unsafe(sca_hash_slot *slot, str *key)
d694ceba
 {
c1e0ba69
 	sca_hash_entry *e;
 	void *value = NULL;
d694ceba
 
c1e0ba69
 	assert(slot != NULL && !SCA_STR_EMPTY(key));
d694ceba
 
cf3c0132
 	for(e = slot->entries; e != NULL; e = e->next) {
 		if(e->compare(key, e->value) == 0) {
c1e0ba69
 			value = e->value;
 		}
d694ceba
 	}
 
c1e0ba69
 	return (value);
d694ceba
 }
 
c1e0ba69
 void *sca_hash_table_slot_kv_find(sca_hash_slot *slot, str *key)
d694ceba
 {
c1e0ba69
 	void *value;
d694ceba
 
c1e0ba69
 	lock_get(&slot->lock);
 	value = sca_hash_table_slot_kv_find_unsafe(slot, key);
 	lock_release(&slot->lock);
d694ceba
 
c1e0ba69
 	return (value);
d694ceba
 }
 
cf3c0132
 void *sca_hash_table_index_kv_find_unsafe(
 		sca_hash_table *ht, int slot_idx, str *key)
4369f775
 {
c1e0ba69
 	assert(ht != NULL && !SCA_STR_EMPTY(key));
 	assert(slot_idx >= 0 && slot_idx < ht->size);
4369f775
 
c1e0ba69
 	return (sca_hash_table_slot_kv_find_unsafe(&ht->slots[slot_idx], key));
4369f775
 }
 
cf3c0132
 void *sca_hash_table_index_kv_find(sca_hash_table *ht, int slot_idx, str *key)
d694ceba
 {
c1e0ba69
 	assert(ht != NULL && !SCA_STR_EMPTY(key));
 	assert(slot_idx >= 0 && slot_idx < ht->size);
d694ceba
 
c1e0ba69
 	return (sca_hash_table_slot_kv_find(&ht->slots[slot_idx], key));
d694ceba
 }
 
c1e0ba69
 void *sca_hash_table_kv_find(sca_hash_table *ht, str *key)
d694ceba
 {
c1e0ba69
 	int slot_idx;
d694ceba
 
c1e0ba69
 	slot_idx = sca_hash_table_index_for_key(ht, key);
d694ceba
 
c1e0ba69
 	return (sca_hash_table_index_kv_find(ht, slot_idx, key));
d694ceba
 }
 
cf3c0132
 sca_hash_entry *sca_hash_table_slot_kv_find_entry_unsafe(
 		sca_hash_slot *slot, str *key)
d694ceba
 {
c1e0ba69
 	sca_hash_entry *e = NULL;
d694ceba
 
c1e0ba69
 	assert(slot != NULL && !SCA_STR_EMPTY(key));
a2f99b96
 
cf3c0132
 	for(e = slot->entries; e != NULL; e = e->next) {
 		if(e->compare(key, e->value) == 0) {
c1e0ba69
 			break;
 		}
a2f99b96
 	}
 
c1e0ba69
 	return (e);
a2f99b96
 }
 
c1e0ba69
 sca_hash_entry *sca_hash_table_slot_kv_find_entry(sca_hash_slot *slot, str *key)
a2f99b96
 {
c1e0ba69
 	sca_hash_entry *e;
a2f99b96
 
c1e0ba69
 	lock_get(&slot->lock);
 	e = sca_hash_table_slot_kv_find_entry(slot, key);
 	lock_release(&slot->lock);
a2f99b96
 
c1e0ba69
 	return (e);
a2f99b96
 }
 
c1e0ba69
 void sca_hash_entry_free(sca_hash_entry *e)
a2f99b96
 {
c1e0ba69
 	assert(e != NULL);
2c968f5c
 
c1e0ba69
 	e->free_entry(e->value);
 	shm_free(e);
a2f99b96
 }
 
cf3c0132
 sca_hash_entry *sca_hash_table_slot_unlink_entry_unsafe(
 		sca_hash_slot *slot, sca_hash_entry *e)
a2f99b96
 {
c1e0ba69
 	sca_hash_entry **cur_e;
2c968f5c
 
c1e0ba69
 	assert(slot != NULL);
 	assert(e != NULL);
2c968f5c
 
cf3c0132
 	for(cur_e = &slot->entries; *cur_e != NULL; cur_e = &(*cur_e)->next) {
 		if(*cur_e == e) {
c1e0ba69
 			*cur_e = e->next;
e09af355
 
c1e0ba69
 			/* ensure any attempted traversal using this entry goes nowhere */
 			e->next = NULL;
 			e->slot = NULL;
e09af355
 
c1e0ba69
 			break;
 		}
a2f99b96
 	}
31e886ed
 
c1e0ba69
 	return (e);
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_slot_kv_delete_unsafe(sca_hash_slot *slot, str *key)
d694ceba
 {
c1e0ba69
 	sca_hash_entry *e;
d694ceba
 
c1e0ba69
 	e = sca_hash_table_slot_kv_find_entry_unsafe(slot, key);
cf3c0132
 	if(e == NULL) {
c1e0ba69
 		return (-1);
 	}
d694ceba
 
c1e0ba69
 	e = sca_hash_table_slot_unlink_entry_unsafe(slot, e);
cf3c0132
 	if(e) {
c1e0ba69
 		e->free_entry(e->value);
 		shm_free(e);
 	}
d694ceba
 
c1e0ba69
 	return (0);
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_slot_kv_delete(sca_hash_slot *slot, str *key)
d694ceba
 {
c1e0ba69
 	int rc;
d694ceba
 
c1e0ba69
 	lock_get(&slot->lock);
 	rc = sca_hash_table_slot_kv_delete_unsafe(slot, key);
 	lock_release(&slot->lock);
d694ceba
 
c1e0ba69
 	return (rc);
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_index_kv_delete(sca_hash_table *ht, int slot_idx, str *key)
d694ceba
 {
c1e0ba69
 	return (sca_hash_table_slot_kv_delete(&ht->slots[slot_idx], key));
d694ceba
 }
 
c1e0ba69
 int sca_hash_table_kv_delete(sca_hash_table *ht, str *key)
d694ceba
 {
c1e0ba69
 	int slot_idx;
d694ceba
 
c1e0ba69
 	slot_idx = sca_hash_table_index_for_key(ht, key);
d694ceba
 
c1e0ba69
 	return (sca_hash_table_index_kv_delete(ht, slot_idx, key));
d694ceba
 }
 
c1e0ba69
 static void sca_hash_slot_print(sca_hash_slot *hs)
d694ceba
 {
c1e0ba69
 	sca_hash_entry *e;
 
cf3c0132
 	for(e = hs->entries; e != NULL; e = e->next) {
 		if(e->description != NULL) {
c1e0ba69
 			e->description(e->value);
 		} else {
 			LM_DBG("0x%p\n", e->value);
 		}
d694ceba
 	}
 }
 
c1e0ba69
 void sca_hash_table_print(sca_hash_table *ht)
d694ceba
 {
c1e0ba69
 	unsigned int i;
d694ceba
 
cf3c0132
 	for(i = 0; i < ht->size; i++) {
c1e0ba69
 		LM_DBG("SLOT %d:\n", i);
 		sca_hash_slot_print(&ht->slots[i]);
 	}
d694ceba
 }
 
c1e0ba69
 void sca_hash_table_free(sca_hash_table *ht)
d694ceba
 {
c1e0ba69
 	sca_hash_entry *e, *e_tmp;
 	unsigned int i;
d694ceba
 
cf3c0132
 	if(ht == NULL) {
c1e0ba69
 		return;
d694ceba
 	}
 
cf3c0132
 	for(i = 0; i < ht->size; i++) {
 		if(ht->slots[i].entries == NULL) {
c1e0ba69
 			continue;
 		}
d694ceba
 
c1e0ba69
 		sca_hash_table_lock_index(ht, i);
d694ceba
 
cf3c0132
 		for(e = ht->slots[i].entries; e != NULL; e = e_tmp) {
c1e0ba69
 			e_tmp = e->next;
d694ceba
 
c1e0ba69
 			e->free_entry(e->value);
d694ceba
 
c1e0ba69
 			shm_free(e);
 		}
d694ceba
 
c1e0ba69
 		sca_hash_table_unlock_index(ht, i);
 
 		lock_destroy(&ht->slots[i].lock);
 		lock_dealloc(&ht->slots[i].lock);
 	}
d694ceba
 
c1e0ba69
 	shm_free(ht->slots);
 	shm_free(ht);
d694ceba
 }