#ifndef __LIB_ROUND_H
#define __LIB_ROUND_H
/*proj0-2*/
/* Yields X rounded up to the nearest multiple of STEP.
For X >= 0, STEP >= 1 only. */
#define ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP) * (STEP))
/* Yields X divided by STEP, rounded up.
For X >= 0, STEP >= 1 only. */
#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP))
/* Yields X rounded down to the nearest multiple of STEP.
For X >= 0, STEP >= 1 only. */
#define ROUND_DOWN(X, STEP) ((X) / (STEP) * (STEP))
/* There is no DIV_ROUND_DOWN. It would be simply X / STEP. */
#endif /* round.h */
#ifndef __LIB_KERNEL_LIST_H
#define __LIB_KERNEL_LIST_H
/* Doubly linked list.
This implementation of a doubly linked list does not require
use of dynamically allocated memory. Instead, each structure
that is a potential list element must embed a struct list_elem
member. All of the list functions operate on these `struct
list_elem's. The list_entry macro allows conversion from a
struct list_elem back to a structure object that contains it.
For example, suppose there is a needed for a list of `struct
foo'. `struct foo' should contain a `struct list_elem'
member, like so:
struct foo
{
struct list_elem elem;
int bar;
...other members...
};
Then a list of `struct foo' can be be declared and initialized
like so:
struct list foo_list;
list_init (&foo_list);
Iteration is a typical situation where it is necessary to
convert from a struct list_elem back to its enclosing
structure. Here's an example using foo_list:
struct list_elem *e;
for (e = list_begin (&foo_list); e != list_end (&foo_list);
e = list_next (e))
{
struct foo *f = list_entry (e, struct foo, elem);
...do something with f...
}
You can find real examples of list usage throughout the
source; for example, malloc.c, palloc.c, and thread.c in the
threads directory all use lists.
The interface for this list is inspired by the list<> template
in the C++ STL. If you're familiar with list<>, you should
find this easy to use. However, it should be emphasized that
these lists do *no* type checking and can't do much other
correctness checking. If you screw up, it will bite you.
Glossary of list terms:
- "front": The first element in a list. Undefined in an
empty list. Returned by list_front().
- "back": The last element in a list. Undefined in an empty
list. Returned by list_back().
- "tail": The element figuratively just after the last
element of a list. Well defined even in an empty list.
Returned by list_end(). Used as the end sentinel for an
iteration from front to back.
- "beginning": In a non-empty list, the front. In an empty
list, the tail. Returned by list_begin(). Used as the
starting point for an iteration from front to back.
- "head": The element figuratively just before the first
element of a list. Well defined even in an empty list.
Returned by list_rend(). Used as the end sentinel for an
iteration from back to front.
- "reverse beginning": In a non-empty list, the back. In an
empty list, the head. Returned by list_rbegin(). Used as
the starting point for an iteration from back to front.
- "interior element": An element that is not the head or
tail, that is, a real list element. An empty list does
not have any interior elements.
*/
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
/* List element. */
struct list_elem
{
struct list_elem* prev; /* Previous list element. */
struct list_elem* next; /* Next list element. */
};
/* List. */
struct list
{
struct list_elem head; /* List head. */
struct list_elem tail; /* List tail. */
};
struct list_item
{
struct list_elem elem;
int data;
};
/* Converts pointer to list element LIST_ELEM into a pointer to
the structure that LIST_ELEM is embedded inside. Supply the
name of the outer structure STRUCT and the member name MEMBER
of the list element. See the big comment at the top of the
file for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \
- offsetof (STRUCT, MEMBER.next)))
void list_init(struct list*);
/* List traversal. */
struct list_elem* list_begin(struct list*);
struct list_elem* list_next(struct list_elem*);
struct list_elem* list_end(struct list*);
void list_swap(struct list_elem* a, struct list_elem* b);
struct list_elem* list_rbegin(struct list*);
struct list_elem* list_prev(struct list_elem*);
struct list_elem* list_rend(struct list*);
struct list_elem* list_head(struct list*);
struct list_elem* list_tail(struct list*);
/* List insertion. */
void list_insert(struct list_elem*, struct list_elem*);
void list_splice(struct list_elem* before,
struct list_elem* first, struct list_elem* last);
void list_push_front(struct list*, struct list_elem*);
void list_push_back(struct list*, struct list_elem*);
/* List removal. */
struct list_elem* list_remove(struct list_elem*);
struct list_elem* list_pop_front(struct list*);
struct list_elem* list_pop_back(struct list*);
/* List elements. */
struct list_elem* list_front(struct list*);
struct list_elem* list_back(struct list*);
void list_shuffle(struct list* list);
/* List properties. */
size_t list_size(struct list*);
bool list_empty(struct list*);
/* Miscellaneous. */
void list_reverse(struct list*);
/* Compares the value of two list elements A and B, given
auxiliary data AUX. Returns true if A is less than B, or
false if A is greater than or equal to B. */
typedef bool list_less_func(const struct list_elem* a,
const struct list_elem* b,
void* aux);
/* Operations on lists with ordered elements. */
void list_sort(struct list*,
list_less_func*, void* aux);
void list_insert_ordered(struct list*, struct list_elem*,
list_less_func*, void* aux);
void list_unique(struct list*, struct list* duplicates,
list_less_func*, void* aux);
/* Max and min. */
struct list_elem* list_max(struct list*, list_less_func*, void* aux);
struct list_elem* list_min(struct list*, list_less_func*, void* aux);
#endif /* lib/kernel/list.h */
#ifndef __LIB_LIMITS_H
#define __LIB_LIMITS_H
/*proj0-2*/
#define CHAR_BIT 8
#define SCHAR_MAX 127
#define SCHAR_MIN (-SCHAR_MAX - 1)
#define UCHAR_MAX 255
#ifdef __CHAR_UNSIGNED__
#define CHAR_MIN 0
#define CHAR_MAX UCHAR_MAX
#else
#define CHAR_MIN SCHAR_MIN
#define CHAR_MAX SCHAR_MAX
#endif
#define SHRT_MAX 32767
#define SHRT_MIN (-SHRT_MAX - 1)
#define USHRT_MAX 65535
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
#define UINT_MAX 4294967295U
#define LONG_MAX 2147483647L
#define LONG_MIN (-LONG_MAX - 1)
#define ULONG_MAX 4294967295UL
#define LLONG_MAX 9223372036854775807LL
#define LLONG_MIN (-LLONG_MAX - 1)
#define ULLONG_MAX 18446744073709551615ULL
#endif /* lib/limits.h */
#ifndef __HEX_DUMP_H
#define __HEX_DUMP_H
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>
void hex_dump (uintptr_t ofs, const void *buf__, size_t size, bool ascii);
#endif /* hex_dump.h */
#ifndef __LIB_KERNEL_HASH_H
#define __LIB_KERNEL_HASH_H
/* Hash table.
This data structure is thoroughly documented in the Tour of
Pintos for Project 3.
This is a standard hash table with chaining. To locate an
element in the table, we compute a hash function over the
element's data and use that as an index into an array of
doubly linked lists, then linearly search the list.
The chain lists do not use dynamic allocation. Instead, each
structure that can potentially be in a hash must embed a
struct hash_elem member. All of the hash functions operate on
these `struct hash_elem's. The hash_entry macro allows
conversion from a struct hash_elem back to a structure object
that contains it. This is the same technique used in the
linked list implementation. Refer to lib/kernel/list.h for a
detailed explanation. */
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "list.h"
/* Hash element. */
struct hash_elem
{
struct list_elem list_elem;
};
/* Converts pointer to hash element HASH_ELEM into a pointer to
the structure that HASH_ELEM is embedded inside. Supply the
name of the outer structure STRUCT and the member name MEMBER
of the hash element. See the big comment at the top of the
file for an example. */
#define hash_entry(HASH_ELEM, STRUCT, MEMBER) \
((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem \
- offsetof (STRUCT, MEMBER.list_elem)))
/* Computes and returns the hash value for hash element E, given
auxiliary data AUX. */
typedef unsigned hash_hash_func(const struct hash_elem* e, void* aux);
/* Compares the value of two hash elements A and B, given
auxiliary data AUX. Returns true if A is less than B, or
false if A is greater than or equal to B. */
typedef bool hash_less_func(const struct hash_elem* a,
const struct hash_elem* b,
void* aux);
/* Performs some operation on hash element E, given auxiliary
data AUX. */
typedef void hash_action_func(struct hash_elem* e, void* aux);
/* Hash table. */
struct hash
{
size_t elem_cnt; /* Number of elements in table. */
size_t bucket_cnt; /* Number of buckets, a power of 2. */
struct list* buckets; /* Array of `bucket_cnt' lists. */
hash_hash_func* hash; /* Hash function. */
hash_less_func* less; /* Comparison function. */
void* aux; /* Auxiliary data for `hash' and `less'. */
};
/* A hash table iterator. */
struct hash_iterator
{
struct hash* hash; /* The hash table. */
struct list* bucket; /* Current bucket. */
struct hash_elem* elem; /* Current hash element in current bucket. */
};
/* Basic life cycle. */
bool hash_init(struct hash*, hash_hash_func*, hash_less_func*, void* aux);
void hash_clear(struct hash*, hash_action_func*);
void hash_destroy(struct hash*, hash_action_func*);
/* Search, insertion, deletion. */
struct hash_elem* hash_insert(struct hash*, struct hash_elem*);
struct hash_elem* hash_replace(struct hash*, struct hash_elem*);
struct hash_elem* hash_find(struct hash*, struct hash_elem*);
struct hash_elem* hash_delete(struct hash*, struct hash_elem*);
/* Iteration. */
void hash_apply(struct hash*, hash_action_func*);
void hash_first(struct hash_iterator*, struct hash*);
struct hash_elem* hash_next(struct hash_iterator*);
struct hash_elem* hash_cur(struct hash_iterator*);
/* Information. */
size_t hash_size(struct hash*);
bool hash_empty(struct hash*);
/* Sample hash functions. */
unsigned hash_bytes(const void*, size_t);
unsigned hash_string(const char*);
unsigned hash_int(int);
unsigned hash_int_2(int);
#endif /* lib/kernel/hash.h */
#ifndef __LIB_KERNEL_BITMAP_H
#define __LIB_KERNEL_BITMAP_H
#include <stdbool.h>
#include <stddef.h>
#include <inttypes.h>
/* Bitmap abstract data type. */
size_t bitnum(struct bitmap*);
/* Creation and destruction. */
struct bitmap* bitmap_create(size_t bit_cnt);
struct bitmap* bitmap_create_in_buf(size_t bit_cnt, void*, size_t byte_cnt);
size_t bitmap_buf_size(size_t bit_cnt);
void bitmap_destroy(struct bitmap*);
/* Bitmap size. */
size_t bitmap_size(const struct bitmap*);
/* Setting and testing single bits. */
void bitmap_set(struct bitmap*, size_t idx, bool);
void bitmap_mark(struct bitmap*, size_t idx);
void bitmap_reset(struct bitmap*, size_t idx);
void bitmap_flip(struct bitmap*, size_t idx);
bool bitmap_test(const struct bitmap*, size_t idx);
/* Setting and testing multiple bits. */
void bitmap_set_all(struct bitmap*, bool);
void bitmap_set_multiple(struct bitmap*, size_t start, size_t cnt, bool);
size_t bitmap_count(const struct bitmap*, size_t start, size_t cnt, bool);
bool bitmap_contains(const struct bitmap*, size_t start, size_t cnt, bool);
bool bitmap_any(const struct bitmap*, size_t start, size_t cnt);
bool bitmap_none(const struct bitmap*, size_t start, size_t cnt);
bool bitmap_all(const struct bitmap*, size_t start, size_t cnt);
struct bitmap* bitmap_expand(struct bitmap*, int size);
/* Finding set or unset bits. */
#define BITMAP_ERROR SIZE_MAX
size_t bitmap_scan(const struct bitmap*, size_t start, size_t cnt, bool);
size_t bitmap_scan_and_flip(struct bitmap*, size_t start, size_t cnt, bool);
/* File input and output. */
#ifdef FILESYS
struct file;
size_t bitmap_file_size(const struct bitmap*);
bool bitmap_read(struct bitmap*, struct file*);
bool bitmap_write(const struct bitmap*, struct file*);
#endif
/* Debugging. */
void bitmap_dump(const struct bitmap*);
#endif /* lib/kernel/bitmap.h */
#include<stdio.h>
#include<math.h>
#include <time.h>
#include <assert.h>
#include <Windows.h>
#define CUDA_CALL(x) { const cudaError_t a = (x); if(a != cudaSuccess) { printf("\nCuda Error: %s (err_num=%d) at line:%d\n", cudaGetErrorString(a), a, __LINE__); cudaDeviceReset(); assert(0);}}
typedef float TIMER_T;
#define USE_CPU_TIMER 1
#define USE_GPU_TIMER 1
#if USE_CPU_TIMER == 1
__int64 start, freq, end;
#define CHECK_TIME_START { QueryPerformanceFrequency((LARGE_INTEGER*)&freq); QueryPerformanceCounter((LARGE_INTEGER*)&start); }
#define CHECK_TIME_END(a) { QueryPerformanceCounter((LARGE_INTEGER*)&end); a = (float)((float)(end - start) / (freq / 1000.0f)); }
#else
#define CHECK_TIME_START
#define CHECK_TIME_END(a)
#endif
#define N 20
#define BLOCK_SIZE 4
float* A, * B, * C;
float* X0, * X1, * FX0, * FX1;
void find_roots_CPU(float* A, float* B, float* C,
float* X0, float* X1, float* FX0, float* FX1, int n) {
int i;
float a, b, c, d, x0, x1, tmp;
for (i = 0; i < n; i++) {
a = A[i]; b = B[i]; c = C[i];
d = sqrtf(b * b - 4.0f * a * c);
tmp = 1.0f / (2.0f * a);
X0[i] = x0 = (-b - d) * tmp;
X1[i] = x1 = (-b + d) * tmp;
FX0[i] = (a * x0 + b) * x0 + c;
FX1[i] = (a * x1 + b) * x1 + c;
}
}
int main()
{
A = new float[20]; B = new float[20]; C = new float[20];
X0 = new float[20]; X1 = new float[20]; FX0 = new float[20]; FX1 = new float[20];
float a, b, c;
srand((unsigned)time(NULL));
for (int i = 0; i < 20; i++) {
a = ((float)rand() / RAND_MAX) * 10.0f;
b = ((float)rand() / RAND_MAX) * 10.0f;
c = ((float)rand() / RAND_MAX) * 10.0f;
if (b * b - 4 * a * c >= 0) {
A[i] = a; B[i] = b; C[i] = c;
}
else
i--;
}
find_roots_CPU(A, B, C, X0, X1, FX0, FX1, N);
return 0;
}
#include "list.h"
#include <assert.h> // Instead of #include "../debug.h"
#include <stdlib.h>
#include <time.h>
#define ASSERT(CONDITION) assert(CONDITION) // patched for proj0-2
/* Our doubly linked lists have two header elements: the "head"
just before the first element and the "tail" just after the
last element. The `prev' link of the front header is null, as
is the `next' link of the back header. Their other two links
point toward each other via the interior elements of the list.
An empty list looks like this:
+------+ +------+
<---| head |<--->| tail |--->
+------+ +------+
A list with two elements in it looks like this:
+------+ +-------+ +-------+ +------+
<---| head |<--->| 1 |<--->| 2 |<--->| tail |<--->
+------+ +-------+ +-------+ +------+
The symmetry of this arrangement eliminates lots of special
cases in list processing. For example, take a look at
list_remove(): it takes only two pointer assignments and no
conditionals. That's a lot simpler than the code would be
without header elements.
(Because only one of the pointers in each header element is used,
we could in fact combine them into a single header element
without sacrificing this simplicity. But using two separate
elements allows us to do a little bit of checking on some
operations, which can be valuable.) */
static bool is_sorted(struct list_elem* a, struct list_elem* b,
list_less_func* less, void* aux);// Remove KERNEL MACRO 'UNUSED';
/* Returns true if ELEM is a head, false otherwise. */
static inline bool
is_head(struct list_elem* elem)
{
return elem != NULL && elem->prev == NULL && elem->next != NULL;
}
/* Returns true if ELEM is an interior element,
false otherwise. */
static inline bool
is_interior(struct list_elem* elem)
{
return elem != NULL && elem->prev != NULL && elem->next != NULL;
}
/* Returns true if ELEM is a tail, false otherwise. */
static inline bool
is_tail(struct list_elem* elem)
{
return elem != NULL && elem->prev != NULL && elem->next == NULL;
}
/* Initializes LIST as an empty list. */
void
list_init(struct list* list)
{
ASSERT(list != NULL);
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}
/* Returns the beginning of LIST. */
struct list_elem*
list_begin(struct list* list)
{
ASSERT(list != NULL);
return list->head.next;
}
/* Returns the element after ELEM in its list. If ELEM is the
last element in its list, returns the list tail. Results are
undefined if ELEM is itself a list tail. */
struct list_elem*
list_next(struct list_elem* elem)
{
ASSERT(is_head(elem) || is_interior(elem));
return elem->next;
}
/* Returns LIST's tail.
list_end() is often used in iterating through a list from
front to back. See the big comment at the top of list.h for
an example. */
struct list_elem*
list_end(struct list* list)
{
ASSERT(list != NULL);
return &list->tail;
}
/* Returns the LIST's reverse beginning, for iterating through
LIST in reverse order, from back to front. */
struct list_elem*
list_rbegin(struct list* list)
{
ASSERT(list != NULL);
return list->tail.prev;
}
/* Returns the element before ELEM in its list. If ELEM is the
first element in its list, returns the list head. Results are
undefined if ELEM is itself a list head. */
struct list_elem*
list_prev(struct list_elem* elem)
{
ASSERT(is_interior(elem) || is_tail(elem));
return elem->prev;
}
/* Returns LIST's head.
list_rend() is often used in iterating through a list in
reverse order, from back to front. Here's typical usage,
following the example from the top of list.h:
for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
e = list_prev (e))
{
struct foo *f = list_entry (e, struct foo, elem);
...do something with f...
}
*/
struct list_elem*
list_rend(struct list* list)
{
ASSERT(list != NULL);
return &list->head;
}
/* Return's LIST's head.
list_head() can be used for an alternate style of iterating
through a list, e.g.:
e = list_head (&list);
while ((e = list_next (e)) != list_end (&list))
{
...
}
*/
struct list_elem*
list_head(struct list* list)
{
ASSERT(list != NULL);
return &list->head;
}
/* Return's LIST's tail. */
struct list_elem*
list_tail(struct list* list)
{
ASSERT(list != NULL);
return &list->tail;
}
/* Inserts ELEM just before BEFORE, which may be either an
interior element or a tail. The latter case is equivalent to
list_push_back(). */
void
list_insert(struct list_elem* before, struct list_elem* elem)
{
ASSERT(is_interior(before) || is_tail(before));
ASSERT(elem != NULL);
elem->prev = before->prev;
elem->next = before;
before->prev->next = elem;
before->prev = elem;
}
/* Removes elements FIRST though LAST (exclusive) from their
current list, then inserts them just before BEFORE, which may
be either an interior element or a tail. */
void
list_splice(struct list_elem* before,
struct list_elem* first, struct list_elem* last)
{
ASSERT(is_interior(before) || is_tail(before));
if (first == last)
return;
last = list_prev(last);
ASSERT(is_interior(first));
ASSERT(is_interior(last));
/* Cleanly remove FIRST...LAST from its current list. */
first->prev->next = last->next;
last->next->prev = first->prev;
/* Splice FIRST...LAST into new list. */
first->prev = before->prev;
last->next = before;
before->prev->next = first;
before->prev = last;
}
/* Inserts ELEM at the beginning of LIST, so that it becomes the
front in LIST. */
void
list_push_front(struct list* list, struct list_elem* elem)
{
list_insert(list_begin(list), elem);
}
/* Inserts ELEM at the end of LIST, so that it becomes the
back in LIST. */
void
list_push_back(struct list* list, struct list_elem* elem)
{
list_insert(list_end(list), elem);
}
/* Removes ELEM from its list and returns the element that
followed it. Undefined behavior if ELEM is not in a list.
It's not safe to treat ELEM as an element in a list after
removing it. In particular, using list_next() or list_prev()
on ELEM after removal yields undefined behavior. This means
that a naive loop to remove the elements in a list will fail:
** DON'T DO THIS **
for (e = list_begin (&list); e != list_end (&list); e = list_next (e))
{
...do something with e...
list_remove (e);
}
** DON'T DO THIS **
Here is one correct way to iterate and remove elements from a
list:
for (e = list_begin (&list); e != list_end (&list); e = list_remove (e))
{
...do something with e...
}
If you need to free() elements of the list then you need to be
more conservative. Here's an alternate strategy that works
even in that case:
while (!list_empty (&list))
{
struct list_elem *e = list_pop_front (&list);
...do something with e...
}
*/
struct list_elem*
list_remove(struct list_elem* elem)
{
ASSERT(is_interior(elem));
elem->prev->next = elem->next;
elem->next->prev = elem->prev;
return elem->next;
}
/* Removes the front element from LIST and returns it.
Undefined behavior if LIST is empty before removal. */
struct list_elem*
list_pop_front(struct list* list)
{
struct list_elem* front = list_front(list);
list_remove(front);
return front;
}
/* Removes the back element from LIST and returns it.
Undefined behavior if LIST is empty before removal. */
struct list_elem*
list_pop_back(struct list* list)
{
struct list_elem* back = list_back(list);
list_remove(back);
return back;
}
/* Returns the front element in LIST.
Undefined behavior if LIST is empty. */
struct list_elem*
list_front(struct list* list)
{
ASSERT(!list_empty(list));
return list->head.next;
}
/* Returns the back element in LIST.
Undefined behavior if LIST is empty. */
struct list_elem*
list_back(struct list* list)
{
ASSERT(!list_empty(list));
return list->tail.prev;
}
/* Returns the number of elements in LIST.
Runs in O(n) in the number of elements. */
size_t
list_size(struct list* list)
{
struct list_elem* e;
size_t cnt = 0;
for (e = list_begin(list); e != list_end(list); e = list_next(e))
cnt++;
return cnt;
}
/* Returns true if LIST is empty, false otherwise. */
bool
list_empty(struct list* list)
{
return list_begin(list) == list_end(list);
}
/*project 0-2-1*/
void
list_swap(struct list_elem* a, struct list_elem* b)
{
struct list_elem* t;
t = (struct list_elem*)malloc(sizeof(struct list_elem));
*t = *a;
*a = *b;
*b = *t;
b->next = a->next;
a->next = t->next;
b->prev = a->prev;
a->prev = t->prev;
free(t);
}
void list_shuffle(struct list* list) {
srand((unsigned int)time(NULL));
int count = rand();
count %= 10;
struct list_elem* cur;
struct list_elem* x;
struct list_elem* y;
for (int i = 0; i < count; i++) {
int a = rand();
int b = rand();
a %= 10;
b %= 10;
cur = (&list->head)->next;
for (int j = 0; j < a; j++) {
cur = cur->next;
if (cur == &list->tail)
cur = (&list->tail)->prev;
}
x = cur;
cur = (&list->head)->next;
for (int k = 0; k < b; k++) {
cur = cur->next;
if (cur == &list->tail)
cur = (&list->tail)->prev;
}
y = cur;
swap(x, y);
}
}
/* Swaps the `struct list_elem *'s that A and B point to. */
static void
swap(struct list_elem** a, struct list_elem** b)
{
struct list_elem* t = *a;
*a = *b;
*b = t;
}
/* Reverses the order of LIST. */
void
list_reverse(struct list* list)
{
if (!list_empty(list))
{
struct list_elem* e;
for (e = list_begin(list); e != list_end(list); e = e->prev)
swap(&e->prev, &e->next);
swap(&list->head.next, &list->tail.prev);
swap(&list->head.next->prev, &list->tail.prev->next);
}
}
/* Returns true only if the list elements A through B (exclusive)
are in order according to LESS given auxiliary data AUX. */
static bool
is_sorted(struct list_elem* a, struct list_elem* b,
list_less_func* less, void* aux)
{
if (a != b)
while ((a = list_next(a)) != b)
if (less(a, list_prev(a), aux))
return false;
return true;
}
/* Finds a run, starting at A and ending not after B, of list
elements that are in nondecreasing order according to LESS
given auxiliary data AUX. Returns the (exclusive) end of the
run.
A through B (exclusive) must form a non-empty range. */
static struct list_elem*
find_end_of_run(struct list_elem* a, struct list_elem* b,
list_less_func* less, void* aux)
{
ASSERT(a != NULL);
ASSERT(b != NULL);
ASSERT(less != NULL);
ASSERT(a != b);
do
{
a = list_next(a);
} while (a != b && !less(a, list_prev(a), aux));
return a;
}
/* Merges A0 through A1B0 (exclusive) with A1B0 through B1
(exclusive) to form a combined range also ending at B1
(exclusive). Both input ranges must be nonempty and sorted in
nondecreasing order according to LESS given auxiliary data
AUX. The output range will be sorted the same way. */
static void
inplace_merge(struct list_elem* a0, struct list_elem* a1b0,
struct list_elem* b1,
list_less_func* less, void* aux)
{
ASSERT(a0 != NULL);
ASSERT(a1b0 != NULL);
ASSERT(b1 != NULL);
ASSERT(less != NULL);
ASSERT(is_sorted(a0, a1b0, less, aux));
ASSERT(is_sorted(a1b0, b1, less, aux));
while (a0 != a1b0 && a1b0 != b1)
if (!less(a1b0, a0, aux))
a0 = list_next(a0);
else
{
a1b0 = list_next(a1b0);
list_splice(a0, list_prev(a1b0), a1b0);
}
}
/* Sorts LIST according to LESS given auxiliary data AUX, using a
natural iterative merge sort that runs in O(n lg n) time and
O(1) space in the number of elements in LIST. */
void
list_sort(struct list* list, list_less_func* less, void* aux)
{
size_t output_run_cnt; /* Number of runs output in current pass. */
ASSERT(list != NULL);
ASSERT(less != NULL);
/* Pass over the list repeatedly, merging adjacent runs of
nondecreasing elements, until only one run is left. */
do
{
struct list_elem* a0; /* Start of first run. */
struct list_elem* a1b0; /* End of first run, start of second. */
struct list_elem* b1; /* End of second run. */
output_run_cnt = 0;
for (a0 = list_begin(list); a0 != list_end(list); a0 = b1)
{
/* Each iteration produces one output run. */
output_run_cnt++;
/* Locate two adjacent runs of nondecreasing elements
A0...A1B0 and A1B0...B1. */
a1b0 = find_end_of_run(a0, list_end(list), less, aux);
if (a1b0 == list_end(list))
break;
b1 = find_end_of_run(a1b0, list_end(list), less, aux);
/* Merge the runs. */
inplace_merge(a0, a1b0, b1, less, aux);
}
} while (output_run_cnt > 1);
ASSERT(is_sorted(list_begin(list), list_end(list), less, aux));
}
/* Inserts ELEM in the proper position in LIST, which must be
sorted according to LESS given auxiliary data AUX.
Runs in O(n) average case in the number of elements in LIST. */
void
list_insert_ordered(struct list* list, struct list_elem* elem,
list_less_func* less, void* aux)
{
struct list_elem* e;
ASSERT(list != NULL);
ASSERT(elem != NULL);
ASSERT(less != NULL);
for (e = list_begin(list); e != list_end(list); e = list_next(e))
if (less(elem, e, aux))
break;
return list_insert(e, elem);
}
/* Iterates through LIST and removes all but the first in each
set of adjacent elements that are equal according to LESS
given auxiliary data AUX. If DUPLICATES is non-null, then the
elements from LIST are appended to DUPLICATES. */
void
list_unique(struct list* list, struct list* duplicates,
list_less_func* less, void* aux)
{
struct list_elem* elem, * next;
ASSERT(list != NULL);
ASSERT(less != NULL);
if (list_empty(list))
return;
elem = list_begin(list);
while ((next = list_next(elem)) != list_end(list))
if (!less(elem, next, aux) && !less(next, elem, aux))
{
list_remove(next);
if (duplicates != NULL)
list_push_back(duplicates, next);
}
else
elem = next;
}
/* Returns the element in LIST with the largest value according
to LESS given auxiliary data AUX. If there is more than one
maximum, returns the one that appears earlier in the list. If
the list is empty, returns its tail. */
struct list_elem*
list_max(struct list* list, list_less_func* less, void* aux)
{
struct list_elem* max = list_begin(list);
if (max != list_end(list))
{
struct list_elem* e;
for (e = list_next(max); e != list_end(list); e = list_next(e))
if (less(max, e, aux))
max = e;
}
return max;
}
/* Returns the element in LIST with the smallest value according
to LESS given auxiliary data AUX. If there is more than one
minimum, returns the one that appears earlier in the list. If
the list is empty, returns its tail. */
struct list_elem*
list_min(struct list* list, list_less_func* less, void* aux)
{
struct list_elem* min = list_begin(list);
if (min != list_end(list))
{
struct list_elem* e;
for (e = list_next(min); e != list_end(list); e = list_next(e))
if (less(e, min, aux))
min = e;
}
return min;
}
#include <stdio.h>
#include <ctype.h>
#include "hex_dump.h"
#include "round.h"
/* Dumps the SIZE bytes in BUF to the console as hex bytes
arranged 16 per line. Numeric offsets are also included,
starting at OFS for the first byte in BUF. If ASCII is true
then the corresponding ASCII characters are also rendered
alongside. */
void
hex_dump (uintptr_t ofs, const void *buf__, size_t size, bool ascii)
{
const uint8_t *buf = buf__;
const size_t per_line = 16; /* Maximum bytes per line. */
while (size > 0)
{
size_t start, end, n;
size_t i;
/* Number of bytes on this line. */
start = ofs % per_line;
end = per_line;
if (end - start > size)
end = start + size;
n = end - start;
/* Print line. */
printf ("%08jx ", (uintmax_t) ROUND_DOWN (ofs, per_line));
for (i = 0; i < start; i++)
printf (" ");
for (; i < end; i++)
printf ("%02hhx%c",
buf[i - start], i == per_line / 2 - 1? '-' : ' ');
if (ascii)
{
for (; i < per_line; i++)
printf (" ");
printf ("|");
for (i = 0; i < start; i++)
printf (" ");
for (; i < end; i++)
printf ("%c",
isprint (buf[i - start]) ? buf[i - start] : '.');
for (; i < per_line; i++)
printf (" ");
printf ("|");
}
printf ("\n");
ofs += n;
buf += n;
size -= n;
}
}
/* Hash table.
This data structure is thoroughly documented in the Tour of
Pintos for Project 3.
See hash.h for basic information. */
#include "hash.h"
#include <assert.h> // Instead of #include "../debug.h"
#include <stdlib.h> // #include "threads/malloc.h"
#include <time.h>
#define ASSERT(CONDITION) assert(CONDITION) // patched for proj0-2
#define list_elem_to_hash_elem(LIST_ELEM) \
list_entry(LIST_ELEM, struct hash_elem, list_elem)
static struct list* find_bucket(struct hash*, struct hash_elem*);
static struct hash_elem* find_elem(struct hash*, struct list*,
struct hash_elem*);
static void insert_elem(struct hash*, struct list*, struct hash_elem*);
static void remove_elem(struct hash*, struct hash_elem*);
static void rehash(struct hash*);
/* Initializes hash table H to compute hash values using HASH and
compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init(struct hash* h,
hash_hash_func* hash, hash_less_func* less, void* aux)
{
h->elem_cnt = 0;
h->bucket_cnt = 4;
h->buckets = malloc(sizeof * h->buckets * h->bucket_cnt);
h->hash = hash;
h->less = less;
h->aux = aux;
if (h->buckets != NULL)
{
hash_clear(h, NULL);
return true;
}
else
return false;
}
/* Removes all the elements from H.
If DESTRUCTOR is non-null, then it is called for each element
in the hash. DESTRUCTOR may, if appropriate, deallocate the
memory used by the hash element. However, modifying hash
table H while hash_clear() is running, using any of the
functions hash_clear(), hash_destroy(), hash_insert(),
hash_replace(), or hash_delete(), yields undefined behavior,
whether done in DESTRUCTOR or elsewhere. */
void
hash_clear(struct hash* h, hash_action_func* destructor)
{
size_t i;
for (i = 0; i < h->bucket_cnt; i++)
{
struct list* bucket = &h->buckets[i];
if (destructor != NULL)
while (!list_empty(bucket))
{
struct list_elem* list_elem = list_pop_front(bucket);
struct hash_elem* hash_elem = list_elem_to_hash_elem(list_elem);
destructor(hash_elem, h->aux);
}
list_init(bucket);
}
h->elem_cnt = 0;
}
/* Destroys hash table H.
If DESTRUCTOR is non-null, then it is first called for each
element in the hash. DESTRUCTOR may, if appropriate,
deallocate the memory used by the hash element. However,
modifying hash table H while hash_clear() is running, using
any of the functions hash_clear(), hash_destroy(),
hash_insert(), hash_replace(), or hash_delete(), yields
undefined behavior, whether done in DESTRUCTOR or
elsewhere. */
void
hash_destroy(struct hash* h, hash_action_func* destructor)
{
if (destructor != NULL)
hash_clear(h, destructor);
free(h->buckets);
}
/* Inserts NEW into hash table H and returns a null pointer, if
no equal element is already in the table.
If an equal element is already in the table, returns it
without inserting NEW. */
struct hash_elem*
hash_insert(struct hash* h, struct hash_elem* new)
{
struct list* bucket = find_bucket(h, new);
struct hash_elem* old = find_elem(h, bucket, new);
if (old == NULL)
insert_elem(h, bucket, new);
rehash(h);
return old;
}
/* Inserts NEW into hash table H, replacing any equal element
already in the table, which is returned. */
struct hash_elem*
hash_replace(struct hash* h, struct hash_elem* new)
{
struct list* bucket = find_bucket(h, new);
struct hash_elem* old = find_elem(h, bucket, new);
if (old != NULL)
remove_elem(h, old);
insert_elem(h, bucket, new);
rehash(h);
return old;
}
/* Finds and returns an element equal to E in hash table H, or a
null pointer if no equal element exists in the table. */
struct hash_elem*
hash_find(struct hash* h, struct hash_elem* e)
{
return find_elem(h, find_bucket(h, e), e);
}
/* Finds, removes, and returns an element equal to E in hash
table H. Returns a null pointer if no equal element existed
in the table.
If the elements of the hash table are dynamically allocated,
or own resources that are, then it is the caller's
responsibility to deallocate them. */
struct hash_elem*
hash_delete(struct hash* h, struct hash_elem* e)
{
struct hash_elem* found = find_elem(h, find_bucket(h, e), e);
if (found != NULL)
{
remove_elem(h, found);
rehash(h);
}
return found;
}
/* Calls ACTION for each element in hash table H in arbitrary
order.
Modifying hash table H while hash_apply() is running, using
any of the functions hash_clear(), hash_destroy(),
hash_insert(), hash_replace(), or hash_delete(), yields
undefined behavior, whether done from ACTION or elsewhere. */
void
hash_apply(struct hash* h, hash_action_func* action)
{
size_t i;
ASSERT(action != NULL);
for (i = 0; i < h->bucket_cnt; i++)
{
struct list* bucket = &h->buckets[i];
struct list_elem* elem, * next;
for (elem = list_begin(bucket); elem != list_end(bucket); elem = next)
{
next = list_next(elem);
action(list_elem_to_hash_elem(elem), h->aux);
}
}
}
/* Initializes I for iterating hash table H.
Iteration idiom:
struct hash_iterator i;
hash_first (&i, h);
while (hash_next (&i))
{
struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
...do something with f...
}
Modifying hash table H during iteration, using any of the
functions hash_clear(), hash_destroy(), hash_insert(),
hash_replace(), or hash_delete(), invalidates all
iterators. */
void
hash_first(struct hash_iterator* i, struct hash* h)
{
ASSERT(i != NULL);
ASSERT(h != NULL);
i->hash = h;
i->bucket = i->hash->buckets;
i->elem = list_elem_to_hash_elem(list_head(i->bucket));
}
/* Advances I to the next element in the hash table and returns
it. Returns a null pointer if no elements are left. Elements
are returned in arbitrary order.
Modifying a hash table H during iteration, using any of the
functions hash_clear(), hash_destroy(), hash_insert(),
hash_replace(), or hash_delete(), invalidates all
iterators. */
struct hash_elem*
hash_next(struct hash_iterator* i)
{
ASSERT(i != NULL);
i->elem = list_elem_to_hash_elem(list_next(&i->elem->list_elem));
while (i->elem == list_elem_to_hash_elem(list_end(i->bucket)))
{
if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
{
i->elem = NULL;
break;
}
i->elem = list_elem_to_hash_elem(list_begin(i->bucket));
}
return i->elem;
}
/* Returns the current element in the hash table iteration, or a
null pointer at the end of the table. Undefined behavior
after calling hash_first() but before hash_next(). */
struct hash_elem*
hash_cur(struct hash_iterator* i)
{
return i->elem;
}
/* Returns the number of elements in H. */
size_t
hash_size(struct hash* h)
{
return h->elem_cnt;
}
/* Returns true if H contains no elements, false otherwise. */
bool
hash_empty(struct hash* h)
{
return h->elem_cnt == 0;
}
/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
#define FNV_32_PRIME 16777619u
#define FNV_32_BASIS 2166136261u
/* Returns a hash of the SIZE bytes in BUF. */
unsigned
hash_bytes(const void* buf_, size_t size)
{
/* Fowler-Noll-Vo 32-bit hash, for bytes. */
const unsigned char* buf = buf_;
unsigned hash;
ASSERT(buf != NULL);
hash = FNV_32_BASIS;
while (size-- > 0)
hash = (hash * FNV_32_PRIME) ^ *buf++;
return hash;
}
/* Returns a hash of string S. */
unsigned
hash_string(const char* s_)
{
const unsigned char* s = (const unsigned char*)s_;
unsigned hash;
ASSERT(s != NULL);
hash = FNV_32_BASIS;
while (*s != '\0')
hash = (hash * FNV_32_PRIME) ^ *s++;
return hash;
}
//unsigned
//hash_hash(const struct hash_elem * e, void* aux) {
// const struct list_item* p;
// hash_entry(e, struct list_item, elem);
// return hash_int(elem->);
//}
/* Returns a hash of integer I. */
unsigned
hash_int(int i)
{
return hash_bytes(&i, sizeof i);
}
unsigned hash_int_2(int i) {
//parameter: integer that will be hashed
//return value: hash value of integer i
//implement this in your own way and describe it in the document
//버킷: 해시 테이블의 자료 구조체 내의 리스트 구조체를 버킷포인터로 사용
//각각의 버킷은 리스트로 구성되어 있음
//리스트 넥스트 함수를 통해, 키에 매핑되는 밸류찾기 가능
//해시테이블 엔트리의 프리브 넥스트, 밸류: 리스트 엘리먼트와 동일
/*리스트 엘리먼트를 매핑한 형태 == 엔트리
* 밸류를 찾는 법: 리스트아이템이, 리스트엘리먼트와 데이터를 함께 포함
* 해시에선, 리스트엘리먼트로 구성된 해시엘리먼트만 주어지고, 데이터는 처리안함
* 그렇기에, 리스트아이템을 참조해, 비슷하게 구현하면 됨
*
* 버킷카운트: 해시테이블의 버킷이 몇개?
* 실제 버킷은, 리스트포인터를 사용해, 메모리할당 받아 사용
* 해시해시펑션: 함수포인터. 해시 함수 포인터는, 해시함수(x/100)같은 걸 사용할
* 함수를 여기에 넣음
* 해시레스펑션: 엘리먼트의 데이터의 대소비교. 이 역시 따로 구현해 넣어주면 됨
* void *aux: 사용자가 필요한 경우, 추가로 억스포인터에 데이터를 넣어 해시테이블
* 에 넣어 사용할 수 있게 하는 보조적 변수
*
* 해시 어플라이: 액션 펑션을 해시테이블 내의 모든 엘리먼트에 대해 수행
*/
srand((unsigned int)time(NULL));
int count = rand();
unsigned int ret;
ret = i % 10;
return ret;
}
/* Returns the bucket in H that E belongs in. */
static struct list*
find_bucket(struct hash* h, struct hash_elem* e)
{
size_t bucket_idx = h->hash(e, h->aux) & (h->bucket_cnt - 1);
return &h->buckets[bucket_idx];
}
/* Searches BUCKET in H for a hash element equal to E. Returns
it if found or a null pointer otherwise. */
static struct hash_elem*
find_elem(struct hash* h, struct list* bucket, struct hash_elem* e)
{
struct list_elem* i;
for (i = list_begin(bucket); i != list_end(bucket); i = list_next(i))
{
struct hash_elem* hi = list_elem_to_hash_elem(i);
if (!h->less(hi, e, h->aux) && !h->less(e, hi, h->aux))
return hi;
}
return NULL;
}
/* Returns X with its lowest-order bit set to 1 turned off. */
static inline size_t
turn_off_least_1bit(size_t x)
{
return x & (x - 1);
}
/* Returns true if X is a power of 2, otherwise false. */
static inline size_t
is_power_of_2(size_t x)
{
return x != 0 && turn_off_least_1bit(x) == 0;
}
/* Element per bucket ratios. */
#define MIN_ELEMS_PER_BUCKET 1 /* Elems/bucket < 1: reduce # of buckets. */
#define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */
#define MAX_ELEMS_PER_BUCKET 4 /* Elems/bucket > 4: increase # of buckets. */
/* Changes the number of buckets in hash table H to match the
ideal. This function can fail because of an out-of-memory
condition, but that'll just make hash accesses less efficient;
we can still continue. */
static void
rehash(struct hash* h)
{
size_t old_bucket_cnt, new_bucket_cnt;
struct list* new_buckets, * old_buckets;
size_t i;
ASSERT(h != NULL);
/* Save old bucket info for later use. */
old_buckets = h->buckets;
old_bucket_cnt = h->bucket_cnt;
/* Calculate the number of buckets to use now.
We want one bucket for about every BEST_ELEMS_PER_BUCKET.
We must have at least four buckets, and the number of
buckets must be a power of 2. */
new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
if (new_bucket_cnt < 4)
new_bucket_cnt = 4;
while (!is_power_of_2(new_bucket_cnt))
new_bucket_cnt = turn_off_least_1bit(new_bucket_cnt);
/* Don't do anything if the bucket count wouldn't change. */
if (new_bucket_cnt == old_bucket_cnt)
return;
/* Allocate new buckets and initialize them as empty. */
new_buckets = malloc(sizeof * new_buckets * new_bucket_cnt);
if (new_buckets == NULL)
{
/* Allocation failed. This means that use of the hash table will
be less efficient. However, it is still usable, so
there's no reason for it to be an error. */
return;
}
for (i = 0; i < new_bucket_cnt; i++)
list_init(&new_buckets[i]);
/* Install new bucket info. */
h->buckets = new_buckets;
h->bucket_cnt = new_bucket_cnt;
/* Move each old element into the appropriate new bucket. */
for (i = 0; i < old_bucket_cnt; i++)
{
struct list* old_bucket;
struct list_elem* elem, * next;
old_bucket = &old_buckets[i];
for (elem = list_begin(old_bucket);
elem != list_end(old_bucket); elem = next)
{
struct list* new_bucket
= find_bucket(h, list_elem_to_hash_elem(elem));
next = list_next(elem);
list_remove(elem);
list_push_front(new_bucket, elem);
}
}
free(old_buckets);
}
/* Inserts E into BUCKET (in hash table H). */
static void
insert_elem(struct hash* h, struct list* bucket, struct hash_elem* e)
{
h->elem_cnt++;
list_push_front(bucket, &e->list_elem);
}
/* Removes E from hash table H. */
static void
remove_elem(struct hash* h, struct hash_elem* e)
{
h->elem_cnt--;
list_remove(&e->list_elem);
}
#include "bitmap.h"
#include <assert.h> // Instead of #include <debug.h>
#include "limits.h" // #include <limits.h>
#include "round.h" // #include <round.h>
#include <stdio.h>
#include <stdlib.h> // #include "threads/malloc.h":malloc
#ifdef FILESYS
#include "filesys/file.h"
#endif
#include "hex_dump.h" // 'hex_dump' : defined in pintos/src/lib/stdio.c
#define ASSERT(CONDITION) assert(CONDITION) // patched for proj0-2
/* 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;
/* Number of bits in an element. */
#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)
/* 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; /* Number of bits. */
elem_type *bits; /* Elements that represent 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;
}
size_t bitnum(struct bitmap* b) {
return b->bit_cnt;
}
/* 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 BIT_CNT bits. */
static inline size_t
elem_cnt (size_t bit_cnt)
{
return DIV_ROUND_UP (bit_cnt, ELEM_BITS);
}
/* Returns the number of bytes required for BIT_CNT bits. */
static inline size_t
byte_cnt (size_t bit_cnt)
{
return sizeof (elem_type) * elem_cnt (bit_cnt);
}
/* 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;
}
/* 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. */
struct bitmap *
bitmap_create (size_t bit_cnt)
{
struct bitmap *b = malloc (sizeof *b);
if (b != NULL)
{
b->bit_cnt = bit_cnt;
b->bits = malloc (byte_cnt (bit_cnt));
for(int i=0; i<bit_cnt; i++)
if (b->bits != NULL || bit_cnt == 0)
{
bitmap_set_all (b, false);
return b;
}
free (b);
}
return NULL;
}
struct bitmap* bitmap_expand(struct bitmap * bitmap, int size) {
if (bitmap != NULL) {
size_t tmp = bitmap->bit_cnt;
size_t rst = bitmap_count(bitmap, 0, bitmap_size(bitmap), 0);
struct bitmap* b = malloc(sizeof * b);
if (b != NULL) {
b->bit_cnt = tmp + size;
b->bits = malloc(byte_cnt(tmp + size));
for (int i = 0; i < tmp; i++) {
size_t p = elem_idx(i);
b->bits[p] = bitmap->bits[p];
}
if (b->bits != NULL || b->bit_cnt == 0) {
for (int i = 0; i < size; i++) {
bitmap_set(b, tmp + i, false);
}
bitmap = b;
return bitmap;
}
free(b);
}
}
return NULL;
}
/* Atomically sets the bit numbered IDX in B to VALUE. */
void
bitmap_set(struct bitmap* b, size_t idx, bool value)
{
// printf("err %d %d\n", idx, b->bit_cnt);
ASSERT(b != NULL);
ASSERT(idx < b->bit_cnt);
if (value)
bitmap_mark(b, idx);
else
bitmap_reset(b, idx);
}
/* Creates and returns a bitmap with BIT_CNT bits in the
BLOCK_SIZE bytes of storage preallocated at BLOCK.
BLOCK_SIZE must be at least bitmap_needed_bytes(BIT_CNT). */
struct bitmap *
bitmap_create_in_buf (size_t bit_cnt, void *block, size_t block_size )
// Remove KERNEL MACRO 'UNUSED')
{
struct bitmap *b = block;
ASSERT (block_size >= bitmap_buf_size (bit_cnt));
b->bit_cnt = bit_cnt;
b->bits = (elem_type *) (b + 1);
bitmap_set_all (b, false);
return b;
}
/* Returns the number of bytes required to accomodate a bitmap
with BIT_CNT bits (for use with bitmap_create_in_buf()). */
size_t
bitmap_buf_size (size_t bit_cnt)
{
return sizeof (struct bitmap) + byte_cnt (bit_cnt);
}
/* Destroys bitmap B, freeing its storage.
Not for use on bitmaps created by
bitmap_create_preallocated(). */
void
bitmap_destroy (struct bitmap *b)
{
if (b != NULL)
{
free (b->bits);
free (b);
}
}
/* Bitmap size. */
/* Returns the number of bits in B. */
size_t
bitmap_size (const struct bitmap *b)
{
return b->bit_cnt;
}
/* Setting and testing single bits. */
/* Atomically sets the bit numbered BIT_IDX in B to true. */
void
bitmap_mark (struct bitmap *b, size_t bit_idx)
{
size_t idx = elem_idx (bit_idx);
elem_type mask = bit_mask (bit_idx);
/* This is equivalent to `b->bits[idx] |= mask' except that it
is guaranteed to be atomic on a uniprocessor machine. See
the description of the OR instruction in [IA32-v2b]. */
b->bits[idx] |= mask;
// asm ("orl %k1, %k0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
/* Setting and testing multiple bits. */
/* Sets all bits in B to VALUE. */
void
bitmap_set_all(struct bitmap* b, bool value)
{
ASSERT(b != NULL);
bitmap_set_multiple(b, 0, bitmap_size(b), value);
}
/* Sets the CNT bits starting at START in B to VALUE. */
void
bitmap_set_multiple(struct bitmap* b, size_t start, size_t cnt, bool value)
{
size_t i;
ASSERT(b != NULL);
ASSERT(start <= b->bit_cnt);
ASSERT(start + cnt <= b->bit_cnt);
for (i = 0; i < cnt; i++) {
bitmap_set(b, start + i, value);
}
}
/* Atomically sets the bit numbered BIT_IDX in B to false. */
void
bitmap_reset (struct bitmap *b, size_t bit_idx)
{
size_t idx = elem_idx (bit_idx);
elem_type mask = bit_mask (bit_idx);
// printf("\n\nbit idx: %d, idx: %d, mask: %ld, b->bits[] %d \n\n",
// bit_idx, idx, ~mask, b->bits[idx]);
/* This is equivalent to `b->bits[idx] &= ~mask' except that it
is guaranteed to be atomic on a uniprocessor machine. See
the description of the AND instruction in [IA32-v2a]. */
b->bits[idx] &= ~mask;
// printf("bitsidx %d , reset %d\n", b->bits[idx], b->bit_cnt);
// asm("andl %k1, %k0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
}
/* Atomically 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 bit_idx)
{
size_t idx = elem_idx (bit_idx);
elem_type mask = bit_mask (bit_idx);
/* This is equivalent to `b->bits[idx] ^= mask' except that it
is guaranteed to be atomic on a uniprocessor machine. See
the description of the XOR instruction in [IA32-v2b]. */
b->bits[idx] ^= mask;
// asm ("xorl %k1, %k0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
/* 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;
}
/* Returns the number of bits in B between START and START + CNT,
exclusive, that are set to VALUE. */
size_t
bitmap_count (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
size_t i, value_cnt;
ASSERT (b != NULL);
ASSERT (start <= b->bit_cnt);
ASSERT (start + cnt <= b->bit_cnt);
value_cnt = 0;
for (i = 0; i < cnt; i++)
if (bitmap_test (b, start + i) == value)
value_cnt++;
return value_cnt;
}
/* Returns true if any bits in B between START and START + CNT,
exclusive, are set to VALUE, and false otherwise. */
bool
bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
size_t i;
ASSERT (b != NULL);
ASSERT (start <= b->bit_cnt);
ASSERT (start + cnt <= b->bit_cnt);
for (i = 0; i < cnt; i++)
if (bitmap_test (b, start + i) == value)
return true;
return false;
}
/* Returns true if any bits in B between START and START + CNT,
exclusive, are set to true, and false otherwise.*/
bool
bitmap_any (const struct bitmap *b, size_t start, size_t cnt)
{
return bitmap_contains (b, start, cnt, true);
}
/* Returns true if no bits in B between START and START + CNT,
exclusive, are set to true, and false otherwise.*/
bool
bitmap_none (const struct bitmap *b, size_t start, size_t cnt)
{
return !bitmap_contains (b, start, cnt, true);
}
/* Returns true if every bit in B between START and START + CNT,
exclusive, is set to true, and false otherwise. */
bool
bitmap_all (const struct bitmap *b, size_t start, size_t cnt)
{
return !bitmap_contains (b, start, cnt, false);
}
/* Finding set or unset bits. */
/* 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. */
size_t
bitmap_scan (const struct bitmap *b, size_t start, size_t cnt, bool value)
{
ASSERT (b != NULL);
ASSERT (start <= b->bit_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;
}
return BITMAP_ERROR;
}
/* 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.
If CNT is zero, returns 0.
Bits are set atomically, but testing bits is not atomic with
setting them. */
size_t
bitmap_scan_and_flip (struct bitmap *b, size_t start, size_t cnt, bool value)
{
size_t idx = bitmap_scan (b, start, cnt, value);
if (idx != BITMAP_ERROR)
bitmap_set_multiple (b, idx, cnt, !value);
return idx;
}
/* File input and output. */
#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->bit_cnt);
}
/* Reads B from FILE. Returns true if successful, false
otherwise. */
bool
bitmap_read (struct bitmap *b, struct file *file)
{
bool success = true;
if (b->bit_cnt > 0)
{
off_t size = byte_cnt (b->bit_cnt);
success = file_read_at (file, b->bits, size, 0) == size;
b->bits[elem_cnt (b->bit_cnt) - 1] &= last_mask (b);
}
return success;
}
/* Writes B to FILE. Return true if successful, false
otherwise. */
bool
bitmap_write (const struct bitmap *b, struct file *file)
{
off_t size = byte_cnt (b->bit_cnt);
return file_write_at (file, b->bits, size, 0) == size;
}
#endif /* FILESYS */
/* Debugging. */
/* Dumps the contents of B to the console as hexadecimal. */
void
bitmap_dump (const struct bitmap *b)
{
hex_dump (0, b->bits, byte_cnt (b->bit_cnt)/2, false);
}