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 } 141
