#ifdef FILESYS
#include "file.h"
#endif
-
+\f
+/* Number of bits in an element. */
#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
-#define ELEM_IDX(BIT_IDX) ((BIT_IDX) / ELEM_BITS)
-#define BIT_MASK(BIT_IDX) ((elem_type) 1 << ((BIT_IDX) % ELEM_BITS))
+/* Returns the index of the element that contains the bit
+ numbered BIT_IDX. */
+static inline size_t
+elem_idx (size_t bit_idx)
+{
+ return bit_idx / ELEM_BITS;
+}
+
+/* Returns an elem_type where only the bit corresponding to
+ BIT_IDX is turned on. */
+static inline elem_type
+bit_mask (size_t bit_idx)
+{
+ return (elem_type) 1 << (bit_idx % ELEM_BITS);
+}
+
+/* Returns the number of elements required for B's bits. */
static inline size_t
elem_cnt (const struct bitmap *b)
{
return DIV_ROUND_UP (b->bit_cnt, ELEM_BITS);
}
+/* Returns the number of bytes required by B's elements. */
static inline size_t
byte_cnt (const struct bitmap *b)
{
return sizeof (elem_type) * elem_cnt (b);
}
+/* Returns a bit mask in which the bits actually used in the last
+ element of B's bits are set to 1 and the rest are set to 0. */
static inline elem_type
last_mask (const struct bitmap *b)
{
int last_bits = b->bit_cnt % ELEM_BITS;
return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
}
-
+\f
+/* Initializes B to be a bitmap of BIT_CNT bits.
+ Returns true if successfalse, false if memory allocation
+ failed. */
bool
bitmap_init (struct bitmap *b, size_t bit_cnt)
{
return true;
}
-size_t
-bitmap_storage_size (const struct bitmap *b)
-{
- return byte_cnt (b);
-}
-
+/* Destroys bitmap B, freeing its storage. */
void
bitmap_destroy (struct bitmap *b)
{
free (b->bits);
}
+/* Returns the number of bits in B. */
size_t
bitmap_size (const struct bitmap *b)
{
return b->bit_cnt;
}
+/* 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);
+ b->bits[elem_idx (idx)] |= bit_mask (idx);
else
- b->bits[ELEM_IDX (idx)] &= ~BIT_MASK (idx);
+ b->bits[elem_idx (idx)] &= ~bit_mask (idx);
}
+/* Sets all bits in B to VALUE. */
void
bitmap_set_all (struct bitmap *b, bool value)
{
b->bits[elem_cnt (b) - 1] &= last_mask (b);
}
+/* Sets the bit numbered IDX in B to true. */
void
bitmap_mark (struct bitmap *b, size_t idx)
{
bitmap_set (b, idx, true);
}
+/* Sets the bit numbered IDX in B to false. */
void
bitmap_reset (struct bitmap *b, size_t idx)
{
bitmap_set (b, idx, false);
}
+/* 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)
{
ASSERT (b != NULL);
ASSERT (idx < b->bit_cnt);
- b->bits[ELEM_IDX (idx)] ^= BIT_MASK (idx);
+ b->bits[elem_idx (idx)] ^= bit_mask (idx);
}
+/* Returns the value of the bit numbered IDX in B. */
bool
bitmap_test (const struct bitmap *b, size_t idx)
{
ASSERT (b != NULL);
ASSERT (idx < b->bit_cnt);
- return (b->bits[ELEM_IDX (idx)] & BIT_MASK (idx)) != 0;
+ return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}
+/* Returns the smallest index of a bit set to VALUE in B.
+ If no bits in B are set to VALUE, returns BITMAP_ERROR. */
size_t
bitmap_scan (const struct bitmap *b, bool value)
{
return BITMAP_ERROR;
}
+/* Finds the smallest index of a bit set to false in B,
+ sets it to true, and returns the index.
+ If no bits in B are set to false, changes no bits and
+ returns BITMAP_ERROR. */
size_t
bitmap_find_and_set (struct bitmap *b)
{
return idx;
}
+/* Finds the smallest index of a bit set to true in B,
+ sets it to false, and returns the index.
+ If no bits in B are set to true, changes no bits and
+ returns BITMAP_ERROR. */
size_t
bitmap_find_and_clear (struct bitmap *b)
{
return idx;
}
+/* Returns the number of bits in B set to true. */
size_t
bitmap_set_cnt (const struct bitmap *b)
{
return cnt;
}
+/* Returns true if any bits in B are set to true,
+ and false otherwise.*/
bool
bitmap_any (const struct bitmap *b)
{
return false;
}
+/* Returns the number of bits in B set to false. */
bool
bitmap_clear_cnt (const struct bitmap *b)
{
return b->bit_cnt - bitmap_set_cnt (b);
}
+/* Returns true if no bits in B are set to true,
+ and false otherwise.*/
bool
bitmap_none (const struct bitmap *b)
{
return !bitmap_any (b);
}
+/* Returns true if every bit in B is set to true,
+ and false otherwise. */
bool
bitmap_all (const struct bitmap *b)
{
}
#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);
+}
+
+/* Reads FILE into B, ignoring errors. */
void
bitmap_read (struct bitmap *b, struct file *file)
{
b->bits[elem_cnt (b) - 1] &= last_mask (b);
}
+/* Writes FILE to B, ignoring errors. */
void
bitmap_write (const struct bitmap *b, struct file *file)
{
}
#endif /* FILESYS */
+/* Dumps the contents of B to the console as hexadecimal. */
void
bitmap_dump (const struct bitmap *b)
{
#include <stdbool.h>
#include <stddef.h>
+/* Bitmap abstract data type. */
+
+/* Element type.
+
+ This must be an unsigned integer type at least as wide as int.
+
+ Each bit represents one bit in the bitmap.
+ If bit 0 in an element represents bit K in the bitmap,
+ then bit 1 in the element represents bit K+1 in the bitmap,
+ and so on. */
typedef unsigned long elem_type;
+/* From the outside, a bitmap is an array of bits. From the
+ inside, it's an array of elem_type (defined above) that
+ simulates an array of bits. */
struct bitmap
{
- size_t bit_cnt;
- elem_type *bits;
+ size_t bit_cnt; /* Number of bits. */
+ elem_type *bits; /* Elements that represent bits. */
};
bool bitmap_init (struct bitmap *, size_t bit_cnt);
void bitmap_destroy (struct bitmap *);
size_t bitmap_size (const struct bitmap *);
-size_t bitmap_storage_size (const struct bitmap *);
void bitmap_set (struct bitmap *, size_t idx, bool);
void bitmap_set_all (struct bitmap *, bool);
#ifdef FILESYS
struct file;
+size_t bitmap_file_size (const struct bitmap *);
void bitmap_read (struct bitmap *, struct file *);
void bitmap_write (const struct bitmap *, struct file *);
#endif
projects / pintos-anon / commitdiff