/*
|
* Copyright (C) 2008 Philippe Gerum <rpm@xenomai.org>.
|
*
|
* This library is free software; you can redistribute it and/or
|
* modify it under the terms of the GNU Lesser General Public
|
* License as published by the Free Software Foundation; either
|
* version 2 of the License, or (at your option) any later version.
|
*
|
* This library is distributed in the hope that it will be useful,
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
* Lesser General Public License for more details.
|
|
* You should have received a copy of the GNU Lesser General Public
|
* License along with this library; if not, write to the Free Software
|
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
|
*/
|
|
#include <string.h>
|
#include <errno.h>
|
#include "boilerplate/lock.h"
|
#include "boilerplate/hash.h"
|
#include "boilerplate/debug.h"
|
|
/*
|
* Crunching routine borrowed from:
|
*
|
* lookup2.c, by Bob Jenkins, December 1996, Public Domain.
|
* hash(), hash2(), hash3, and mix() are externally useful functions.
|
* Routines to test the hash are included if SELF_TEST is defined.
|
* You can use this free for any purpose. It has no warranty.
|
*/
|
|
#define __mixer(a, b, c) \
|
{ \
|
a -= b; a -= c; a ^= (c>>13); \
|
b -= c; b -= a; b ^= (a<<8); \
|
c -= a; c -= b; c ^= (b>>13); \
|
a -= b; a -= c; a ^= (c>>12); \
|
b -= c; b -= a; b ^= (a<<16); \
|
c -= a; c -= b; c ^= (b>>5); \
|
a -= b; a -= c; a ^= (c>>3); \
|
b -= c; b -= a; b ^= (a<<10); \
|
c -= a; c -= b; c ^= (b>>15); \
|
}
|
|
static inline int store_key(struct hashobj *obj,
|
const void *key, size_t len,
|
const struct hash_operations *hops);
|
|
static inline void drop_key(struct hashobj *obj,
|
const struct hash_operations *hops);
|
|
#define GOLDEN_HASH_RATIO 0x9e3779b9 /* Arbitrary value. */
|
|
unsigned int __hash_key(const void *key, size_t length, unsigned int c)
|
{
|
const unsigned char *k = key;
|
unsigned int a, b, len;
|
|
len = (unsigned int)length;
|
a = b = GOLDEN_HASH_RATIO;
|
|
while (len >= 12) {
|
a += (k[0] +((unsigned int)k[1]<<8) +((unsigned int)k[2]<<16) +((unsigned int)k[3]<<24));
|
b += (k[4] +((unsigned int)k[5]<<8) +((unsigned int)k[6]<<16) +((unsigned int)k[7]<<24));
|
c += (k[8] +((unsigned int)k[9]<<8) +((unsigned int)k[10]<<16)+((unsigned int)k[11]<<24));
|
__mixer(a, b, c);
|
k += 12;
|
len -= 12;
|
}
|
|
c += (unsigned int)length;
|
|
switch (len) {
|
case 11: c += ((unsigned int)k[10]<<24);
|
case 10: c += ((unsigned int)k[9]<<16);
|
case 9 : c += ((unsigned int)k[8]<<8);
|
case 8 : b += ((unsigned int)k[7]<<24);
|
case 7 : b += ((unsigned int)k[6]<<16);
|
case 6 : b += ((unsigned int)k[5]<<8);
|
case 5 : b += k[4];
|
case 4 : a += ((unsigned int)k[3]<<24);
|
case 3 : a += ((unsigned int)k[2]<<16);
|
case 2 : a += ((unsigned int)k[1]<<8);
|
case 1 : a += k[0];
|
};
|
|
__mixer(a, b, c);
|
|
return c;
|
}
|
|
void __hash_init(void *heap, struct hash_table *t)
|
{
|
pthread_mutexattr_t mattr;
|
int n;
|
|
for (n = 0; n < HASHSLOTS; n++)
|
__list_init(heap, &t->table[n].obj_list);
|
|
pthread_mutexattr_init(&mattr);
|
pthread_mutexattr_settype(&mattr, mutex_type_attribute);
|
pthread_mutexattr_setprotocol(&mattr, PTHREAD_PRIO_INHERIT);
|
pthread_mutexattr_setpshared(&mattr, mutex_scope_attribute);
|
__RT(pthread_mutex_init(&t->lock, &mattr));
|
pthread_mutexattr_destroy(&mattr);
|
}
|
|
void hash_destroy(struct hash_table *t)
|
{
|
__RT(pthread_mutex_destroy(&t->lock));
|
}
|
|
static struct hash_bucket *do_hash(struct hash_table *t,
|
const void *key, size_t len)
|
{
|
unsigned int hash = __hash_key(key, len, 0);
|
return &t->table[hash & (HASHSLOTS-1)];
|
}
|
|
int __hash_enter(struct hash_table *t,
|
const void *key, size_t len,
|
struct hashobj *newobj,
|
const struct hash_operations *hops,
|
int nodup)
|
{
|
struct hash_bucket *bucket;
|
struct hashobj *obj;
|
int ret;
|
|
holder_init(&newobj->link);
|
ret = store_key(newobj, key, len, hops);
|
if (ret)
|
return ret;
|
|
bucket = do_hash(t, key, len);
|
write_lock_nocancel(&t->lock);
|
|
if (nodup && !list_empty(&bucket->obj_list)) {
|
list_for_each_entry(obj, &bucket->obj_list, link) {
|
if (obj->len != newobj->len)
|
continue;
|
if (hops->compare(__mptr(obj->key), __mptr(newobj->key),
|
obj->len) == 0) {
|
drop_key(newobj, hops);
|
ret = -EEXIST;
|
goto out;
|
}
|
}
|
}
|
|
list_append(&newobj->link, &bucket->obj_list);
|
out:
|
write_unlock(&t->lock);
|
|
return ret;
|
}
|
|
int hash_remove(struct hash_table *t, struct hashobj *delobj,
|
const struct hash_operations *hops)
|
{
|
struct hash_bucket *bucket;
|
struct hashobj *obj;
|
int ret = -ESRCH;
|
|
bucket = do_hash(t, __mptr(delobj->key), delobj->len);
|
|
write_lock_nocancel(&t->lock);
|
|
if (!list_empty(&bucket->obj_list)) {
|
list_for_each_entry(obj, &bucket->obj_list, link) {
|
if (obj == delobj) {
|
list_remove_init(&obj->link);
|
drop_key(obj, hops);
|
ret = 0;
|
goto out;
|
}
|
}
|
}
|
out:
|
write_unlock(&t->lock);
|
|
return __bt(ret);
|
}
|
|
struct hashobj *hash_search(struct hash_table *t, const void *key,
|
size_t len, const struct hash_operations *hops)
|
{
|
struct hash_bucket *bucket;
|
struct hashobj *obj;
|
|
bucket = do_hash(t, key, len);
|
|
read_lock_nocancel(&t->lock);
|
|
if (!list_empty(&bucket->obj_list)) {
|
list_for_each_entry(obj, &bucket->obj_list, link) {
|
if (obj->len != len)
|
continue;
|
if (hops->compare(__mptr(obj->key), key, len) == 0)
|
goto out;
|
}
|
}
|
obj = NULL;
|
out:
|
read_unlock(&t->lock);
|
|
return obj;
|
}
|
|
int hash_walk(struct hash_table *t, hash_walk_op walk, void *arg)
|
{
|
struct hash_bucket *bucket;
|
struct hashobj *obj, *tmp;
|
int ret, n;
|
|
read_lock_nocancel(&t->lock);
|
|
for (n = 0; n < HASHSLOTS; n++) {
|
bucket = &t->table[n];
|
if (list_empty(&bucket->obj_list))
|
continue;
|
list_for_each_entry_safe(obj, tmp, &bucket->obj_list, link) {
|
read_unlock(&t->lock);
|
ret = walk(t, obj, arg);
|
if (ret)
|
return __bt(ret);
|
read_lock_nocancel(&t->lock);
|
}
|
}
|
|
read_unlock(&t->lock);
|
|
return 0;
|
}
|
|
#ifdef CONFIG_XENO_PSHARED
|
|
static inline int store_key(struct hashobj *obj,
|
const void *key, size_t len,
|
const struct hash_operations *hops)
|
{
|
void *p;
|
|
assert(__mchk(obj));
|
|
if (len > sizeof(obj->static_key)) {
|
p = hops->alloc(len);
|
if (p == NULL)
|
return -ENOMEM;
|
assert(__mchk(p));
|
} else
|
p = obj->static_key;
|
|
memcpy(p, key, len);
|
obj->key = __moff(p);
|
obj->len = len;
|
|
return 0;
|
}
|
|
static inline void drop_key(struct hashobj *obj,
|
const struct hash_operations *hops)
|
{
|
const void *key = __mptr(obj->key);
|
|
if (key != obj->static_key)
|
hops->free((void *)key);
|
}
|
|
int __hash_enter_probe(struct hash_table *t,
|
const void *key, size_t len,
|
struct hashobj *newobj,
|
const struct hash_operations *hops,
|
int nodup)
|
{
|
struct hash_bucket *bucket;
|
struct hashobj *obj, *tmp;
|
struct service svc;
|
int ret;
|
|
holder_init(&newobj->link);
|
ret = store_key(newobj, key, len, hops);
|
if (ret)
|
return ret;
|
|
bucket = do_hash(t, key, len);
|
CANCEL_DEFER(svc);
|
write_lock(&t->lock);
|
|
if (!list_empty(&bucket->obj_list)) {
|
list_for_each_entry_safe(obj, tmp, &bucket->obj_list, link) {
|
if (obj->len != newobj->len)
|
continue;
|
if (hops->compare(__mptr(obj->key),
|
__mptr(newobj->key), obj->len) == 0) {
|
if (hops->probe(obj)) {
|
if (nodup) {
|
drop_key(newobj, hops);
|
ret = -EEXIST;
|
goto out;
|
}
|
continue;
|
}
|
list_remove_init(&obj->link);
|
drop_key(obj, hops);
|
}
|
}
|
}
|
|
list_append(&newobj->link, &bucket->obj_list);
|
out:
|
write_unlock(&t->lock);
|
CANCEL_RESTORE(svc);
|
|
return ret;
|
}
|
|
struct hashobj *hash_search_probe(struct hash_table *t,
|
const void *key, size_t len,
|
const struct hash_operations *hops)
|
{
|
struct hash_bucket *bucket;
|
struct hashobj *obj, *tmp;
|
struct service svc;
|
|
bucket = do_hash(t, key, len);
|
|
CANCEL_DEFER(svc);
|
write_lock(&t->lock);
|
|
if (!list_empty(&bucket->obj_list)) {
|
list_for_each_entry_safe(obj, tmp, &bucket->obj_list, link) {
|
if (obj->len != len)
|
continue;
|
if (hops->compare(__mptr(obj->key), key, len) == 0) {
|
if (!hops->probe(obj)) {
|
list_remove_init(&obj->link);
|
drop_key(obj, hops);
|
continue;
|
}
|
goto out;
|
}
|
}
|
}
|
obj = NULL;
|
out:
|
write_unlock(&t->lock);
|
CANCEL_RESTORE(svc);
|
|
return obj;
|
}
|
|
void pvhash_init(struct pvhash_table *t)
|
{
|
pthread_mutexattr_t mattr;
|
int n;
|
|
for (n = 0; n < HASHSLOTS; n++)
|
pvlist_init(&t->table[n].obj_list);
|
|
pthread_mutexattr_init(&mattr);
|
pthread_mutexattr_settype(&mattr, mutex_type_attribute);
|
pthread_mutexattr_setprotocol(&mattr, PTHREAD_PRIO_INHERIT);
|
pthread_mutexattr_setpshared(&mattr, PTHREAD_PROCESS_PRIVATE);
|
__RT(pthread_mutex_init(&t->lock, &mattr));
|
pthread_mutexattr_destroy(&mattr);
|
}
|
|
static struct pvhash_bucket *do_pvhash(struct pvhash_table *t,
|
const void *key, size_t len)
|
{
|
unsigned int hash = __hash_key(key, len, 0);
|
return &t->table[hash & (HASHSLOTS-1)];
|
}
|
|
int __pvhash_enter(struct pvhash_table *t,
|
const void *key, size_t len,
|
struct pvhashobj *newobj,
|
const struct pvhash_operations *hops,
|
int nodup)
|
{
|
struct pvhash_bucket *bucket;
|
struct pvhashobj *obj;
|
int ret = 0;
|
|
pvholder_init(&newobj->link);
|
newobj->key = key;
|
newobj->len = len;
|
bucket = do_pvhash(t, key, len);
|
|
write_lock_nocancel(&t->lock);
|
|
if (nodup && !pvlist_empty(&bucket->obj_list)) {
|
pvlist_for_each_entry(obj, &bucket->obj_list, link) {
|
if (obj->len != newobj->len)
|
continue;
|
if (hops->compare(obj->key, newobj->key, len) == 0) {
|
ret = -EEXIST;
|
goto out;
|
}
|
}
|
}
|
|
pvlist_append(&newobj->link, &bucket->obj_list);
|
out:
|
write_unlock(&t->lock);
|
|
return ret;
|
}
|
|
int pvhash_remove(struct pvhash_table *t, struct pvhashobj *delobj,
|
const struct pvhash_operations *hops)
|
{
|
struct pvhash_bucket *bucket;
|
struct pvhashobj *obj;
|
int ret = -ESRCH;
|
|
bucket = do_pvhash(t, delobj->key, delobj->len);
|
|
write_lock_nocancel(&t->lock);
|
|
if (!pvlist_empty(&bucket->obj_list)) {
|
pvlist_for_each_entry(obj, &bucket->obj_list, link) {
|
if (obj == delobj) {
|
pvlist_remove_init(&obj->link);
|
ret = 0;
|
goto out;
|
}
|
}
|
}
|
out:
|
write_unlock(&t->lock);
|
|
return __bt(ret);
|
}
|
|
struct pvhashobj *pvhash_search(struct pvhash_table *t,
|
const void *key, size_t len,
|
const struct pvhash_operations *hops)
|
{
|
struct pvhash_bucket *bucket;
|
struct pvhashobj *obj;
|
|
bucket = do_pvhash(t, key, len);
|
|
read_lock_nocancel(&t->lock);
|
|
if (!pvlist_empty(&bucket->obj_list)) {
|
pvlist_for_each_entry(obj, &bucket->obj_list, link) {
|
if (obj->len != len)
|
continue;
|
if (hops->compare(obj->key, key, len) == 0)
|
goto out;
|
}
|
}
|
obj = NULL;
|
out:
|
read_unlock(&t->lock);
|
|
return obj;
|
}
|
|
int pvhash_walk(struct pvhash_table *t, pvhash_walk_op walk, void *arg)
|
{
|
struct pvhash_bucket *bucket;
|
struct pvhashobj *obj, *tmp;
|
int ret, n;
|
|
read_lock_nocancel(&t->lock);
|
|
for (n = 0; n < HASHSLOTS; n++) {
|
bucket = &t->table[n];
|
if (pvlist_empty(&bucket->obj_list))
|
continue;
|
pvlist_for_each_entry_safe(obj, tmp, &bucket->obj_list, link) {
|
read_unlock(&t->lock);
|
ret = walk(t, obj, arg);
|
if (ret)
|
return __bt(ret);
|
read_lock_nocancel(&t->lock);
|
}
|
}
|
|
read_unlock(&t->lock);
|
|
return 0;
|
}
|
|
#else /* !CONFIG_XENO_PSHARED */
|
|
static inline int store_key(struct hashobj *obj,
|
const void *key, size_t len,
|
const struct hash_operations *hops)
|
{
|
obj->key = key;
|
obj->len = len;
|
|
return 0;
|
}
|
|
static inline void drop_key(struct hashobj *obj,
|
const struct hash_operations *hops)
|
{ }
|
|
#endif /* !CONFIG_XENO_PSHARED */
|
