pintos-os.org Git - pintos-anon/blob - grading/vm/random.diff

   1 --- bitmap.c.~1.5.~     2004-10-06 14:29:56.000000000 -0700
   2 +++ bitmap.c    2004-11-03 14:35:22.000000000 -0800
   3 @@ -1,6 +1,7 @@
   4  #include "bitmap.h"
   5  #include <debug.h>
   6  #include <limits.h>
   7 +#include <random.h>
   8  #include <round.h>
   9  #include <stdio.h>
  10  #include "threads/malloc.h"
  11 @@ -212,14 +213,25 @@ size_t
  12  bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
  13  {
  14    size_t idx, last;
  15 +  size_t n = 0, m;
  16
  17    ASSERT (b != NULL);
  18    ASSERT (start <= b->bit_cnt);
  19
  20    for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
  21      if (!contains (b, idx, idx + cnt, !value))
  22 +      n++;
  23 +  if (n == 0)
  24 +    return BITMAP_ERROR;
  25 +
  26 +  random_init (0);
  27 +  m = random_ulong () % n;
  28 +
  29 +  for (idx = start, last = b->bit_cnt - cnt; idx <= last; idx++)
  30 +    if (!contains (b, idx, idx + cnt, !value) && m-- == 0)
  31        return idx;
  32 -  return BITMAP_ERROR;
  33 +
  34 +  NOT_REACHED ();
  35  }
  36
  37  /* Finds the first group of CNT consecutive bits in B at or after