return last_bits ? ((elem_type) 1 << last_bits) - 1 : (elem_type) -1;
}
\f
+/* Creation and destruction. */
+
/* 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
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(). */
free (b);
}
}
+\f
+/* Bitmap size. */
/* Returns the number of bits in B. */
size_t
{
return b->bit_cnt;
}
+\f
+/* Setting and testing single bits. */
/* Atomically sets the bit numbered IDX in B to VALUE. */
void
bitmap_reset (b, idx);
}
-/* Sets all bits in B to VALUE. */
-void
-bitmap_set_all (struct bitmap *b, bool value)
-{
- ASSERT (b != NULL);
-
- bitmap_set_multiple (b, 0, bitmap_size (b), value);
-}
-
-/* Sets the CNT bits starting at START in B to VALUE. */
-void
-bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
-{
- size_t i;
-
- ASSERT (b != NULL);
- ASSERT (start <= b->bit_cnt);
- ASSERT (start + cnt <= b->bit_cnt);
-
- for (i = 0; i < cnt; i++)
- bitmap_set (b, start + i, value);
-}
-
/* Atomically sets the bit numbered BIT_IDX in B to true. */
void
bitmap_mark (struct bitmap *b, size_t bit_idx)
ASSERT (idx < b->bit_cnt);
return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}
+\f
+/* Setting and testing multiple bits. */
-/* 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 cnt, bool value)
+/* Sets all bits in B to VALUE. */
+void
+bitmap_set_all (struct bitmap *b, bool value)
{
- size_t i;
-
ASSERT (b != NULL);
- ASSERT (start <= b->bit_cnt);
- ASSERT (start + cnt <= b->bit_cnt);
- for (i = 0; i < cnt; i++)
- if (bitmap_test (b, start + i) == value)
- return true;
- return false;
+ bitmap_set_multiple (b, 0, bitmap_size (b), value);
}
-/* 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.
- If there is no such group, returns BITMAP_ERROR. */
-size_t
-bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
+/* Sets the CNT bits starting at START in B to VALUE. */
+void
+bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value)
{
+ size_t i;
+
ASSERT (b != NULL);
ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
- 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;
-}
-
-/* Finds the first group of CNT consecutive bits in B at or after
- 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
-bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
-{
- size_t idx = bitmap_scan (b, start, cnt, value);
- if (idx != BITMAP_ERROR)
- bitmap_set_multiple (b, idx, cnt, !value);
- return idx;
+ for (i = 0; i < cnt; i++)
+ bitmap_set (b, start + i, value);
}
/* Returns the number of bits in B between START and START + CNT,
return value_cnt;
}
+/* 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 i;
+
+ ASSERT (b != NULL);
+ ASSERT (start <= b->bit_cnt);
+ ASSERT (start + cnt <= b->bit_cnt);
+
+ 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 contains (b, start, cnt, true);
+ return bitmap_contains (b, start, cnt, true);
}
/* Returns true if no bits in B between START and START + CNT,
bool
bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
{
- return !contains (b, start, cnt, true);
+ return !bitmap_contains (b, start, cnt, true);
}
/* Returns true if every bit in B between START and START + CNT,
bool
bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
{
- return !contains (b, start, cnt, false);
+ 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.
+ If there is no such group, returns BITMAP_ERROR. */
+size_t
+bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
+{
+ ASSERT (b != NULL);
+ ASSERT (start <= b->bit_cnt);
+
+ 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;
+}
+
+/* Finds the first group of CNT consecutive bits in B at or after
+ 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
+bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
+{
+ size_t idx = bitmap_scan (b, start, cnt, value);
+ if (idx != BITMAP_ERROR)
+ bitmap_set_multiple (b, idx, cnt, !value);
+ return idx;
+}
+\f
+/* File input and output. */
#ifdef FILESYS
/* Returns the number of bytes needed to store B in a file. */
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->bit_cnt), 0);
+ 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->bit_cnt), 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
hex_dump (0, b->bits, byte_cnt (b->bit_cnt), false);
}
-/* Returns the number of bytes required to accomodate a bitmap
- with BIT_CNT bits. */
-size_t
-bitmap_needed_bytes (size_t bit_cnt)
-{
- return sizeof (struct bitmap) + byte_cnt (bit_cnt);
-}
-
-/* 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;
-}
-
projects / pintos-anon / blobdiff