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
return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
}
\f
-/* Initializes B to be a bitmap of BIT_CNT bits
- and sets all of its bits to false.
- Returns true if success, false if memory allocation
- failed. */
+/* Creation and destruction. */
+
+/* Creates and returns a pointer to a newly allocated bitmap with room for
+ BIT_CNT (or more) bits. Returns a null pointer if memory allocation fails.
+ The caller is responsible for freeing the bitmap, with bitmap_destroy(),
+ when it is no longer needed. */
struct bitmap *
bitmap_create (size_t bit_cnt)
{
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 NULL;
}
+/* Creates and returns a bitmap with BIT_CNT bits in the
+ BLOCK_SIZE bytes of storage preallocated at BLOCK.
+ BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
+struct bitmap *
+bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size UNUSED)
+{
+ struct bitmap *b = block;
+
+ ASSERT (block_size >= bitmap_buf_size (bit_cnt));
+
+ b->bit_cnt = bit_cnt;
+ b->bits = (elem_type *) (b + 1);
+ bitmap_set_all (b, false);
+ return b;
+}
+
+/* Returns the number of bytes required to accomodate a bitmap
+ with BIT_CNT bits (for use with bitmap_create_in_buf()). */
+size_t
+bitmap_buf_size (size_t bit_cnt)
+{
+ return sizeof (struct bitmap) + byte_cnt (bit_cnt);
+}
+
/* Destroys bitmap B, freeing its storage.
- Not for use on bitmaps created by
- bitmap_create_preallocated(). */
+ Not for use on bitmaps created by bitmap_create_in_buf(). */
void
bitmap_destroy (struct bitmap *b)
{
free (b);
}
}
+\f
+/* Bitmap size. */
/* Returns the number of bits in B. */
size_t
{
return b->bit_cnt;
}
+\f
+/* Setting and testing single bits. */
-/* 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. */
+/* Atomically sets the bit numbered BIT_IDX in B to true. */
void
-bitmap_set_all (struct bitmap *b, bool value)
+bitmap_mark (struct bitmap *b, size_t bit_idx)
{
- ASSERT (b != NULL);
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
- bitmap_set_multiple (b, 0, bitmap_size (b), value);
+ /* 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");
}
-/* Sets the bits numbered START through END, exclusive, in B to
- VALUE. */
+/* Atomically sets the bit numbered BIT_IDX in B to false. */
void
-bitmap_set_multiple (struct bitmap *b, size_t start, size_t end, bool value)
+bitmap_reset (struct bitmap *b, size_t bit_idx)
{
- size_t idx;
-
- ASSERT (b != NULL);
- ASSERT (start <= end);
- ASSERT (end <= b->bit_cnt);
+ size_t idx = elem_idx (bit_idx);
+ elem_type mask = bit_mask (bit_idx);
- for (idx = start; idx < end; idx++)
- bitmap_set (b, idx, value);
+ /* 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 sets the bit numbered IDX in B to true. */
+/* 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_mark (struct bitmap *b, size_t idx)
+bitmap_flip (struct bitmap *b, size_t bit_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. */
+bool
+bitmap_test (const struct bitmap *b, size_t idx)
{
- asm ("orl %1, %0"
- : "=m" (b->bits[elem_idx (idx)])
- : "r" (bit_mask (idx)));
+ ASSERT (b != NULL);
+ ASSERT (idx < b->bit_cnt);
+ return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}
+\f
+/* Setting and testing multiple bits. */
-/* Atomically sets the bit numbered IDX in B to false. */
+/* Sets all bits in B to VALUE. */
void
-bitmap_reset (struct bitmap *b, size_t idx)
+bitmap_set_all (struct bitmap *b, bool value)
{
- asm ("andl %1, %0"
- : "=m" (b->bits[elem_idx (idx)])
- : "r" (~bit_mask (idx)));
+ ASSERT (b != NULL);
+
+ bitmap_set_multiple (b, 0, bitmap_size (b), value);
}
-/* 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. */
+/* Sets the CNT bits starting at START in B to VALUE. */
void
-bitmap_flip (struct bitmap *b, size_t idx)
+bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
{
+ size_t i;
+
ASSERT (b != NULL);
- ASSERT (idx < b->bit_cnt);
- asm ("xorl %1, %0"
- : "=m" (b->bits[elem_idx (idx)])
- : "r" (bit_mask (idx)));
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
+
+ for (i = 0; i < cnt; i++)
+ bitmap_set (b, start + i, value);
}
-/* Returns the value of the bit numbered IDX in B. */
-bool
-bitmap_test (const struct bitmap *b, size_t idx)
+/* 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 cnt, bool value)
{
+ size_t i, value_cnt;
+
ASSERT (b != NULL);
- ASSERT (idx < b->bit_cnt);
- return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_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 bit from START to END, exclusive, is set
- to VALUE. */
-static bool
-contains (const struct bitmap *b, size_t start, size_t end, bool value)
+/* Returns true if any bits in B between START and START + CNT,
+ exclusive, are set to VALUE, and false otherwise. */
+bool
+bitmap_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;
}
+/* 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 cnt)
+{
+ return bitmap_contains (b, start, cnt, true);
+}
+
+/* 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 cnt)
+{
+ return !bitmap_contains (b, start, cnt, true);
+}
+
+/* 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 cnt)
+{
+ return !bitmap_contains (b, start, cnt, false);
+}
+\f
+/* Finding set or unset bits. */
+
/* Finds and returns the starting index of the first group of CNT
consecutive bits in B at or after START that are all set to
VALUE.
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 (!bitmap_contains (b, i, cnt, !value))
+ return i;
+ }
return BITMAP_ERROR;
}
START that are all set to VALUE, flips them all to !VALUE,
and returns the index of the first bit in the group.
If there is no such group, returns BITMAP_ERROR.
+ If CNT is zero, returns 0.
Bits are set atomically, but testing bits is not atomic with
setting them. */
size_t
{
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,
- exclusive, that are set to VALUE. */
-size_t
-bitmap_count (const struct bitmap *b, size_t start, size_t end, bool value)
-{
- size_t idx, cnt;
-
- ASSERT (b != NULL);
- ASSERT (start <= end);
- ASSERT (end <= b->bit_cnt);
-
- cnt = 0;
- for (idx = start; idx < end; idx++)
- cnt += bitmap_test (b, idx) == value;
- return cnt;
-}
-
-/* Returns true if any bits in B between START and END,
- exclusive, are set to true, and false otherwise.*/
-bool
-bitmap_any (const struct bitmap *b, size_t start, size_t end)
-{
- return contains (b, start, end, true);
-}
-
-/* Returns true if no bits in B between START and END, exclusive,
- are set to true, and false otherwise.*/
-bool
-bitmap_none (const struct bitmap *b, size_t start, size_t end)
-{
- return !contains (b, start, end, true);
-}
-
-/* Returns true if every bit in B between START and END,
- exclusive, is set to true, and false otherwise. */
-bool
-bitmap_all (const struct bitmap *b, size_t start, size_t end)
-{
- return !contains (b, start, end, false);
-}
+\f
+/* File input and output. */
#ifdef FILESYS
/* Returns the number of bytes needed to store B in a file. */
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. */
-void
+/* Reads B from FILE. Returns true if successful, false
+ otherwise. */
+bool
bitmap_read (struct bitmap *b, struct file *file)
{
+ bool success = true;
if (b->bit_cnt > 0)
{
- file_read_at (file, b->bits, byte_cnt (b), 0);
- b->bits[elem_cnt (b) - 1] &= last_mask (b);
+ off_t size = byte_cnt (b->bit_cnt);
+ success = file_read_at (file, b->bits, size, 0) == size;
+ b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
}
+ return success;
}
-/* Writes FILE to B, ignoring errors. */
-void
+/* Writes B to FILE. Return true if successful, false
+ otherwise. */
+bool
bitmap_write (const struct bitmap *b, struct file *file)
{
- file_write_at (file, b->bits, byte_cnt (b), 0);
+ off_t size = byte_cnt (b->bit_cnt);
+ return file_write_at (file, b->bits, size, 0) == size;
}
#endif /* FILESYS */
+\f
+/* Debugging. */
/* Dumps the contents of B to the console as hexadecimal. */
void
bitmap_dump (const struct bitmap *b)
{
- hex_dump (0, b->bits, byte_cnt (b), false);
-}
-
-/* Returns the number of bytes required to accomodate a bitmap
- with BIT_CNT bits. */
-size_t
-bitmap_needed_bytes (size_t bit_cnt)
-{
- struct bitmap b;
- b.bit_cnt = bit_cnt;
- return byte_cnt (&b) + sizeof b;
-}
-
-/* Creates and returns a bitmap with BIT_CNT bits in the
- BLOCK_SIZE bytes of storage preallocated at BLOCK.
- BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
-struct bitmap *
-bitmap_create_preallocated (size_t bit_cnt, void *block, size_t block_size)
-{
- struct bitmap *b = block;
-
- ASSERT (block_size >= bitmap_needed_bytes (bit_cnt));
-
- b->bit_cnt = bit_cnt;
- b->bits = (elem_type *) (b + 1);
- bitmap_set_all (b, false);
- return b;
+ hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
}
projects / pintos-anon / blobdiff