git.ozlabs.org Git - ccan/blob - ccan/bitmap/bitmap.c

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2
   3 #include "config.h"
   4
   5 #include <ccan/bitmap/bitmap.h>
   6
   7 #include <assert.h>
   8
   9 #define BIT_ALIGN_DOWN(n)       ((n) & ~(BITMAP_WORD_BITS - 1))
  10 #define BIT_ALIGN_UP(n)         BIT_ALIGN_DOWN((n) + BITMAP_WORD_BITS - 1)
  11
  12 void bitmap_zero_range(bitmap *bitmap, unsigned long n, unsigned long m)
  13 {
  14         unsigned long an = BIT_ALIGN_UP(n);
  15         unsigned long am = BIT_ALIGN_DOWN(m);
  16         bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
  17         bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
  18
  19         assert(m >= n);
  20
  21         if (am < an) {
  22                 BITMAP_WORD(bitmap, n) &= ~bitmap_bswap(headmask & tailmask);
  23                 return;
  24         }
  25
  26         if (an > n)
  27                 BITMAP_WORD(bitmap, n) &= ~bitmap_bswap(headmask);
  28
  29         if (am > an)
  30                 memset(&BITMAP_WORD(bitmap, an), 0,
  31                        (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
  32
  33         if (m > am)
  34                 BITMAP_WORD(bitmap, m) &= ~bitmap_bswap(tailmask);
  35 }
  36
  37 void bitmap_fill_range(bitmap *bitmap, unsigned long n, unsigned long m)
  38 {
  39         unsigned long an = BIT_ALIGN_UP(n);
  40         unsigned long am = BIT_ALIGN_DOWN(m);
  41         bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
  42         bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
  43
  44         assert(m >= n);
  45
  46         if (am < an) {
  47                 BITMAP_WORD(bitmap, n) |= bitmap_bswap(headmask & tailmask);
  48                 return;
  49         }
  50
  51         if (an > n)
  52                 BITMAP_WORD(bitmap, n) |= bitmap_bswap(headmask);
  53
  54         if (am > an)
  55                 memset(&BITMAP_WORD(bitmap, an), 0xff,
  56                        (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
  57
  58         if (m > am)
  59                 BITMAP_WORD(bitmap, m) |= bitmap_bswap(tailmask);
  60 }
  61
  62 static int bitmap_clz(bitmap_word w)
  63 {
  64 #if HAVE_BUILTIN_CLZL
  65         return __builtin_clzl(w);
  66 #else
  67         int lz = 0;
  68         bitmap_word mask = 1UL << (BITMAP_WORD_BITS - 1);
  69
  70         while (!(w & mask)) {
  71                 lz++;
  72                 mask >>= 1;
  73         }
  74
  75         return lz;
  76 #endif
  77 }
  78
  79 unsigned long bitmap_ffs(const bitmap *bitmap,
  80                          unsigned long n, unsigned long m)
  81 {
  82         unsigned long an = BIT_ALIGN_UP(n);
  83         unsigned long am = BIT_ALIGN_DOWN(m);
  84         bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
  85         bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
  86
  87         assert(m >= n);
  88
  89         if (am < an) {
  90                 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, n));
  91
  92                 w &= (headmask & tailmask);
  93
  94                 return w ? am + bitmap_clz(w) : m;
  95         }
  96
  97         if (an > n) {
  98                 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, n));
  99
 100                 w &= headmask;
 101
 102                 if (w)
 103                         return BIT_ALIGN_DOWN(n) + bitmap_clz(w);
 104         }
 105
 106         while (an < am) {
 107                 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, an));
 108
 109                 if (w)
 110                         return an + bitmap_clz(w);
 111
 112                 an += BITMAP_WORD_BITS;
 113         }
 114
 115         if (m > am) {
 116                 bitmap_word w = bitmap_bswap(BITMAP_WORD(bitmap, m));
 117
 118                 w &= tailmask;
 119
 120                 if (w)
 121                         return am + bitmap_clz(w);
 122         }
 123
 124         return m;
 125 }