pintos-os.org Git - pintos-anon/blob - src/lib/bitmap.h

   1 #ifndef HEADER_BITMAP_H
   2 #define HEADER_BITMAP_H 1
   3
   4 #include <stdbool.h>
   5 #include <stddef.h>
   6
   7 /* Bitmap abstract data type. */
   8
   9 /* Element type.
  10
  11    This must be an unsigned integer type at least as wide as int.
  12
  13    Each bit represents one bit in the bitmap.
  14    If bit 0 in an element represents bit K in the bitmap,
  15    then bit 1 in the element represents bit K+1 in the bitmap,
  16    and so on. */
  17 typedef unsigned long elem_type;
  18
  19 /* From the outside, a bitmap is an array of bits.  From the
  20    inside, it's an array of elem_type (defined above) that
  21    simulates an array of bits. */
  22 struct bitmap
  23   {
  24     size_t bit_cnt;     /* Number of bits. */
  25     elem_type *bits;    /* Elements that represent bits. */
  26   };
  27
  28 bool bitmap_init (struct bitmap *, size_t bit_cnt);
  29 void bitmap_destroy (struct bitmap *);
  30
  31 size_t bitmap_size (const struct bitmap *);
  32
  33 void bitmap_set (struct bitmap *, size_t idx, bool);
  34 void bitmap_set_all (struct bitmap *, bool);
  35
  36 void bitmap_mark (struct bitmap *, size_t idx);
  37 void bitmap_reset (struct bitmap *, size_t idx);
  38 void bitmap_flip (struct bitmap *, size_t idx);
  39
  40 bool bitmap_test (const struct bitmap *, size_t idx);
  41
  42 #define BITMAP_ERROR ((size_t) -1)
  43 size_t bitmap_scan (const struct bitmap *, bool);
  44 size_t bitmap_find_and_set (struct bitmap *);
  45 size_t bitmap_find_and_clear (struct bitmap *);
  46
  47 size_t bitmap_set_cnt (const struct bitmap *);
  48 bool bitmap_clear_cnt (const struct bitmap *);
  49
  50 bool bitmap_any (const struct bitmap *);
  51 bool bitmap_none (const struct bitmap *);
  52 bool bitmap_all (const struct bitmap *);
  53
  54 #ifdef FILESYS
  55 struct file;
  56 size_t bitmap_file_size (const struct bitmap *);
  57 void bitmap_read (struct bitmap *, struct file *);
  58 void bitmap_write (const struct bitmap *, struct file *);
  59 #endif
  60
  61 void bitmap_dump (const struct bitmap *);
  62
  63 #endif /* bitmap.h */