]>
Commit | Line | Data |
---|---|---|
6fc5a581 RB |
1 | /* |
2 | * Copyright (C) the libgit2 contributors. All rights reserved. | |
3 | * | |
4 | * This file is part of libgit2, distributed under the GNU GPL v2 with | |
5 | * a Linking Exception. For full terms see the included COPYING file. | |
6 | */ | |
7 | #ifndef INCLUDE_bitvec_h__ | |
8 | #define INCLUDE_bitvec_h__ | |
9 | ||
72556cc6 | 10 | #include "common.h" |
6fc5a581 RB |
11 | |
12 | /* | |
13 | * This is a silly little fixed length bit vector type that will store | |
14 | * vectors of 64 bits or less directly in the structure and allocate | |
15 | * memory for vectors longer than 64 bits. You can use the two versions | |
16 | * transparently through the API and avoid heap allocation completely when | |
17 | * using a short bit vector as a result. | |
18 | */ | |
19 | typedef struct { | |
20 | size_t length; | |
21 | union { | |
406dd556 | 22 | uint64_t *words; |
6fc5a581 RB |
23 | uint64_t bits; |
24 | } u; | |
25 | } git_bitvec; | |
26 | ||
27 | GIT_INLINE(int) git_bitvec_init(git_bitvec *bv, size_t capacity) | |
28 | { | |
406dd556 VM |
29 | memset(bv, 0x0, sizeof(*bv)); |
30 | ||
31 | if (capacity >= 64) { | |
32 | bv->length = (capacity / 64) + 1; | |
33 | bv->u.words = git__calloc(bv->length, sizeof(uint64_t)); | |
34 | if (!bv->u.words) | |
35 | return -1; | |
6fc5a581 RB |
36 | } |
37 | ||
406dd556 | 38 | return 0; |
6fc5a581 RB |
39 | } |
40 | ||
406dd556 VM |
41 | #define GIT_BITVEC_MASK(BIT) ((uint64_t)1 << (BIT % 64)) |
42 | #define GIT_BITVEC_WORD(BV, BIT) (BV->length ? &BV->u.words[BIT / 64] : &BV->u.bits) | |
6fc5a581 RB |
43 | |
44 | GIT_INLINE(void) git_bitvec_set(git_bitvec *bv, size_t bit, bool on) | |
45 | { | |
406dd556 VM |
46 | uint64_t *word = GIT_BITVEC_WORD(bv, bit); |
47 | uint64_t mask = GIT_BITVEC_MASK(bit); | |
6fc5a581 | 48 | |
406dd556 VM |
49 | if (on) |
50 | *word |= mask; | |
51 | else | |
52 | *word &= ~mask; | |
6fc5a581 RB |
53 | } |
54 | ||
55 | GIT_INLINE(bool) git_bitvec_get(git_bitvec *bv, size_t bit) | |
56 | { | |
406dd556 VM |
57 | uint64_t *word = GIT_BITVEC_WORD(bv, bit); |
58 | return (*word & GIT_BITVEC_MASK(bit)) != 0; | |
6fc5a581 RB |
59 | } |
60 | ||
61 | GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv) | |
62 | { | |
63 | if (!bv->length) | |
64 | bv->u.bits = 0; | |
65 | else | |
406dd556 | 66 | memset(bv->u.words, 0x0, bv->length * sizeof(uint64_t)); |
6fc5a581 RB |
67 | } |
68 | ||
69 | GIT_INLINE(void) git_bitvec_free(git_bitvec *bv) | |
70 | { | |
406dd556 VM |
71 | if (bv->length) |
72 | git__free(bv->u.words); | |
6fc5a581 RB |
73 | } |
74 | ||
75 | #endif |