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

   1 #ifndef HEADER_LIST_H
   2 #define HEADER_LIST_H 1
   3
   4 #include <stdbool.h>
   5 #include <stddef.h>
   6 #include <stdint.h>
   7
   8 struct list_elem
   9   {
  10     struct list_elem *prev, *next;
  11   };
  12
  13 struct list
  14   {
  15     struct list_elem head, tail;
  16   };
  17
  18 #define list_entry(LIST_ELEM, STRUCT, MEMBER)                              \
  19         ((STRUCT *) ((uint8_t *) (LIST_ELEM) - offsetof (STRUCT, MEMBER)))
  20
  21 void list_init (struct list *);
  22
  23 struct list_elem *list_begin (struct list *);
  24 struct list_elem *list_end (struct list *);
  25 struct list_elem *list_next (struct list_elem *);
  26 struct list_elem *list_prev (struct list_elem *);
  27
  28 void list_insert (struct list_elem *, struct list_elem *);
  29 void list_splice (struct list_elem *before,
  30                   struct list_elem *first, struct list_elem *last);
  31 void list_push_front (struct list *, struct list_elem *);
  32 void list_push_back (struct list *, struct list_elem *);
  33
  34 void list_remove (struct list_elem *);
  35 struct list_elem *list_pop_front (struct list *);
  36 struct list_elem *list_pop_back (struct list *);
  37
  38 struct list_elem *list_front (struct list *);
  39 struct list_elem *list_back (struct list *);
  40
  41 size_t list_size (struct list *);
  42 bool list_empty (struct list *);
  43
  44 void list_reverse (struct list *);
  45
  46 typedef bool list_less_func (const struct list_elem *a,
  47                              const struct list_elem *b, void *aux);
  48
  49 void list_merge (struct list *, struct list *,
  50                  list_less_func *, void *aux);
  51 void list_sort (struct list *,
  52                 list_less_func *, void *aux);
  53 void list_insert_ordered (struct list *, struct list_elem *,
  54                           list_less_func *, void *aux);
  55 void list_unique (struct list *,
  56                   list_less_func *, void *aux);
  57
  58 #endif /* list.h */