Hash :
6fc5a581
Author :
Date :
2013-07-08T22:42:02
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
/*
* Copyright (C) the libgit2 contributors. All rights reserved.
*
* This file is part of libgit2, distributed under the GNU GPL v2 with
* a Linking Exception. For full terms see the included COPYING file.
*/
#ifndef INCLUDE_bitvec_h__
#define INCLUDE_bitvec_h__
#include "util.h"
/*
* This is a silly little fixed length bit vector type that will store
* vectors of 64 bits or less directly in the structure and allocate
* memory for vectors longer than 64 bits. You can use the two versions
* transparently through the API and avoid heap allocation completely when
* using a short bit vector as a result.
*/
typedef struct {
size_t length;
union {
uint8_t *ptr;
uint64_t bits;
} u;
} git_bitvec;
GIT_INLINE(int) git_bitvec_init(git_bitvec *bv, size_t capacity)
{
if (capacity < 64) {
bv->length = 0;
bv->u.bits = 0;
return 0;
}
bv->length = (capacity + 7) / 8;
bv->u.ptr = git__calloc(bv->length, 1);
return bv->u.ptr ? 0 : -1;
}
#define GIT_BITVEC_MASK_INLINE(BIT) (((uint64_t)1) << BIT)
#define GIT_BITVEC_MASK_BYTE(BIT) (((uint8_t)1) << ((BIT) & 0x07))
#define GIT_BITVEC_INDEX_BYTE(BIT) ((BIT) >> 3)
GIT_INLINE(void) git_bitvec_set(git_bitvec *bv, size_t bit, bool on)
{
if (!bv->length) {
assert(bit < 64);
if (on)
bv->u.bits |= GIT_BITVEC_MASK_INLINE(bit);
else
bv->u.bits &= ~GIT_BITVEC_MASK_INLINE(bit);
} else {
assert(bit < bv->length * 8);
if (on)
bv->u.ptr[GIT_BITVEC_INDEX_BYTE(bit)] |= GIT_BITVEC_MASK_BYTE(bit);
else
bv->u.ptr[GIT_BITVEC_INDEX_BYTE(bit)] &= ~GIT_BITVEC_MASK_BYTE(bit);
}
}
GIT_INLINE(bool) git_bitvec_get(git_bitvec *bv, size_t bit)
{
if (!bv->length) {
assert(bit < 64);
return (bv->u.bits & GIT_BITVEC_MASK_INLINE(bit)) != 0;
} else {
assert(bit < bv->length * 8);
return (bv->u.ptr[GIT_BITVEC_INDEX_BYTE(bit)] &
GIT_BITVEC_MASK_BYTE(bit)) != 0;
}
}
GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv)
{
if (!bv->length)
bv->u.bits = 0;
else
memset(bv->u.ptr, 0, bv->length);
}
GIT_INLINE(void) git_bitvec_free(git_bitvec *bv)
{
if (bv->length) {
git__free(bv->u.ptr);
memset(bv, 0, sizeof(*bv));
}
}
#endif