X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flib%2Fkernel%2Fbitmap.c;h=d14a98cf343e935a390d9fd5702980ea50640dc6;hb=4d8d667bed137a2d791e9cb7befc3cbfb3a31c09;hp=77edf2270b35435538fbbb5adeec52096403f50b;hpb=468f548e6848498767eb6ac7b55ab9bca06de462;p=pintos-anon

diff --git a/src/lib/kernel/bitmap.c b/src/lib/kernel/bitmap.c
index 77edf22..d14a98c 100644
--- a/src/lib/kernel/bitmap.c
+++ b/src/lib/kernel/bitmap.c
@@ -1,7 +1,6 @@
 #include "bitmap.h"
 #include <debug.h>
 #include <limits.h>
-#include <random.h>
 #include <round.h>
 #include <stdio.h>
 #include "threads/malloc.h"
@@ -72,10 +71,10 @@ last_mask (const struct bitmap *b)
 
 /* 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
-   failed. */
+/* 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) 
 {
@@ -119,8 +118,7 @@ bitmap_buf_size (size_t 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) 
 {
@@ -290,7 +288,7 @@ bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
 
 /* Finding set or unset bits. */
 
-/* Finds and returns the starting index of a group of CNT
+/* 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. */
@@ -303,20 +301,15 @@ bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
   if (cnt <= b->bit_cnt) 
     {
       size_t last = b->bit_cnt - cnt;
-      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);
+      size_t i;
+      for (i = start; i <= last; i++)
+        if (!bitmap_contains (b, i, cnt, !value))
+          return i; 
     }
   return BITMAP_ERROR;
 }
 
-/* Finds a group of CNT consecutive bits in B at or after
+/* 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.