#include "usg_common.h"
|
#include "hashtable.h"
|
#include "mm.h"
|
#include "sem_util.h"
|
#include <set>
|
|
typedef struct tailq_entry_t
|
{
|
void *value;
|
int key;
|
/*
|
* This holds the pointers to the next and previous joint in
|
* the tail queue.
|
*/
|
TAILQ_ENTRY(tailq_entry_t) joint;
|
} tailq_entry_t;
|
|
#define START_KEY 1000
|
|
typedef TAILQ_HEAD(tailq_header_t, tailq_entry_t) tailq_header_t;
|
|
static size_t hashcode(int key);
|
|
void hashtable_init(hashtable_t *hashtable )
|
{
|
|
memset(hashtable, 0, sizeof(hashtable_t));
|
hashtable->mutex = SemUtil::get(IPC_PRIVATE, 1);
|
hashtable->wlock = SemUtil::get(IPC_PRIVATE, 1);
|
hashtable->cond = SemUtil::get(IPC_PRIVATE, 1);
|
hashtable->readcnt = 0;
|
}
|
|
|
void *_hashtable_get(hashtable_t *hashtable, int key)
|
{
|
size_t code = hashcode(key);
|
tailq_entry_t *item;
|
tailq_header_t *my_tailq_head = hashtable->array[code] ;
|
if ( my_tailq_head == NULL)
|
{
|
return NULL;
|
}
|
else
|
{
|
|
TAILQ_FOREACH(item, my_tailq_head, joint)
|
{
|
if (key == item->key)
|
return item->value;
|
}
|
}
|
return NULL;
|
|
}
|
|
void * _hashtable_put(hashtable_t *hashtable, int key, void *value)
|
{
|
size_t code = hashcode(key);
|
void *oldvalue;
|
tailq_entry_t *item;
|
tailq_header_t *my_tailq_head = hashtable->array[code] ;
|
if ( my_tailq_head == NULL)
|
{
|
my_tailq_head = (tailq_header_t*) mm_malloc(sizeof(tailq_header_t ));
|
TAILQ_INIT(my_tailq_head);
|
hashtable->array[code] = my_tailq_head;
|
goto putnew;
|
}
|
|
TAILQ_FOREACH(item, my_tailq_head, joint)
|
{
|
if (key ==item->key)
|
{
|
oldvalue = item -> value;
|
item->key= key;
|
item -> value = value;
|
return oldvalue;
|
}
|
}
|
putnew:
|
item = (tailq_entry_t *) mm_malloc(sizeof(tailq_entry_t));
|
item->key = key;
|
item -> value = value;
|
TAILQ_INSERT_TAIL(my_tailq_head, item, joint);
|
return NULL;
|
}
|
|
void *hashtable_remove(hashtable_t *hashtable, int key)
|
{
|
size_t code = hashcode(key);
|
tailq_entry_t *item;
|
void *oldvalue;
|
|
SemUtil::dec(hashtable->wlock);
|
tailq_header_t *my_tailq_head = hashtable->array[code] ;
|
if ( my_tailq_head == NULL)
|
{
|
SemUtil::inc(hashtable->wlock);
|
return NULL;
|
}
|
else
|
{
|
for (item = TAILQ_FIRST(my_tailq_head); item != NULL; item = TAILQ_NEXT(item, joint))
|
{
|
if (key == item->key)
|
{
|
oldvalue = item->value;
|
/* Remove the item from the tail queue. */
|
TAILQ_REMOVE(my_tailq_head, item, joint);
|
|
/* mm_free the item as we don't need it anymore. */
|
mm_free(item);
|
SemUtil::inc(hashtable->wlock);
|
return oldvalue;
|
}
|
}
|
}
|
SemUtil::inc(hashtable->wlock);
|
return NULL;
|
|
}
|
|
|
|
|
|
void hashtable_removeall(hashtable_t *hashtable)
|
{
|
tailq_entry_t *item;
|
SemUtil::dec(hashtable->wlock);
|
for (int i = 0; i < MAPSIZE; i++)
|
{
|
tailq_header_t *my_tailq_head = hashtable->array[i] ;
|
|
if (my_tailq_head == NULL )
|
continue;
|
|
while ((item = TAILQ_FIRST(my_tailq_head)) )
|
{
|
TAILQ_REMOVE(my_tailq_head, item, joint);
|
mm_free(item);
|
}
|
mm_free(my_tailq_head);
|
hashtable->array[i] = NULL;
|
}
|
SemUtil::inc(hashtable->wlock);
|
}
|
|
/**
|
* for debug
|
*/
|
void hashtable_printall(hashtable_t *hashtable)
|
{
|
tailq_entry_t *item;
|
for (int i = 0; i < MAPSIZE; i++)
|
{
|
tailq_header_t *my_tailq_head = hashtable->array[i] ;
|
|
if (my_tailq_head == NULL )
|
continue;
|
|
printf("code=%d\n", i);
|
TAILQ_FOREACH(item, my_tailq_head, joint)
|
{
|
printf("%d:%s\n", item->key, (char *)item->value);
|
}
|
printf("\n");
|
}
|
}
|
|
static size_t hashcode(int key)
|
{
|
|
return key % MAPSIZE;
|
/*printf("hashfun = %ld\n", code);*/
|
}
|
|
|
int hashtable_alloc_key(hashtable_t *hashtable) {
|
int key = START_KEY;
|
SemUtil::dec(hashtable->wlock);
|
|
while(_hashtable_get(hashtable, key) != NULL) {
|
key++;
|
}
|
|
_hashtable_put(hashtable, key, (void *)1);
|
SemUtil::inc(hashtable->wlock);
|
return key;
|
}
|
|
void *hashtable_get(hashtable_t *hashtable, int key) {
|
SemUtil::dec(hashtable->mutex);
|
hashtable->readcnt++;
|
if (hashtable->readcnt == 1) {
|
//获取读写锁
|
SemUtil::dec(hashtable->wlock);
|
}
|
SemUtil::inc(hashtable->mutex);
|
|
void * res = _hashtable_get(hashtable, key);
|
|
SemUtil::dec(hashtable->mutex);
|
hashtable->readcnt--;
|
if(hashtable->readcnt == 0) {
|
//释放读写锁
|
SemUtil::inc(hashtable->wlock);
|
//通知写
|
SemUtil::set(hashtable->cond, 1);
|
}
|
SemUtil::inc(hashtable->mutex);
|
return res;
|
}
|
|
void hashtable_put(hashtable_t *hashtable, int key, void *value) {
|
SemUtil::dec(hashtable->mutex);
|
while (hashtable->readcnt > 0)
|
{
|
SemUtil::set(hashtable->cond, 0);
|
SemUtil::inc(hashtable->mutex);
|
//等待写通知
|
SemUtil::dec(hashtable->cond);
|
|
SemUtil::dec(hashtable->mutex);
|
|
}
|
SemUtil::inc(hashtable->mutex);
|
|
//获取读写锁
|
SemUtil::dec(hashtable->wlock);
|
_hashtable_put(hashtable, key, value);
|
//释放读写锁
|
SemUtil::inc(hashtable->wlock);
|
}
|
|
|
|
void hashtable_foreach(hashtable_t *hashtable, hashtable_foreach_cb cb) {
|
tailq_entry_t *item;
|
for (int i = 0; i < MAPSIZE; i++) {
|
tailq_header_t *my_tailq_head = hashtable->array[i] ;
|
|
if (my_tailq_head == NULL )
|
continue;
|
|
TAILQ_FOREACH(item, my_tailq_head, joint)
|
{
|
cb(item->key, item -> value);
|
}
|
}
|
}
|
|
std::set<int> * hashtable_keyset(hashtable_t *hashtable) {
|
std::set<int> *keyset = new std::set<int>;
|
tailq_entry_t *item;
|
for (int i = 0; i < MAPSIZE; i++) {
|
tailq_header_t *my_tailq_head = hashtable->array[i] ;
|
|
if (my_tailq_head == NULL )
|
continue;
|
|
TAILQ_FOREACH(item, my_tailq_head, joint)
|
{
|
keyset->insert(item->key);
|
}
|
}
|
return keyset;
|
}
|
