dedup

data deduplication program
git clone git://git.2f30.org/dedup.git
Log | Files | Refs | README | LICENSE

cache.c (1756B)


      1 #include <sys/types.h>
      2 
      3 #include <err.h>
      4 #include <stdint.h>
      5 #include <stdlib.h>
      6 #include <string.h>
      7 
      8 #include "dedup.h"
      9 #include "tree.h"
     10 
     11 struct cache_node {
     12 	struct blk_desc desc;
     13 	RB_ENTRY(cache_node) e;
     14 };
     15 RB_HEAD(cache_head, cache_node);
     16 
     17 struct cache {
     18 	struct cache_head nodes;
     19 };
     20 
     21 static int
     22 cache_node_cmp(struct cache_node *e1, struct cache_node *e2)
     23 {
     24 	int r;
     25 
     26 	r = memcmp(e1->desc.md, e2->desc.md, sizeof(e1->desc.md));
     27 	if (r > 0)
     28 		return 1;
     29 	else if (r < 0)
     30 		return -1;
     31 	return 0;
     32 }
     33 static RB_PROTOTYPE(cache_head, cache_node, e, cache_node_cmp);
     34 static RB_GENERATE(cache_head, cache_node, e, cache_node_cmp);
     35 
     36 static struct cache_node *
     37 alloc_cache_node(struct blk_desc *desc)
     38 {
     39 	struct cache_node *node;
     40 
     41 	node = calloc(1, sizeof(*node));
     42 	if (node == NULL)
     43 		err(1, "calloc");
     44 	node->desc = *desc;
     45 	return node;
     46 }
     47 
     48 static void
     49 free_cache_node(struct cache_node *node)
     50 {
     51 	free(node);
     52 }
     53 
     54 struct cache *
     55 alloc_cache(void)
     56 {
     57 	struct cache *cache;
     58 
     59 	cache = calloc(1, sizeof(*cache));
     60 	if (cache == NULL)
     61 		err(1, "calloc");
     62 	RB_INIT(&cache->nodes);
     63 	return cache;
     64 }
     65 
     66 void
     67 free_cache(struct cache *cache)
     68 {
     69 	struct cache_node *node, *tmp;
     70 
     71 	RB_FOREACH_SAFE(node, cache_head, &cache->nodes, tmp) {
     72 		RB_REMOVE(cache_head, &cache->nodes, node);
     73 		free_cache_node(node);
     74 	}
     75 	free(cache);
     76 }
     77 
     78 void
     79 add_cache_entry(struct cache *cache, struct blk_desc *desc)
     80 {
     81 	struct cache_node *node;
     82 
     83 	node = alloc_cache_node(desc);
     84 	if (RB_INSERT(cache_head, &cache->nodes, node) != NULL)
     85 		free_cache_node(node);
     86 }
     87 
     88 int
     89 lookup_cache_entry(struct cache *cache, struct blk_desc *desc)
     90 {
     91 	struct cache_node *node, key;
     92 
     93 	key.desc = *desc;
     94 	node = RB_FIND(cache_head, &cache->nodes, &key);
     95 	if (node != NULL) {
     96 		*desc = node->desc;
     97 		return 0;
     98 	}
     99 	return -1;
    100 }