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

   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 \f
 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 */