File: results-tree.h

package info (click to toggle)
duperemove 0.11.2-3
  • links: PTS, VCS
  • area: main
  • in suites: bookworm, bullseye, sid, trixie
  • size: 844 kB
  • sloc: ansic: 11,586; makefile: 110
file content (92 lines) | stat: -rw-r--r-- 2,542 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*
 * results-tree.h
 *
 * Copyright (C) 2016 SUSE.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License version 2 as published by the Free Software Foundation.
 *
 * This program 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
 * General Public License for more details.
 *
 */

#ifndef __RESULTS_TREE_
#define __RESULTS_TREE_

#include <glib.h>

#include "interval_tree.h"

struct results_tree {
	struct rb_root	root;
	unsigned int	num_dupes;
	GMutex		tree_mutex;
	unsigned long long	num_extents;
};

struct dupe_extents {
	unsigned int	de_num_dupes;
	uint64_t	de_len;
	unsigned char		de_hash[DIGEST_LEN_MAX];

	uint64_t	de_score;

	struct list_head	de_extents;
	struct rb_root		de_extents_root;

	struct rb_node		de_node;
	GMutex			de_mutex;
};

struct extent_dedupe_info;
struct extent	{
	struct dupe_extents	*e_parent;

	uint64_t	e_loff;
	struct filerec	*e_file;

	struct list_head	e_list; /* For de_extents */
	struct rb_node		e_node; /* For de_extents_root */

	/* Each file keeps a tree of it's own dupes. This makes it
	 * easier to remove overlapping duplicates. */
	struct interval_tree_node e_itnode;

#define	E_MAY_DELETE	0x01
	int			e_flags;

	/*
	 * Physical offset and length are used to figure out whether
	 * we have already deduped this extent yet.
	 */
	uint64_t		e_poff;
	uint64_t		e_plen;
	uint64_t		e_shared_bytes;
};
#define extent_len(_e)	((_e)->e_parent->de_len)
#define extent_poff(_e)	((_e)->e_poff)
#define extent_plen(_e)	((_e)->e_plen)
#define extent_shared_bytes(_e)	((_e)->e_shared_bytes)

/*
 * insert_result and insert_one_result use the object mutexes above
 * and are thread-safe.
 */
int insert_result(struct results_tree *res, unsigned char *digest,
		  struct filerec *recs[2], uint64_t startoff[2],
		  uint64_t endoff[2]);
int insert_one_result(struct results_tree *res, unsigned char *digest,
		      struct filerec *file, uint64_t startoff, uint64_t len,
		      uint64_t poff, int flags);
void remove_overlapping_extents(struct results_tree *res, struct filerec *file);

void init_results_tree(struct results_tree *res);
void free_results_tree(struct results_tree *res);
void dupe_extents_free(struct dupe_extents *dext, struct results_tree *res);

unsigned int remove_extent(struct results_tree *res, struct extent *extent);
#endif /* __RESULTS_TREE__ */