voron

experimental ARM OS
git clone git://git.2f30.org/voron
Log | Files | Refs | README | LICENSE

hash.c (2336B)

      1 #include <kernel.h>
      2 #include <alloc.h>
      3 #include <spinlock.h>
      4 #include <hash.h>
      5 
      6 enum { CHAIN_SIZ = 32 };
      7 
      8 struct hentry {
      9 	struct {
     10 		void *data;
     11 		size_t siz;
     12 	} c[CHAIN_SIZ];
     13 };
     14 
     15 struct htable {
     16 	struct hentry *e;
     17 	struct hops *ops;
     18 	size_t siz;
     19 	spinlock_t lock;
     20 };
     21 
     22 struct htable *
     23 init_htable(struct hops *ops, size_t siz)
     24 {
     25 	struct htable *ht;
     26 	size_t i, j;
     27 
     28 	if (!ops || !ops->hash || !ops->cmp || !siz)
     29 		return NULL;
     30 
     31 	ht = kmalloc(sizeof(*ht));
     32 	if (!ht)
     33 		return NULL;
     34 	ht->e = kmalloc(siz * sizeof(*ht->e));
     35 	if (!ht->e) {
     36 		kfree(ht);
     37 		return NULL;
     38 	}
     39 	for (i = 0; i < siz; i++) {
     40 		for (j = 0; j < CHAIN_SIZ; j++) {
     41 			ht->e[i].c[j].data = NULL;
     42 			ht->e[i].c[j].siz = 0;
     43 		}
     44 	}
     45 	ht->siz = siz;
     46 	ht->ops = ops;
     47 	spinlock_init(&ht->lock);
     48 	return ht;
     49 }
     50 
     51 void
     52 kfree_htable(struct htable *ht)
     53 {
     54 	kfree(ht->e);
     55 	kfree(ht);
     56 }
     57 
     58 long
     59 search_htable(struct htable *ht, void *data, size_t siz)
     60 {
     61 	struct hentry *e;
     62 	struct hops *ops;
     63 	long i;
     64 	size_t j;
     65 
     66 	if (!ht || !data || !siz)
     67 		return -EINVAL;
     68 
     69 	spinlock_lock(&ht->lock);
     70 	ops = ht->ops;
     71 	i = ops->hash(data, siz) % ht->siz;
     72 	e = &ht->e[i];
     73 	for (j = 0; j < CHAIN_SIZ; j++) {
     74 		if (!e->c[j].data || e->c[j].siz != siz)
     75 			continue;
     76 		if (!ops->cmp(e->c[j].data, data, siz)) {
     77 			spinlock_unlock(&ht->lock);
     78 			return i;
     79 		}
     80 	}
     81 	spinlock_unlock(&ht->lock);
     82 	return -1;
     83 }
     84 
     85 long
     86 insert_htable(struct htable *ht, void *data, size_t siz)
     87 {
     88 	struct hentry *e;
     89 	struct hops *ops;
     90 	long i;
     91 	size_t j;
     92 
     93 	if (!ht || !data || !siz)
     94 		return -EINVAL;
     95 
     96 	spinlock_lock(&ht->lock);
     97 	ops = ht->ops;
     98 	i = ops->hash(data, siz) % ht->siz;
     99 	e = &ht->e[i];
    100 	for (j = 0; j < CHAIN_SIZ; j++) {
    101 		if (e->c[j].data)
    102 			continue;
    103 		e->c[j].data = data;
    104 		e->c[j].siz = siz;
    105 		spinlock_unlock(&ht->lock);
    106 		return i;
    107 	}
    108 	spinlock_unlock(&ht->lock);
    109 	return -1;
    110 }
    111 
    112 long
    113 remove_htable(struct htable *ht, void *data, size_t siz)
    114 {
    115 	struct hentry *e;
    116 	struct hops *ops;
    117 	long i;
    118 	size_t j;
    119 
    120 	if (!ht || !data || !siz)
    121 		return -EINVAL;
    122 
    123 	spinlock_lock(&ht->lock);
    124 	ops = ht->ops;
    125 	i = ops->hash(data, siz) % ht->siz;
    126 	e = &ht->e[i];
    127 	for (j = 0; j < CHAIN_SIZ; j++) {
    128 		if (!e->c[j].data || e->c[j].siz != siz)
    129 			continue;
    130 		if (!ops->cmp(e->c[j].data, data, siz)) {
    131 			e->c[j].data = NULL;
    132 			e->c[j].siz = 0;
    133 			spinlock_unlock(&ht->lock);
    134 			return i;
    135 		}
    136 	}
    137 	spinlock_unlock(&ht->lock);
    138 	return -1;
    139 }