1 files changed, 181 insertions, 0 deletions
diff --git a/lib/kernel/list.h b/lib/kernel/list.h
new file mode 100644
index 0000000..82efbb5
--- /dev/null
+++ b/lib/kernel/list.h
@@ -0,0 +1,181 @@
+#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. */
+  };
+/* 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)))
+/* List initialization.
+   A list may be initialized by calling list_init():
+       struct list my_list;
+       list_init (&my_list);
+   or with an initializer using LIST_INITIALIZER:
+       struct list my_list = LIST_INITIALIZER (my_list); */
+#define LIST_INITIALIZER(NAME) { { NULL, &(NAME).tail }, \
+                                 { &(NAME).head, NULL } }
+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 *);
+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 *);
+/* 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 */

diff --git a/lib/kernel/list.h b/lib/kernel/list.h new file mode 100644 index 0000000..82efbb5 --- /dev/null +++ b/lib/kernel/list.h
@@ -0,0 +1,181 @@
	1	#ifndef __LIB_KERNEL_LIST_H
	2	#define __LIB_KERNEL_LIST_H
	3
	4	/* Doubly linked list.
	5
	6	This implementation of a doubly linked list does not require
	7	use of dynamically allocated memory. Instead, each structure
	8	that is a potential list element must embed a struct list_elem
	9	member. All of the list functions operate on these `struct
	10	list_elem's. The list_entry macro allows conversion from a
	11	struct list_elem back to a structure object that contains it.
	12
	13	For example, suppose there is a needed for a list of `struct
	14	foo'. `struct foo' should contain a `struct list_elem'
	15	member, like so:
	16
	17	struct foo
	18	{
	19	struct list_elem elem;
	20	int bar;
	21	...other members...
	22	};
	23
	24	Then a list of `struct foo' can be be declared and initialized
	25	like so:
	26
	27	struct list foo_list;
	28
	29	list_init (&foo_list);
	30
	31	Iteration is a typical situation where it is necessary to
	32	convert from a struct list_elem back to its enclosing
	33	structure. Here's an example using foo_list:
	34
	35	struct list_elem *e;
	36
	37	for (e = list_begin (&foo_list); e != list_end (&foo_list);
	38	e = list_next (e))
	39	{
	40	struct foo *f = list_entry (e, struct foo, elem);
	41	...do something with f...
	42	}
	43
	44	You can find real examples of list usage throughout the
	45	source; for example, malloc.c, palloc.c, and thread.c in the
	46	threads directory all use lists.
	47
	48	The interface for this list is inspired by the list<> template
	49	in the C++ STL. If you're familiar with list<>, you should
	50	find this easy to use. However, it should be emphasized that
	51	these lists do no type checking and can't do much other
	52	correctness checking. If you screw up, it will bite you.
	53
	54	Glossary of list terms:
	55
	56	- "front": The first element in a list. Undefined in an
	57	empty list. Returned by list_front().
	58
	59	- "back": The last element in a list. Undefined in an empty
	60	list. Returned by list_back().
	61
	62	- "tail": The element figuratively just after the last
	63	element of a list. Well defined even in an empty list.
	64	Returned by list_end(). Used as the end sentinel for an
	65	iteration from front to back.
	66
	67	- "beginning": In a non-empty list, the front. In an empty
	68	list, the tail. Returned by list_begin(). Used as the
	69	starting point for an iteration from front to back.
	70
	71	- "head": The element figuratively just before the first
	72	element of a list. Well defined even in an empty list.
	73	Returned by list_rend(). Used as the end sentinel for an
	74	iteration from back to front.
	75
	76	- "reverse beginning": In a non-empty list, the back. In an
	77	empty list, the head. Returned by list_rbegin(). Used as
	78	the starting point for an iteration from back to front.
	79
	80	- "interior element": An element that is not the head or
	81	tail, that is, a real list element. An empty list does
	82	not have any interior elements.
	83	*/
	84
	85	#include <stdbool.h>
	86	#include <stddef.h>
	87	#include <stdint.h>
	88
	89	/* List element. */
	90	struct list_elem
	91	{
	92	struct list_elem prev; / Previous list element. */
	93	struct list_elem next; / Next list element. */
	94	};
	95
	96	/* List. */
	97	struct list
	98	{
	99	struct list_elem head; /* List head. */
	100	struct list_elem tail; /* List tail. */
	101	};
	102
	103	/* Converts pointer to list element LIST_ELEM into a pointer to
	104	the structure that LIST_ELEM is embedded inside. Supply the
	105	name of the outer structure STRUCT and the member name MEMBER
	106	of the list element. See the big comment at the top of the
	107	file for an example. */
	108	#define list_entry(LIST_ELEM, STRUCT, MEMBER) \
	109	((STRUCT ) ((uint8_t ) &(LIST_ELEM)->next \
	110	- offsetof (STRUCT, MEMBER.next)))
	111
	112	/* List initialization.
	113
	114	A list may be initialized by calling list_init():
	115
	116	struct list my_list;
	117	list_init (&my_list);
	118
	119	or with an initializer using LIST_INITIALIZER:
	120
	121	struct list my_list = LIST_INITIALIZER (my_list); */
	122	#define LIST_INITIALIZER(NAME) { { NULL, &(NAME).tail }, \
	123	{ &(NAME).head, NULL } }
	124
	125	void list_init (struct list *);
	126
	127	/* List traversal. */
	128	struct list_elem list_begin (struct list );
	129	struct list_elem list_next (struct list_elem );
	130	struct list_elem list_end (struct list );
	131
	132	struct list_elem list_rbegin (struct list );
	133	struct list_elem list_prev (struct list_elem );
	134	struct list_elem list_rend (struct list );
	135
	136	struct list_elem list_head (struct list );
	137	struct list_elem list_tail (struct list );
	138
	139	/* List insertion. */
	140	void list_insert (struct list_elem , struct list_elem );
	141	void list_splice (struct list_elem *before,
	142	struct list_elem first, struct list_elem last);
	143	void list_push_front (struct list , struct list_elem );
	144	void list_push_back (struct list , struct list_elem );
	145
	146	/* List removal. */
	147	struct list_elem list_remove (struct list_elem );
	148	struct list_elem list_pop_front (struct list );
	149	struct list_elem list_pop_back (struct list );
	150
	151	/* List elements. */
	152	struct list_elem list_front (struct list );
	153	struct list_elem list_back (struct list );
	154
	155	/* List properties. */
	156	size_t list_size (struct list *);
	157	bool list_empty (struct list *);
	158
	159	/* Miscellaneous. */
	160	void list_reverse (struct list *);
	161
	162	/* Compares the value of two list elements A and B, given
	163	auxiliary data AUX. Returns true if A is less than B, or
	164	false if A is greater than or equal to B. */
	165	typedef bool list_less_func (const struct list_elem *a,
	166	const struct list_elem *b,
	167	void *aux);
	168
	169	/* Operations on lists with ordered elements. */
	170	void list_sort (struct list *,
	171	list_less_func , void aux);
	172	void list_insert_ordered (struct list , struct list_elem ,
	173	list_less_func , void aux);
	174	void list_unique (struct list , struct list duplicates,
	175	list_less_func , void aux);
	176
	177	/* Max and min. */
	178	struct list_elem list_max (struct list , list_less_func , void aux);
	179	struct list_elem list_min (struct list , list_less_func , void aux);
	180
	181	#endif /* lib/kernel/list.h */