1

I am working on a Linux kernel module and I am using be built in linked list. I need to sort this list and I saw that there is a built in list_sort function as described below. However I'm confused about the priv parameter. What is this parameter used for and what do I need to pass? There isn't much documentation on it anywhere.

Defined in linux/list_sort.h:

/**
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *
 * This function implements "merge sort", which has O(nlog(n))
 * complexity.
 *
 * The comparison function @cmp must return a negative value if @a
 * should sort before @b, and a positive value if @a should sort after
 * @b. If @a and @b are equivalent, and their original relative
 * ordering is to be preserved, @cmp must return 0.
 */
void list_sort(void *priv, struct list_head *head,
        int (*cmp)(void *priv, struct list_head *a,
            struct list_head *b))

EDIT So I understand I can just pass NULL for the priv parameter. Now I'm not sure how to write my cmp function because list_sort takes in struct list_head pointers but I have my own defined struct birthday which contains a list_head. My below compare function won't work because list_head does not contain members that my struct birthday has.

struct birthday {
char *name;
int month;
int day;
int year;
struct list_head list;
};

int compare(void *priv, struct list_head *a, struct list_head *b) {
if (a != NULL && b != NULL) {
    struct birthday personA = a;
    struct birthday personB = b;
    int monthA = personA.month;
    int monthB = personB.month;
    int dayA = personA.day;
    int dayB = personB.day;
    int yearA = personA.year;
    int yearB = personB.year;

    if (yearA < yearB) {
        return 1;
    } else if (yearB < yearA) {
        return -1;
    } else {
        if (monthA < monthB) {
            return 1;
        } else if (monthB < monthA) {
            return -1;
        } else {
            if (dayA < dayB) {
                return 1;
            } else if (dayB < dayA) {
                return -1;
            } else {
            return 0;
            }
        }
    }
}

}

Shan
  • 3,057
  • 4
  • 21
  • 33
  • For people that will use list.h and the sorting function. These are the source files you may need and are modified for user space: [list.h](http://www.mcs.anl.gov/~kazutomo/list/) / [list_sort.c](https://gist.github.com/anonymous/c57d6665ad487e25329d91a2c44a2237). list_sort.h is no need to change, and you can find it on the git repo. – Kevin Dong Sep 05 '16 at 18:13

2 Answers2

1

The priv argument is just an argument that gets passed back to your cmp function, list_sort itself is not using it. You can pass in NULL if you don't need it.

Such a parameter is common for callback functions in C to avoid using global variables to pass information to the callback function.

nos
  • 223,662
  • 58
  • 417
  • 506
  • Thanks @nos. Can you see if you're able to help with my edited question? Thanks. – Shan Mar 01 '16 at 01:24
  • 1
    You need to use the [container_of()](http://stackoverflow.com/questions/15832301/understanding-container-of-macro-in-linux-kernel) macro to recover a pointer to your `struct birthday` like so: `struct birthday *personA = container_of(a, struct birthday , list);`. If you placed the `struct list_head list` as the 1. member of your `struct birthday` , you could also just do `struct birthday *personA = (struct birthday*)a;` – nos Mar 01 '16 at 08:16
0

use container_of to retrieve your actual struct. The first operand of container_of function is a list_head and the second is the type of your struct. fill the third argument with list.
It's easy to find out how container_of function works. It returns head->next->prev casted into the type you pass it though the second argument.

Community
  • 1
  • 1
geradism
  • 97
  • 2
  • 14