sys/compat/linuxkpi/common/include/linux/bitmap.h

   1 /*
   2  * Copyright (c) 2013-2017 Mellanox Technologies, Ltd.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice unmodified, this list of conditions, and the following
  10  *    disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  */
  28
  29 #ifndef _LINUX_BITMAP_H_
  30 #define _LINUX_BITMAP_H_
  31
  32 #include <linux/bitops.h>
  33
  34 static inline void
  35 bitmap_zero(unsigned long *addr, const unsigned int size)
  36 {
  37         memset(addr, 0, BITS_TO_LONGS(size) * sizeof(long));
  38 }
  39
  40 static inline void
  41 bitmap_fill(unsigned long *addr, const unsigned int size)
  42 {
  43         const unsigned int tail = size & (BITS_PER_LONG - 1);
  44
  45         memset(addr, 0xff, BIT_WORD(size) * sizeof(long));
  46
  47         if (tail)
  48                 addr[BIT_WORD(size)] = BITMAP_LAST_WORD_MASK(tail);
  49 }
  50
  51 static inline int
  52 bitmap_full(unsigned long *addr, const unsigned int size)
  53 {
  54         const unsigned int end = BIT_WORD(size);
  55         const unsigned int tail = size & (BITS_PER_LONG - 1);
  56         unsigned int i;
  57
  58         for (i = 0; i != end; i++) {
  59                 if (addr[i] != ~0UL)
  60                         return (0);
  61         }
  62
  63         if (tail) {
  64                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
  65
  66                 if ((addr[end] & mask) != mask)
  67                         return (0);
  68         }
  69         return (1);
  70 }
  71
  72 static inline int
  73 bitmap_empty(unsigned long *addr, const unsigned int size)
  74 {
  75         const unsigned int end = BIT_WORD(size);
  76         const unsigned int tail = size & (BITS_PER_LONG - 1);
  77         unsigned int i;
  78
  79         for (i = 0; i != end; i++) {
  80                 if (addr[i] != 0)
  81                         return (0);
  82         }
  83
  84         if (tail) {
  85                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
  86
  87                 if ((addr[end] & mask) != 0)
  88                         return (0);
  89         }
  90         return (1);
  91 }
  92
  93 static inline void
  94 bitmap_set(unsigned long *map, unsigned int start, int nr)
  95 {
  96         const unsigned int size = start + nr;
  97         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
  98         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
  99
 100         map += BIT_WORD(start);
 101
 102         while (nr - bits_to_set >= 0) {
 103                 *map |= mask_to_set;
 104                 nr -= bits_to_set;
 105                 bits_to_set = BITS_PER_LONG;
 106                 mask_to_set = ~0UL;
 107                 map++;
 108         }
 109
 110         if (nr) {
 111                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 112                 *map |= mask_to_set;
 113         }
 114 }
 115
 116 static inline void
 117 bitmap_clear(unsigned long *map, unsigned int start, int nr)
 118 {
 119         const unsigned int size = start + nr;
 120         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 121         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 122
 123         map += BIT_WORD(start);
 124
 125         while (nr - bits_to_clear >= 0) {
 126                 *map &= ~mask_to_clear;
 127                 nr -= bits_to_clear;
 128                 bits_to_clear = BITS_PER_LONG;
 129                 mask_to_clear = ~0UL;
 130                 map++;
 131         }
 132
 133         if (nr) {
 134                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 135                 *map &= ~mask_to_clear;
 136         }
 137 }
 138
 139 static inline unsigned int
 140 bitmap_find_next_zero_area_off(const unsigned long *map,
 141     const unsigned int size, unsigned int start,
 142     unsigned int nr, unsigned int align_mask,
 143     unsigned int align_offset)
 144 {
 145         unsigned int index;
 146         unsigned int end;
 147         unsigned int i;
 148
 149 retry:
 150         index = find_next_zero_bit(map, size, start);
 151
 152         index = (((index + align_offset) + align_mask) & ~align_mask) - align_offset;
 153
 154         end = index + nr;
 155         if (end > size)
 156                 return (end);
 157
 158         i = find_next_bit(map, end, index);
 159         if (i < end) {
 160                 start = i + 1;
 161                 goto retry;
 162         }
 163         return (index);
 164 }
 165
 166 static inline unsigned int
 167 bitmap_find_next_zero_area(const unsigned long *map,
 168     const unsigned int size, unsigned int start,
 169     unsigned int nr, unsigned int align_mask)
 170 {
 171         return (bitmap_find_next_zero_area_off(map, size,
 172             start, nr, align_mask, 0));
 173 }
 174
 175 static inline int
 176 bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 177 {
 178         int pos;
 179         int end;
 180
 181         for (pos = 0; (end = pos + (1 << order)) <= bits; pos = end) {
 182                 if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
 183                         continue;
 184                 linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
 185                 return (pos);
 186         }
 187         return (-ENOMEM);
 188 }
 189
 190 static inline int
 191 bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 192 {
 193         if (!linux_reg_op(bitmap, pos, order, REG_OP_ISFREE))
 194                 return (-EBUSY);
 195         linux_reg_op(bitmap, pos, order, REG_OP_ALLOC);
 196         return (0);
 197 }
 198
 199 static inline void
 200 bitmap_release_region(unsigned long *bitmap, int pos, int order)
 201 {
 202         linux_reg_op(bitmap, pos, order, REG_OP_RELEASE);
 203 }
 204
 205 static inline unsigned int
 206 bitmap_weight(unsigned long *addr, const unsigned int size)
 207 {
 208         const unsigned int end = BIT_WORD(size);
 209         const unsigned int tail = size & (BITS_PER_LONG - 1);
 210         unsigned int retval = 0;
 211         unsigned int i;
 212
 213         for (i = 0; i != end; i++)
 214                 retval += hweight_long(addr[i]);
 215
 216         if (tail) {
 217                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
 218
 219                 retval += hweight_long(addr[end] & mask);
 220         }
 221         return (retval);
 222 }
 223
 224 static inline int
 225 bitmap_equal(const unsigned long *pa,
 226     const unsigned long *pb, unsigned size)
 227 {
 228         const unsigned int end = BIT_WORD(size);
 229         const unsigned int tail = size & (BITS_PER_LONG - 1);
 230         unsigned int i;
 231
 232         for (i = 0; i != end; i++) {
 233                 if (pa[i] != pb[i])
 234                         return (0);
 235         }
 236
 237         if (tail) {
 238                 const unsigned long mask = BITMAP_LAST_WORD_MASK(tail);
 239
 240                 if ((pa[end] ^ pb[end]) & mask)
 241                         return (0);
 242         }
 243         return (1);
 244 }
 245
 246 static inline void
 247 bitmap_complement(unsigned long *dst, const unsigned long *src,
 248     const unsigned int size)
 249 {
 250         const unsigned int end = BITS_TO_LONGS(size);
 251         unsigned int i;
 252
 253         for (i = 0; i != end; i++)
 254                 dst[i] = ~src[i];
 255 }
 256
 257 static inline void
 258 bitmap_or(unsigned long *dst, const unsigned long *src1,
 259     const unsigned long *src2, const unsigned int size)
 260 {
 261         const unsigned int end = BITS_TO_LONGS(size);
 262         unsigned int i;
 263
 264         for (i = 0; i != end; i++)
 265                 dst[i] = src1[i] | src2[i];
 266 }
 267
 268 static inline void
 269 bitmap_and(unsigned long *dst, const unsigned long *src1,
 270     const unsigned long *src2, const unsigned int size)
 271 {
 272         const unsigned int end = BITS_TO_LONGS(size);
 273         unsigned int i;
 274
 275         for (i = 0; i != end; i++)
 276                 dst[i] = src1[i] & src2[i];
 277 }
 278
 279 static inline void
 280 bitmap_xor(unsigned long *dst, const unsigned long *src1,
 281     const unsigned long *src2, const unsigned int size)
 282 {
 283         const unsigned int end = BITS_TO_LONGS(size);
 284         unsigned int i;
 285
 286         for (i = 0; i != end; i++)
 287                 dst[i] = src1[i] ^ src2[i];
 288 }
 289
 290 #endif                                  /* _LINUX_BITMAP_H_ */