embox

1
/**
2
 * @file
3
 * @brief
4
 *
5
 * @date 09.10.12
6
 * @author Anton Bondarev
7
 * @author Ilia Vaprol
8
 */
9

10
#include <assert.h>
11
#include <errno.h>
12
#include <limits.h>
13
#include <stddef.h>
14
#include <stdlib.h>
15

16
#include <lib/libds/indexator.h>
17

18
int ind_check(struct indexator *ind, size_t idx) {
19
	assert(ind);
20

21
	if (idx == INDEX_NONE) {
22
		return -EINVAL;
23
	}
24

25
	if (!((idx >= ind->start) && (idx <= ind->end))) {
26
		return -EINVAL;
27
	}
28

29
	return 0;
30
}
31

32
int ind_get_bit(struct indexator *ind, size_t idx) {
33
	size_t word, bit;
34

35
	assert(ind != NULL);
36
	assert(idx != INDEX_NONE);
37
	assert((idx >= ind->start) && (idx <= ind->end));
38

39
	word = (idx - ind->start) / LONG_BIT;
40
	bit = (idx - ind->start) % LONG_BIT;
41

42
	assert(ind->mask != NULL);
43

44
	return ind->mask[word] & (1 << bit);
45
}
46

47
void ind_set_bit(struct indexator *ind, size_t idx) {
48
	size_t word, bit;
49

50
	assert(ind != NULL);
51
	assert(idx != INDEX_NONE);
52
	assert((idx >= ind->start) && (idx <= ind->end));
53

54
	word = (idx - ind->start) / LONG_BIT;
55
	bit = (idx - ind->start) % LONG_BIT;
56

57
	assert(ind->mask != NULL);
58
	assert(~ind->mask[word] & (1 << bit));
59

60
	ind->mask[word] |= (1 << bit);
61
}
62

63
void ind_unset_bit(struct indexator *ind, size_t idx) {
64
	size_t word, bit;
65

66
	assert(ind != NULL);
67
	assert(idx != INDEX_NONE);
68
	assert((idx >= ind->start) && (idx <= ind->end));
69

70
	word = (idx - ind->start) / LONG_BIT;
71
	bit = (idx - ind->start) % LONG_BIT;
72

73
	assert(ind->mask != NULL);
74
	assert(ind->mask[word] & (1 << bit));
75

76
	ind->mask[word] &= ~(1 << bit);
77
}
78

79
size_t ind_find_rand(struct indexator *ind) {
80
	size_t idx, capacity;
81

82
	assert(ind != NULL);
83

84
	if (ind->min == INDEX_NONE) {
85
		return INDEX_NONE;
86
	}
87

88
	capacity = ind->clamp_max - ind->clamp_min + 1;
89
	do {
90
		idx = ind->clamp_min + rand() % capacity;
91
	} while (ind_get_bit(ind, idx));
92

93
	return idx;
94
}
95

96
size_t ind_find_less(struct indexator *ind, size_t idx, size_t min,
97
    size_t none) {
98
	while (idx-- > min) {
99
		if (!ind_get_bit(ind, idx)) {
100
			return idx;
101
		}
102
	}
103

104
	return none;
105
}
106

107
size_t ind_find_more(struct indexator *ind, size_t idx, size_t max,
108
    size_t none) {
109
	while (idx++ < max) {
110
		if (!ind_get_bit(ind, idx)) {
111
			return idx;
112
		}
113
	}
114

115
	return none;
116
}
117