bitvec.h 1.72 KB
Newer Older
Russell Belfer committed
1 2 3 4 5 6 7 8 9
/*
 * 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__

Russell Belfer committed
10
#include "common.h"
Russell Belfer committed
11 12 13 14 15 16 17 18 19 20 21

/*
 * 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 {
22
		uint64_t *words;
Russell Belfer committed
23 24 25 26 27 28
		uint64_t bits;
	} u;
} git_bitvec;

GIT_INLINE(int) git_bitvec_init(git_bitvec *bv, size_t capacity)
{
29 30 31 32 33 34 35
	memset(bv, 0x0, sizeof(*bv));

	if (capacity >= 64) {
		bv->length = (capacity / 64) + 1;
		bv->u.words = git__calloc(bv->length, sizeof(uint64_t));
		if (!bv->u.words)
			return -1;
Russell Belfer committed
36 37
	}

38
	return 0;
Russell Belfer committed
39 40
}

41 42
#define GIT_BITVEC_MASK(BIT) ((uint64_t)1 << (BIT % 64))
#define GIT_BITVEC_WORD(BV, BIT) (BV->length ? &BV->u.words[BIT / 64] : &BV->u.bits)
Russell Belfer committed
43 44 45

GIT_INLINE(void) git_bitvec_set(git_bitvec *bv, size_t bit, bool on)
{
46 47
	uint64_t *word = GIT_BITVEC_WORD(bv, bit);
	uint64_t mask = GIT_BITVEC_MASK(bit);
Russell Belfer committed
48

49 50 51 52
	if (on)
		*word |= mask;
	else
		*word &= ~mask;
Russell Belfer committed
53 54 55 56
}

GIT_INLINE(bool) git_bitvec_get(git_bitvec *bv, size_t bit)
{
57 58
	uint64_t *word = GIT_BITVEC_WORD(bv, bit);
	return (*word & GIT_BITVEC_MASK(bit)) != 0;
Russell Belfer committed
59 60 61 62 63 64 65
}

GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv)
{
	if (!bv->length)
		bv->u.bits = 0;
	else
66
		memset(bv->u.words, 0x0, bv->length * sizeof(uint64_t));
Russell Belfer committed
67 68 69 70
}

GIT_INLINE(void) git_bitvec_free(git_bitvec *bv)
{
71 72
	if (bv->length)
		git__free(bv->u.words);
Russell Belfer committed
73 74 75
}

#endif