11ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe#include <stdio.h> 21ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe#include <string.h> 31ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe#include "../flist.h" 41ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe#include "../log.h" 51ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 61ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe#define MAX_LIST_LENGTH_BITS 20 71ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 81ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe/* 91ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * Returns a list organized in an intermediate format suited 101ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * to chaining of merge() calls: null-terminated, no reserved or 111ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * sentinel head node, "prev" links not maintained. 121ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe */ 131ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboestatic struct flist_head *merge(void *priv, 141ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe int (*cmp)(void *priv, struct flist_head *a, 151ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *b), 161ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *a, struct flist_head *b) 171ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe{ 181ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head head, *tail = &head; 191ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 201ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe while (a && b) { 211ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe /* if equal, take 'a' -- important for sort stability */ 221ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe if ((*cmp)(priv, a, b) <= 0) { 231ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = a; 241ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe a = a->next; 251ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } else { 261ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = b; 271ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe b = b->next; 281ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 291ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail = tail->next; 301ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 311ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = a?:b; 321ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe return head.next; 331ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe} 341ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 351ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe/* 361ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * Combine final list merge with restoration of standard doubly-linked 371ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * list structure. This approach duplicates code from merge(), but 381ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * runs faster than the tidier alternatives of either a separate final 391ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * prev-link restoration pass, or maintaining the prev links 401ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * throughout. 411ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe */ 421ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboestatic void merge_and_restore_back_links(void *priv, 431ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe int (*cmp)(void *priv, struct flist_head *a, 441ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *b), 451ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *head, 461ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *a, struct flist_head *b) 471ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe{ 481ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *tail = head; 491ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 501ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe while (a && b) { 511ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe /* if equal, take 'a' -- important for sort stability */ 521ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe if ((*cmp)(priv, a, b) <= 0) { 531ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = a; 541ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe a->prev = tail; 551ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe a = a->next; 561ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } else { 571ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = b; 581ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe b->prev = tail; 591ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe b = b->next; 601ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 611ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail = tail->next; 621ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 631ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = a ? : b; 641ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 651ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe do { 661ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe /* 671ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * In worst cases this loop may run many iterations. 681ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * Continue callbacks to the client even though no 691ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * element comparison is needed, so the client's cmp() 701ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * routine can invoke cond_resched() periodically. 711ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe */ 721ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe (*cmp)(priv, tail->next, tail->next); 731ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 741ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next->prev = tail; 751ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail = tail->next; 761ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } while (tail->next); 771ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 781ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe tail->next = head; 791ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe head->prev = tail; 801ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe} 811ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 821ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe/** 831ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * list_sort - sort a list 841ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * @priv: private data, opaque to list_sort(), passed to @cmp 851ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * @head: the list to sort 861ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * @cmp: the elements comparison function 871ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * 881ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * This function implements "merge sort", which has O(nlog(n)) 891ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * complexity. 901ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * 911ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * The comparison function @cmp must return a negative value if @a 921ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * should sort before @b, and a positive value if @a should sort after 931ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * @b. If @a and @b are equivalent, and their original relative 941ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe * ordering is to be preserved, @cmp must return 0. 951ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe */ 961ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboevoid flist_sort(void *priv, struct flist_head *head, 971ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe int (*cmp)(void *priv, struct flist_head *a, 981ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *b)) 991ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe{ 1001ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists 1011ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe -- last slot is a sentinel */ 1021ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe int lev; /* index into part[] */ 1031ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe int max_lev = 0; 1041ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *list; 1051ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1061ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe if (flist_empty(head)) 1071ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe return; 1081ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1091ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe memset(part, 0, sizeof(part)); 1101ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1111ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe head->prev->next = NULL; 1121ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe list = head->next; 1131ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1141ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe while (list) { 1151ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe struct flist_head *cur = list; 1161ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe list = list->next; 1171ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe cur->next = NULL; 1181ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1191ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe for (lev = 0; part[lev]; lev++) { 1201ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe cur = merge(priv, cmp, part[lev], cur); 1211ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe part[lev] = NULL; 1221ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 1231ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe if (lev > max_lev) { 1241ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe if (lev >= MAX_LIST_LENGTH_BITS) { 1251ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe log_err("fio: list passed to" 1261ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe " list_sort() too long for" 1271ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe " efficiency\n"); 1281ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe lev--; 1291ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 1301ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe max_lev = lev; 1311ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 1321ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe part[lev] = cur; 1331ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe } 1341ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1351ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe for (lev = 0; lev < max_lev; lev++) 1361ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe if (part[lev]) 1371ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe list = merge(priv, cmp, part[lev], list); 1381ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe 1391ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 1401ae83d45ed853cd73b95b89ae14cacac5b97187eJens Axboe} 141