include/list.h

   1 /*
   2  * Copyright (C) 2008 Karel Zak <kzak@redhat.com>
   3  * Copyright (C) 1999-2008 by Theodore Ts'o
   4  *
   5  * This file may be redistributed under the terms of the
   6  * GNU Lesser General Public License.
   7  *
   8  * (based on list.h from e2fsprogs)
   9  * Merge sort based on kernel's implementation.
  10  */
  11
  12 #ifndef UTIL_LINUX_LIST_H
  13 #define UTIL_LINUX_LIST_H
  14
  15 #include "c.h"
  16
  17 /* TODO: use AC_C_INLINE */
  18 #ifdef __GNUC__
  19 #define _INLINE_ static __inline__
  20 #else                         /* For Watcom C */
  21 #define _INLINE_ static inline
  22 #endif
  23
  24 /*
  25  * Simple doubly linked list implementation.
  26  *
  27  * Some of the internal functions ("__xxx") are useful when
  28  * manipulating whole lists rather than single entries, as
  29  * sometimes we already know the next/prev entries and we can
  30  * generate better code by using them directly rather than
  31  * using the generic single-entry routines.
  32  */
  33
  34 struct list_head {
  35         struct list_head *next, *prev;
  36 };
  37
  38 #define INIT_LIST_HEAD(ptr) do { \
  39         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  40 } while (0)
  41
  42 /*
  43  * Insert a new entry between two known consecutive entries.
  44  *
  45  * This is only for internal list manipulation where we know
  46  * the prev/next entries already!
  47  */
  48 _INLINE_ void __list_add(struct list_head * add,
  49         struct list_head * prev,
  50         struct list_head * next)
  51 {
  52         next->prev = add;
  53         add->next = next;
  54         add->prev = prev;
  55         prev->next = add;
  56 }
  57
  58 /**
  59  * list_add - add a new entry
  60  * @add:        new entry to be added
  61  * @head:       list head to add it after
  62  *
  63  * Insert a new entry after the specified head.
  64  * This is good for implementing stacks.
  65  */
  66 _INLINE_ void list_add(struct list_head *add, struct list_head *head)
  67 {
  68         __list_add(add, head, head->next);
  69 }
  70
  71 /**
  72  * list_add_tail - add a new entry
  73  * @add:        new entry to be added
  74  * @head:       list head to add it before
  75  *
  76  * Insert a new entry before the specified head.
  77  * This is useful for implementing queues.
  78  */
  79 _INLINE_ void list_add_tail(struct list_head *add, struct list_head *head)
  80 {
  81         __list_add(add, head->prev, head);
  82 }
  83
  84 /*
  85  * Delete a list entry by making the prev/next entries
  86  * point to each other.
  87  *
  88  * This is only for internal list manipulation where we know
  89  * the prev/next entries already!
  90  */
  91 _INLINE_ void __list_del(struct list_head * prev,
  92                                   struct list_head * next)
  93 {
  94         next->prev = prev;
  95         prev->next = next;
  96 }
  97
  98 /**
  99  * list_del - deletes entry from list.
 100  * @entry:      the element to delete from the list.
 101  *
 102  * list_empty() on @entry does not return true after this, @entry is
 103  * in an undefined state.
 104  */
 105 _INLINE_ void list_del(struct list_head *entry)
 106 {
 107         __list_del(entry->prev, entry->next);
 108 }
 109
 110 /**
 111  * list_del_init - deletes entry from list and reinitialize it.
 112  * @entry:      the element to delete from the list.
 113  */
 114 _INLINE_ void list_del_init(struct list_head *entry)
 115 {
 116         __list_del(entry->prev, entry->next);
 117         INIT_LIST_HEAD(entry);
 118 }
 119
 120 /**
 121  * list_empty - tests whether a list is empty
 122  * @head:       the list to test.
 123  */
 124 _INLINE_ int list_empty(struct list_head *head)
 125 {
 126         return head->next == head;
 127 }
 128
 129 /**
 130  * list_entry_is_last - tests whether is entry last in the list
 131  * @entry:      the entry to test.
 132  * @head:       the list to test.
 133  */
 134 _INLINE_ int list_entry_is_last(struct list_head *entry, struct list_head *head)
 135 {
 136         return head->prev == entry;
 137 }
 138
 139 /**
 140  * list_entry_is_first - tests whether is entry first in the list
 141  * @entry:      the entry to test.
 142  * @head:       the list to test.
 143  */
 144 _INLINE_ int list_entry_is_first(struct list_head *entry, struct list_head *head)
 145 {
 146         return head->next == entry;
 147 }
 148
 149 /**
 150  * list_splice - join two lists
 151  * @list:       the new list to add.
 152  * @head:       the place to add it in the first list.
 153  */
 154 _INLINE_ void list_splice(struct list_head *list, struct list_head *head)
 155 {
 156         struct list_head *first = list->next;
 157
 158         if (first != list) {
 159                 struct list_head *last = list->prev;
 160                 struct list_head *at = head->next;
 161
 162                 first->prev = head;
 163                 head->next = first;
 164
 165                 last->next = at;
 166                 at->prev = last;
 167         }
 168 }
 169
 170 /**
 171  * list_entry - get the struct for this entry
 172  * @ptr:        the &struct list_head pointer.
 173  * @type:       the type of the struct this is embedded in.
 174  * @member:     the name of the list_struct within the struct.
 175  */
 176 #define list_entry(ptr, type, member)   container_of(ptr, type, member)
 177
 178 #define list_first_entry(head, type, member) \
 179         ((head) && (head)->next != (head) ? list_entry((head)->next, type, member) : NULL)
 180
 181 #define list_last_entry(head, type, member) \
 182         ((head) && (head)->prev != (head) ? list_entry((head)->prev, type, member) : NULL)
 183
 184 /**
 185  * list_for_each - iterate over elements in a list
 186  * @pos:        the &struct list_head to use as a loop counter.
 187  * @head:       the head for your list.
 188  */
 189 #define list_for_each(pos, head) \
 190         for (pos = (head)->next; pos != (head); pos = pos->next)
 191
 192 /**
 193  * list_for_each_backwardly - iterate over elements in a list in reverse
 194  * @pos:        the &struct list_head to use as a loop counter.
 195  * @head:       the head for your list.
 196  */
 197 #define list_for_each_backwardly(pos, head) \
 198         for (pos = (head)->prev; pos != (head); pos = pos->prev)
 199
 200 /**
 201  * list_for_each_safe - iterate over elements in a list, but don't dereference
 202  *                      pos after the body is done (in case it is freed)
 203  * @pos:        the &struct list_head to use as a loop counter.
 204  * @pnext:      the &struct list_head to use as a pointer to the next item.
 205  * @head:       the head for your list (not included in iteration).
 206  */
 207 #define list_for_each_safe(pos, pnext, head) \
 208         for (pos = (head)->next, pnext = pos->next; pos != (head); \
 209              pos = pnext, pnext = pos->next)
 210
 211 _INLINE_ size_t list_count_entries(struct list_head *head)
 212 {
 213         struct list_head *pos;
 214         size_t ct = 0;
 215
 216         list_for_each(pos, head)
 217                 ct++;
 218
 219         return ct;
 220 }
 221
 222 #define MAX_LIST_LENGTH_BITS 20
 223
 224 /*
 225  * Returns a list organized in an intermediate format suited
 226  * to chaining of merge() calls: null-terminated, no reserved or
 227  * sentinel head node, "prev" links not maintained.
 228  */
 229 _INLINE_ struct list_head *merge(int (*cmp)(struct list_head *a,
 230                                           struct list_head *b,
 231                                           void *data),
 232                                void *data,
 233                                struct list_head *a, struct list_head *b)
 234 {
 235         struct list_head head, *tail = &head;
 236
 237         while (a && b) {
 238                 /* if equal, take 'a' -- important for sort stability */
 239                 if ((*cmp)(a, b, data) <= 0) {
 240                         tail->next = a;
 241                         a = a->next;
 242                 } else {
 243                         tail->next = b;
 244                         b = b->next;
 245                 }
 246                 tail = tail->next;
 247         }
 248         tail->next = a ? a : b;
 249         return head.next;
 250 }
 251
 252 /*
 253  * Combine final list merge with restoration of standard doubly-linked
 254  * list structure.  This approach duplicates code from merge(), but
 255  * runs faster than the tidier alternatives of either a separate final
 256  * prev-link restoration pass, or maintaining the prev links
 257  * throughout.
 258  */
 259 _INLINE_ void merge_and_restore_back_links(int (*cmp)(struct list_head *a,
 260                                                     struct list_head *b,
 261                                                     void *data),
 262                                          void *data,
 263                                          struct list_head *head,
 264                                          struct list_head *a, struct list_head *b)
 265 {
 266         struct list_head *tail = head;
 267
 268         while (a && b) {
 269                 /* if equal, take 'a' -- important for sort stability */
 270                 if ((*cmp)(a, b, data) <= 0) {
 271                         tail->next = a;
 272                         a->prev = tail;
 273                         a = a->next;
 274                 } else {
 275                         tail->next = b;
 276                         b->prev = tail;
 277                         b = b->next;
 278                 }
 279                 tail = tail->next;
 280         }
 281         tail->next = a ? a : b;
 282
 283         do {
 284                 /*
 285                  * In worst cases this loop may run many iterations.
 286                  * Continue callbacks to the client even though no
 287                  * element comparison is needed, so the client's cmp()
 288                  * routine can invoke cond_resched() periodically.
 289                  */
 290                 (*cmp)(tail->next, tail->next, data);
 291
 292                 tail->next->prev = tail;
 293                 tail = tail->next;
 294         } while (tail->next);
 295
 296         tail->next = head;
 297         head->prev = tail;
 298 }
 299
 300
 301 /**
 302  * list_sort - sort a list
 303  * @head: the list to sort
 304  * @cmp: the elements comparison function
 305  *
 306  * This function implements "merge sort", which has O(nlog(n))
 307  * complexity.
 308  *
 309  * The comparison function @cmp must return a negative value if @a
 310  * should sort before @b, and a positive value if @a should sort after
 311  * @b. If @a and @b are equivalent, and their original relative
 312  * ordering is to be preserved, @cmp must return 0.
 313  */
 314 _INLINE_ void list_sort(struct list_head *head,
 315                         int (*cmp)(struct list_head *a,
 316                                    struct list_head *b,
 317                                    void *data),
 318                         void *data)
 319 {
 320         struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
 321                                                            -- last slot is a sentinel */
 322         size_t lev;  /* index into part[] */
 323         size_t max_lev = 0;
 324         struct list_head *list;
 325
 326         if (list_empty(head))
 327                 return;
 328
 329         memset(part, 0, sizeof(part));
 330
 331         head->prev->next = NULL;
 332         list = head->next;
 333
 334         while (list) {
 335                 struct list_head *cur = list;
 336                 list = list->next;
 337                 cur->next = NULL;
 338
 339                 for (lev = 0; part[lev]; lev++) {
 340                         cur = merge(cmp, data, part[lev], cur);
 341                         part[lev] = NULL;
 342                 }
 343                 if (lev > max_lev) {
 344                         /* list passed to list_sort() too long for efficiency */
 345                         if (lev >= ARRAY_SIZE(part) - 1)
 346                                 lev--;
 347                         max_lev = lev;
 348                 }
 349                 part[lev] = cur;
 350         }
 351
 352         for (lev = 0; lev < max_lev; lev++)
 353                 if (part[lev])
 354                         list = merge(cmp, data, part[lev], list);
 355
 356         merge_and_restore_back_links(cmp, data, head, part[max_lev], list);
 357 }
 358
 359 #undef _INLINE_
 360
 361 #endif /* UTIL_LINUX_LIST_H */