return (elem_type) 1 << (bit_idx % ELEM_BITS);
}
-/* Returns the number of elements required for B's bits. */
+/* Returns the number of elements required for BIT_CNT bits. */
static inline size_t
-elem_cnt (const struct bitmap *b)
+elem_cnt (size_t bit_cnt)
{
- return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
+ return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
}
-/* Returns the number of bytes required by B's elements. */
+/* Returns the number of bytes required for BIT_CNT bits. */
static inline size_t
-byte_cnt (const struct bitmap *b)
+byte_cnt (size_t bit_cnt)
{
- return sizeof (elem_type) * elem_cnt (b);
+ return sizeof (elem_type) * elem_cnt (bit_cnt);
}
/* Returns a bit mask in which the bits actually used in the last
if (b != NULL)
{
b->bit_cnt = bit_cnt;
- b->bits = malloc (byte_cnt (b));
+ b->bits = malloc (byte_cnt (bit_cnt));
if (b->bits != NULL || bit_cnt == 0)
{
bitmap_set_all (b, false);
return b->bit_cnt;
}
-/* Sets the bit numbered IDX in B to VALUE. */
+/* Atomically sets the bit numbered IDX in B to VALUE. */
void
bitmap_set (struct bitmap *b, size_t idx, bool value)
{
ASSERT (b != NULL);
ASSERT (idx < b->bit_cnt);
if (value)
- b->bits[elem_idx (idx)] |= bit_mask (idx);
+ bitmap_mark (b, idx);
else
- b->bits[elem_idx (idx)] &= ~bit_mask (idx);
+ bitmap_reset (b, idx);
}
/* Sets all bits in B to VALUE. */
bitmap_set_multiple (b, 0, bitmap_size (b), value);
}
-/* Sets the bits numbered START through END, exclusive, in B to
- VALUE. */
+/* Sets the CNT bits starting at START in B to VALUE. */
void
-bitmap_set_multiple (struct bitmap *b, size_t start, size_t end, bool value)
+bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
{
- size_t idx;
+ size_t i;
ASSERT (b != NULL);
- ASSERT (start <= end);
- ASSERT (end <= b->bit_cnt);
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
- for (idx = start; idx < end; idx++)
- bitmap_set (b, idx, value);
+ for (i = 0; i < cnt; i++)
+ bitmap_set (b, start + i, value);
}
-/* Atomically sets the bit numbered IDX in B to true. */
+/* Atomically sets the bit numbered BIT_IDX in B to true. */
void
-bitmap_mark (struct bitmap *b, size_t idx)
+bitmap_mark (struct bitmap *b, size_t bit_idx)
{
- asm ("orl %1, %0"
- : "=m" (b->bits[elem_idx (idx)])
- : "r" (bit_mask (idx)));
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
+
+ /* This is equivalent to `b->bits[idx] |= mask' except that it
+ is guaranteed to be atomic on a uniprocessor machine. See
+ the description of the OR instruction in [IA32-v2b]. */
+ asm ("orl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
-/* Atomically sets the bit numbered IDX in B to false. */
+/* Atomically sets the bit numbered BIT_IDX in B to false. */
void
-bitmap_reset (struct bitmap *b, size_t idx)
+bitmap_reset (struct bitmap *b, size_t bit_idx)
{
- asm ("andl %1, %0"
- : "=m" (b->bits[elem_idx (idx)])
- : "r" (~bit_mask (idx)));
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
+
+ /* This is equivalent to `b->bits[idx] &= ~mask' except that it
+ is guaranteed to be atomic on a uniprocessor machine. See
+ the description of the AND instruction in [IA32-v2a]. */
+ asm ("andl %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
}
/* Atomically toggles the bit numbered IDX in B;
that is, if it is true, makes it false,
and if it is false, makes it true. */
void
-bitmap_flip (struct bitmap *b, size_t idx)
+bitmap_flip (struct bitmap *b, size_t bit_idx)
{
- ASSERT (b != NULL);
- ASSERT (idx < b->bit_cnt);
- asm ("xorl %1, %0"
- : "=m" (b->bits[elem_idx (idx)])
- : "r" (bit_mask (idx)));
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
+
+ /* This is equivalent to `b->bits[idx] ^= mask' except that it
+ is guaranteed to be atomic on a uniprocessor machine. See
+ the description of the XOR instruction in [IA32-v2b]. */
+ asm ("xorl %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
/* Returns the value of the bit numbered IDX in B. */
return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}
-/* Returns true if any bit from START to END, exclusive, is set
+/* Returns true if any of the CNT bits starting at START is set
to VALUE. */
static bool
-contains (const struct bitmap *b, size_t start, size_t end, bool value)
+contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
- size_t idx;
+ size_t i;
ASSERT (b != NULL);
- ASSERT (start <= end);
- ASSERT (end <= b->bit_cnt);
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
- for (idx = start; idx < end; idx++)
- if (bitmap_test (b, idx) == value)
+ for (i = 0; i < cnt; i++)
+ if (bitmap_test (b, start + i) == value)
return true;
return false;
}
size_t
bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
- size_t idx, last;
-
ASSERT (b != NULL);
ASSERT (start <= b->bit_cnt);
- if (cnt <= b->bit_cnt)
- for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
- if (!contains (b, idx, idx + cnt, !value))
- return idx;
+ if (cnt <= b->bit_cnt)
+ {
+ size_t last = b->bit_cnt - cnt;
+ size_t i;
+ for (i = start; i <= last; i++)
+ if (!contains (b, i, cnt, !value))
+ return i;
+ }
return BITMAP_ERROR;
}
{
size_t idx = bitmap_scan (b, start, cnt, value);
if (idx != BITMAP_ERROR)
- bitmap_set_multiple (b, idx, idx + cnt, !value);
+ bitmap_set_multiple (b, idx, cnt, !value);
return idx;
}
-/* Returns the number of bits in B between START and END,
+/* Returns the number of bits in B between START and START + CNT,
exclusive, that are set to VALUE. */
size_t
-bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value)
+bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
- size_t idx, cnt;
+ size_t i, value_cnt;
ASSERT (b != NULL);
- ASSERT (start <= end);
- ASSERT (end <= b->bit_cnt);
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
- cnt = 0;
- for (idx = start; idx < end; idx++)
- cnt += bitmap_test (b, idx) == value;
- return cnt;
+ value_cnt = 0;
+ for (i = 0; i < cnt; i++)
+ if (bitmap_test (b, start + i) == value)
+ value_cnt++;
+ return value_cnt;
}
-/* Returns true if any bits in B between START and END,
+/* Returns true if any bits in B between START and START + CNT,
exclusive, are set to true, and false otherwise.*/
bool
-bitmap_any (const struct bitmap *b, size_t start, size_t end)
+bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
{
- return contains (b, start, end, true);
+ return contains (b, start, cnt, true);
}
-/* Returns true if no bits in B between START and END, exclusive,
- are set to true, and false otherwise.*/
+/* Returns true if no bits in B between START and START + CNT,
+ exclusive, are set to true, and false otherwise.*/
bool
-bitmap_none (const struct bitmap *b, size_t start, size_t end)
+bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
{
- return !contains (b, start, end, true);
+ return !contains (b, start, cnt, true);
}
-/* Returns true if every bit in B between START and END,
+/* Returns true if every bit in B between START and START + CNT,
exclusive, is set to true, and false otherwise. */
bool
-bitmap_all (const struct bitmap *b, size_t start, size_t end)
+bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
{
- return !contains (b, start, end, false);
+ return !contains (b, start, cnt, false);
}
#ifdef FILESYS
size_t
bitmap_file_size (const struct bitmap *b)
{
- return byte_cnt (b);
+ return byte_cnt (b->bit_cnt);
}
/* Reads FILE into B, ignoring errors. */
{
if (b->bit_cnt > 0)
{
- file_read_at (file, b->bits, byte_cnt (b), 0);
- b->bits[elem_cnt (b) - 1] &= last_mask (b);
+ file_read_at (file, b->bits, byte_cnt (b->bit_cnt), 0);
+ b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
}
}
void
bitmap_write (const struct bitmap *b, struct file *file)
{
- file_write_at (file, b->bits, byte_cnt (b), 0);
+ file_write_at (file, b->bits, byte_cnt (b->bit_cnt), 0);
}
#endif /* FILESYS */
void
bitmap_dump (const struct bitmap *b)
{
- hex_dump (0, b->bits, byte_cnt (b), false);
+ hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
}
/* Returns the number of bytes required to accomodate a bitmap
size_t
bitmap_needed_bytes (size_t bit_cnt)
{
- struct bitmap b;
- b.bit_cnt = bit_cnt;
- return byte_cnt (&b) + sizeof b;
+ return sizeof (struct bitmap) + byte_cnt (bit_cnt);
}
/* Creates and returns a bitmap with BIT_CNT bits in the
projects / pintos-anon / blobdiff