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