lib/bitmap.h

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef BITMAP_H
  18 #define BITMAP_H 1
  19
  20 #include <limits.h>
  21 #include <stdlib.h>
  22 #include "util.h"
  23
  24 #define BITMAP_ULONG_BITS (sizeof(unsigned long) * CHAR_BIT)
  25
  26 static inline unsigned long *
  27 bitmap_unit__(const unsigned long *bitmap, size_t offset)
  28 {
  29     return CONST_CAST(unsigned long *, &bitmap[offset / BITMAP_ULONG_BITS]);
  30 }
  31
  32 static inline unsigned long
  33 bitmap_bit__(size_t offset)
  34 {
  35     return 1UL << (offset % BITMAP_ULONG_BITS);
  36 }
  37
  38 #define BITMAP_N_LONGS(N_BITS) DIV_ROUND_UP(N_BITS, BITMAP_ULONG_BITS)
  39
  40 static inline size_t
  41 bitmap_n_longs(size_t n_bits)
  42 {
  43     return BITMAP_N_LONGS(n_bits);
  44 }
  45
  46 static inline size_t
  47 bitmap_n_bytes(size_t n_bits)
  48 {
  49     return bitmap_n_longs(n_bits) * sizeof(unsigned long int);
  50 }
  51
  52 static inline unsigned long *
  53 bitmap_allocate(size_t n_bits)
  54 {
  55     return xzalloc(bitmap_n_bytes(n_bits));
  56 }
  57
  58 unsigned long *bitmap_allocate1(size_t n_bits);
  59
  60 static inline unsigned long *
  61 bitmap_clone(const unsigned long *bitmap, size_t n_bits)
  62 {
  63     return xmemdup(bitmap, bitmap_n_bytes(n_bits));
  64 }
  65
  66 static inline void
  67 bitmap_free(unsigned long *bitmap)
  68 {
  69     free(bitmap);
  70 }
  71
  72 static inline bool
  73 bitmap_is_set(const unsigned long *bitmap, size_t offset)
  74 {
  75     return (*bitmap_unit__(bitmap, offset) & bitmap_bit__(offset)) != 0;
  76 }
  77
  78 static inline void
  79 bitmap_set1(unsigned long *bitmap, size_t offset)
  80 {
  81     *bitmap_unit__(bitmap, offset) |= bitmap_bit__(offset);
  82 }
  83
  84 static inline void
  85 bitmap_set0(unsigned long *bitmap, size_t offset)
  86 {
  87     *bitmap_unit__(bitmap, offset) &= ~bitmap_bit__(offset);
  88 }
  89
  90 static inline void
  91 bitmap_set(unsigned long *bitmap, size_t offset, bool value)
  92 {
  93     if (value) {
  94         bitmap_set1(bitmap, offset);
  95     } else {
  96         bitmap_set0(bitmap, offset);
  97     }
  98 }
  99
 100 void bitmap_set_multiple(unsigned long *, size_t start, size_t count,
 101                          bool value);
 102 bool bitmap_equal(const unsigned long *, const unsigned long *, size_t n);
 103 size_t bitmap_scan(const unsigned long int *, bool target,
 104                    size_t start, size_t end);
 105 size_t bitmap_count1(const unsigned long *, size_t n);
 106
 107 #define BITMAP_FOR_EACH_1(IDX, SIZE, BITMAP) \
 108     for ((IDX) = bitmap_scan(BITMAP, 1, 0, SIZE); (IDX) < (SIZE);    \
 109          (IDX) = bitmap_scan(BITMAP, 1, (IDX) + 1, SIZE))
 110
 111 #endif /* bitmap.h */