git

1
/**
2
 * Copyright 2013, GitHub, Inc
3
 * Copyright 2009-2013, Daniel Lemire, Cliff Moon,
4
 *	David McIntosh, Robert Becho, Google Inc. and Veronika Zenz
5
 *
6
 * This program is free software; you can redistribute it and/or
7
 * modify it under the terms of the GNU General Public License
8
 * as published by the Free Software Foundation; either version 2
9
 * of the License, or (at your option) any later version.
10
 *
11
 * This program is distributed in the hope that it will be useful,
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
 * GNU General Public License for more details.
15
 *
16
 * You should have received a copy of the GNU General Public License
17
 * along with this program; if not, see <http://www.gnu.org/licenses/>.
18
 */
19
#include "git-compat-util.h"
20
#include "ewok.h"
21
#include "ewok_rlw.h"
22

23
static inline int next_word(struct rlw_iterator *it)
24
{
25
	if (it->pointer >= it->size)
26
		return 0;
27

28
	it->rlw.word = &it->buffer[it->pointer];
29
	it->pointer += rlw_get_literal_words(it->rlw.word) + 1;
30

31
	it->rlw.literal_words = rlw_get_literal_words(it->rlw.word);
32
	it->rlw.running_len = rlw_get_running_len(it->rlw.word);
33
	it->rlw.running_bit = rlw_get_run_bit(it->rlw.word);
34
	it->rlw.literal_word_offset = 0;
35

36
	return 1;
37
}
38

39
void rlwit_init(struct rlw_iterator *it, struct ewah_bitmap *from_ewah)
40
{
41
	it->buffer = from_ewah->buffer;
42
	it->size = from_ewah->buffer_size;
43
	it->pointer = 0;
44

45
	next_word(it);
46

47
	it->literal_word_start = rlwit_literal_words(it) +
48
		it->rlw.literal_word_offset;
49
}
50

51
void rlwit_discard_first_words(struct rlw_iterator *it, size_t x)
52
{
53
	while (x > 0) {
54
		size_t discard;
55

56
		if (it->rlw.running_len > x) {
57
			it->rlw.running_len -= x;
58
			return;
59
		}
60

61
		x -= it->rlw.running_len;
62
		it->rlw.running_len = 0;
63

64
		discard = (x > it->rlw.literal_words) ? it->rlw.literal_words : x;
65

66
		it->literal_word_start += discard;
67
		it->rlw.literal_words -= discard;
68
		x -= discard;
69

70
		if (x > 0 || rlwit_word_size(it) == 0) {
71
			if (!next_word(it))
72
				break;
73

74
			it->literal_word_start =
75
				rlwit_literal_words(it) + it->rlw.literal_word_offset;
76
		}
77
	}
78
}
79

80
size_t rlwit_discharge(
81
	struct rlw_iterator *it, struct ewah_bitmap *out, size_t max, int negate)
82
{
83
	size_t index = 0;
84

85
	while (index < max && rlwit_word_size(it) > 0) {
86
		size_t pd, pl = it->rlw.running_len;
87

88
		if (index + pl > max)
89
			pl = max - index;
90

91
		ewah_add_empty_words(out, it->rlw.running_bit ^ negate, pl);
92
		index += pl;
93

94
		pd = it->rlw.literal_words;
95
		if (pd + index > max)
96
			pd = max - index;
97

98
		ewah_add_dirty_words(out,
99
			it->buffer + it->literal_word_start, pd, negate);
100

101
		rlwit_discard_first_words(it, pd + pl);
102
		index += pd;
103
	}
104

105
	return index;
106
}
107