lib/flist_sort.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include "../flist.h"
   4 #include "../log.h"
   5
   6 #define MAX_LIST_LENGTH_BITS 20
   7
   8 /*
   9  * Returns a list organized in an intermediate format suited
  10  * to chaining of merge() calls: null-terminated, no reserved or
  11  * sentinel head node, "prev" links not maintained.
  12  */
  13 static struct flist_head *merge(void *priv,
  14                                 int (*cmp)(void *priv, struct flist_head *a,
  15                                         struct flist_head *b),
  16                                 struct flist_head *a, struct flist_head *b)
  17 {
  18         struct flist_head head, *tail = &head;
  19
  20         while (a && b) {
  21                 /* if equal, take 'a' -- important for sort stability */
  22                 if ((*cmp)(priv, a, b) <= 0) {
  23                         tail->next = a;
  24                         a = a->next;
  25                 } else {
  26                         tail->next = b;
  27                         b = b->next;
  28                 }
  29                 tail = tail->next;
  30         }
  31         tail->next = a?:b;
  32         return head.next;
  33 }
  34
  35 /*
  36  * Combine final list merge with restoration of standard doubly-linked
  37  * list structure.  This approach duplicates code from merge(), but
  38  * runs faster than the tidier alternatives of either a separate final
  39  * prev-link restoration pass, or maintaining the prev links
  40  * throughout.
  41  */
  42 static void merge_and_restore_back_links(void *priv,
  43                                 int (*cmp)(void *priv, struct flist_head *a,
  44                                         struct flist_head *b),
  45                                 struct flist_head *head,
  46                                 struct flist_head *a, struct flist_head *b)
  47 {
  48         struct flist_head *tail = head;
  49
  50         while (a && b) {
  51                 /* if equal, take 'a' -- important for sort stability */
  52                 if ((*cmp)(priv, a, b) <= 0) {
  53                         tail->next = a;
  54                         a->prev = tail;
  55                         a = a->next;
  56                 } else {
  57                         tail->next = b;
  58                         b->prev = tail;
  59                         b = b->next;
  60                 }
  61                 tail = tail->next;
  62         }
  63         tail->next = a ? : b;
  64
  65         do {
  66                 /*
  67                  * In worst cases this loop may run many iterations.
  68                  * Continue callbacks to the client even though no
  69                  * element comparison is needed, so the client's cmp()
  70                  * routine can invoke cond_resched() periodically.
  71                  */
  72                 (*cmp)(priv, tail->next, tail->next);
  73
  74                 tail->next->prev = tail;
  75                 tail = tail->next;
  76         } while (tail->next);
  77
  78         tail->next = head;
  79         head->prev = tail;
  80 }
  81
  82 /**
  83  * list_sort - sort a list
  84  * @priv: private data, opaque to list_sort(), passed to @cmp
  85  * @head: the list to sort
  86  * @cmp: the elements comparison function
  87  *
  88  * This function implements "merge sort", which has O(nlog(n))
  89  * complexity.
  90  *
  91  * The comparison function @cmp must return a negative value if @a
  92  * should sort before @b, and a positive value if @a should sort after
  93  * @b. If @a and @b are equivalent, and their original relative
  94  * ordering is to be preserved, @cmp must return 0.
  95  */
  96 void flist_sort(void *priv, struct flist_head *head,
  97                 int (*cmp)(void *priv, struct flist_head *a,
  98                         struct flist_head *b))
  99 {
 100         struct flist_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
 101                                                 -- last slot is a sentinel */
 102         int lev;  /* index into part[] */
 103         int max_lev = 0;
 104         struct flist_head *list;
 105
 106         if (flist_empty(head))
 107                 return;
 108
 109         memset(part, 0, sizeof(part));
 110
 111         head->prev->next = NULL;
 112         list = head->next;
 113
 114         while (list) {
 115                 struct flist_head *cur = list;
 116                 list = list->next;
 117                 cur->next = NULL;
 118
 119                 for (lev = 0; part[lev]; lev++) {
 120                         cur = merge(priv, cmp, part[lev], cur);
 121                         part[lev] = NULL;
 122                 }
 123                 if (lev > max_lev) {
 124                         if (lev >= MAX_LIST_LENGTH_BITS) {
 125                                 log_err("fio: list passed to"
 126                                         " list_sort() too long for"
 127                                         " efficiency\n");
 128                                 lev--;
 129                         }
 130                         max_lev = lev;
 131                 }
 132                 part[lev] = cur;
 133         }
 134
 135         for (lev = 0; lev < max_lev; lev++)
 136                 if (part[lev])
 137                         list = merge(priv, cmp, part[lev], list);
 138
 139         merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
 140 }