that assume contiguous memory allocation show up.
#include "bitmap.h"
#include <debug.h>
#include <limits.h>
#include "bitmap.h"
#include <debug.h>
#include <limits.h>
#include <round.h>
#include <stdio.h>
#include "threads/malloc.h"
#include <round.h>
#include <stdio.h>
#include "threads/malloc.h"
\f
/* Finding set or unset bits. */
\f
/* Finding set or unset bits. */
-/* Finds and returns the starting index of the first group of CNT
+/* Finds and returns the starting index of a 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. */
consecutive bits in B at or after START that are all set to
VALUE.
If there is no such group, returns BITMAP_ERROR. */
if (cnt <= b->bit_cnt)
{
size_t last = b->bit_cnt - 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;
+ size_t middle = start + random_ulong () % (last - start + 1);
+ size_t i = middle;
+ do
+ {
+ if (!bitmap_contains (b, i, cnt, !value))
+ return i;
+ i = i != last ? i + 1 : start;
+ }
+ while (i != middle);
-/* Finds the first group of CNT consecutive bits in B at or after
+/* Finds a 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.
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.
argv = read_command_line ();
argv = parse_options (argv);
argv = read_command_line ();
argv = parse_options (argv);
+ /* Set random seed if parse_options() didn't. */
+ random_init (0);
+
/* Initialize memory system. */
palloc_init ();
malloc_init ();
/* Initialize memory system. */
palloc_init ();
malloc_init ();
- /* Set random seed if parse_options() didn't. */
- random_init (0);
-
/* Initialize interrupt handlers. */
intr_init ();
timer_init ();
/* Initialize interrupt handlers. */
intr_init ();
timer_init ();