From: Ben Pfaff <blp@cs.stanford.edu>
Date: Thu, 2 Sep 2004 23:52:22 +0000 (+0000)
Subject: Add comments.
X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=45693e4cf682db525fc167d83bdcf7be919af12b

Add comments.
Rename bitmap_storage_size() as bitmap_file_size(), make conditional
on FILESYS.
---

diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c
index acd7123..37ea078 100644
--- a/src/filesys/filesys.c
+++ b/src/filesys/filesys.c
@@ -35,7 +35,7 @@ do_format (void)
 
   /* Allocate data sector(s) for the free map file
      and write its file header to disk. */
-  map_hdr = filehdr_allocate (&free_map, bitmap_storage_size (&free_map));
+  map_hdr = filehdr_allocate (&free_map, bitmap_file_size (&free_map));
   if (map_hdr == NULL)
     PANIC ("free map creation failed--disk is too large");
   filehdr_write (map_hdr, FREE_MAP_SECTOR);
diff --git a/src/lib/bitmap.c b/src/lib/bitmap.c
index d614c38..c5ca38a 100644
--- a/src/lib/bitmap.c
+++ b/src/lib/bitmap.c
@@ -7,30 +7,52 @@
 #ifdef FILESYS
 #include "file.h"
 #endif
-
+
+/* 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;
 }
-
+
+/* 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) 
 {
@@ -43,12 +65,7 @@ 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) 
 {
@@ -57,23 +74,26 @@ 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) 
 {
@@ -86,34 +106,42 @@ 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) 
 {
@@ -140,6 +168,10 @@ 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) 
 {
@@ -149,6 +181,10 @@ 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) 
 {
@@ -158,6 +194,7 @@ 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) 
 {
@@ -178,6 +215,8 @@ 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) 
 {
@@ -190,18 +229,23 @@ 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) 
 {
@@ -219,6 +263,14 @@ 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) 
 {
@@ -226,6 +278,7 @@ 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)
 {
@@ -233,6 +286,7 @@ 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) 
 {
diff --git a/src/lib/bitmap.h b/src/lib/bitmap.h
index 2dbf38a..ada1354 100644
--- a/src/lib/bitmap.h
+++ b/src/lib/bitmap.h
@@ -4,19 +4,31 @@
 #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);
@@ -41,6 +53,7 @@ bool bitmap_all (const struct bitmap *);
 
 #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