library/hash.h

   1 /*
   2  * 2008+ Copyright (c) Evgeniy Polyakov <zbr@ioremap.net>
   3  * All rights reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  */
  15
  16 #ifndef __EBLOB_HASH_H
  17 #define __EBLOB_HASH_H
  18
  19 #include <strings.h>
  20
  21 #include "atomic.h"
  22 #include "lock.h"
  23 #include "list.h"
  24 #include "rbtree.h"
  25
  26 struct eblob_hash_head;
  27 struct eblob_hash {
  28         unsigned int            flags;
  29
  30         struct rb_root          root;
  31         pthread_mutex_t         root_lock;
  32
  33         struct list_head        cache_top;
  34         struct list_head        cache_bottom;
  35
  36         uint64_t                cache_top_cnt;
  37         uint64_t                cache_bottom_cnt;
  38         uint64_t                max_queue_size;
  39 };
  40
  41 struct eblob_hash *eblob_hash_init(uint64_t cache_szie, int *errp);
  42 void eblob_hash_exit(struct eblob_hash *h);
  43 int eblob_hash_remove_nolock(struct eblob_hash *h, struct eblob_key *key);
  44 int eblob_hash_lookup_alloc_nolock(struct eblob_hash *h, struct eblob_key *key, void **datap, unsigned int *dsizep, int *on_diskp);
  45 int eblob_hash_lookup_alloc(struct eblob_hash *h, struct eblob_key *key, void **datap, unsigned int *dsizep, int *on_diskp);
  46 int eblob_hash_replace_nolock(struct eblob_hash *h, struct eblob_key *key, void *data, unsigned int dsize, int on_disk);
  47
  48 /* Record is cached from disk index */
  49 #define EBLOB_HASH_FLAGS_CACHE          (1<<0)
  50
  51 /* Record is placed in top queue.
  52  * It happens if it is hitted again
  53  */
  54 #define EBLOB_HASH_FLAGS_TOP_QUEUE      (1<<1)
  55
  56 struct eblob_hash_entry {
  57         struct rb_node          node;
  58         struct list_head        cache_entry;
  59
  60         unsigned int            dsize;
  61         unsigned int            flags;
  62
  63         struct eblob_key        key;
  64         unsigned char           data[0];
  65 };
  66
  67 static inline unsigned int eblob_hash_data(void *data, unsigned int size, unsigned int limit)
  68 {
  69         unsigned int i, hash = 0;
  70         unsigned char *ptr = data;
  71         unsigned char *h = (unsigned char *)&hash;
  72
  73         if (size > 4)
  74                 size = 4;
  75
  76         for (i=0; i<size; ++i)
  77                 h[size - i - 1] = ptr[i];
  78
  79         /* 33 because ffs() returns bit number starting from 1 not 0 */
  80         hash >>= 33 - ffs(limit);
  81
  82         return hash;
  83 }
  84
  85 #endif /* __EBLOB_HASH_H */