src/bitvec.h

   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
  10 #include "common.h"
  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 {
  22                 uint64_t *words;
  23                 uint64_t bits;
  24         } u;
  25 } git_bitvec;
  26
  27 GIT_INLINE(int) git_bitvec_init(git_bitvec *bv, size_t capacity)
  28 {
  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;
  36         }
  37
  38         return 0;
  39 }
  40
  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)
  43
  44 GIT_INLINE(void) git_bitvec_set(git_bitvec *bv, size_t bit, bool on)
  45 {
  46         uint64_t *word = GIT_BITVEC_WORD(bv, bit);
  47         uint64_t mask = GIT_BITVEC_MASK(bit);
  48
  49         if (on)
  50                 *word |= mask;
  51         else
  52                 *word &= ~mask;
  53 }
  54
  55 GIT_INLINE(bool) git_bitvec_get(git_bitvec *bv, size_t bit)
  56 {
  57         uint64_t *word = GIT_BITVEC_WORD(bv, bit);
  58         return (*word & GIT_BITVEC_MASK(bit)) != 0;
  59 }
  60
  61 GIT_INLINE(void) git_bitvec_clear(git_bitvec *bv)
  62 {
  63         if (!bv->length)
  64                 bv->u.bits = 0;
  65         else
  66                 memset(bv->u.words, 0x0, bv->length * sizeof(uint64_t));
  67 }
  68
  69 GIT_INLINE(void) git_bitvec_free(git_bitvec *bv)
  70 {
  71         if (bv->length)
  72                 git__free(bv->u.words);
  73 }
  74
  75 #endif