+ int ret;
+
+ if (entry1->root_id > entry2->root_id)
+ ret = 1;
+ else if (entry1->root_id < entry2->root_id)
+ ret = -1;
+ else
+ ret = 0;
+
+ return is_descending ? -ret : ret;
+}
+
+static int comp_entry_with_gen(struct root_info *entry1,
+ struct root_info *entry2,
+ int is_descending)
+{
+ int ret;
+
+ if (entry1->gen > entry2->gen)
+ ret = 1;
+ else if (entry1->gen < entry2->gen)
+ ret = -1;
+ else
+ ret = 0;
+
+ return is_descending ? -ret : ret;
+}
+
+static int comp_entry_with_ogen(struct root_info *entry1,
+ struct root_info *entry2,
+ int is_descending)
+{
+ int ret;
+
+ if (entry1->ogen > entry2->ogen)
+ ret = 1;
+ else if (entry1->ogen < entry2->ogen)
+ ret = -1;
+ else
+ ret = 0;
+
+ return is_descending ? -ret : ret;
+}
+
+static int comp_entry_with_path(struct root_info *entry1,
+ struct root_info *entry2,
+ int is_descending)
+{
+ int ret;
+
+ if (strcmp(entry1->full_path, entry2->full_path) > 0)
+ ret = 1;
+ else if (strcmp(entry1->full_path, entry2->full_path) < 0)
+ ret = -1;
+ else
+ ret = 0;
+
+ return is_descending ? -ret : ret;
+}
+
+static btrfs_list_comp_func all_comp_funcs[] = {
+ [BTRFS_LIST_COMP_ROOTID] = comp_entry_with_rootid,
+ [BTRFS_LIST_COMP_OGEN] = comp_entry_with_ogen,
+ [BTRFS_LIST_COMP_GEN] = comp_entry_with_gen,
+ [BTRFS_LIST_COMP_PATH] = comp_entry_with_path,
+};
+
+static char *all_sort_items[] = {
+ [BTRFS_LIST_COMP_ROOTID] = "rootid",
+ [BTRFS_LIST_COMP_OGEN] = "ogen",
+ [BTRFS_LIST_COMP_GEN] = "gen",
+ [BTRFS_LIST_COMP_PATH] = "path",
+ [BTRFS_LIST_COMP_MAX] = NULL,
+};
+
+static int btrfs_list_get_sort_item(char *sort_name)
+{
+ int i;
+
+ for (i = 0; i < BTRFS_LIST_COMP_MAX; i++) {
+ if (strcmp(sort_name, all_sort_items[i]) == 0)
+ return i;
+ }
+ return -1;
+}
+
+struct btrfs_list_comparer_set *btrfs_list_alloc_comparer_set(void)
+{
+ struct btrfs_list_comparer_set *set;
+ int size;
+
+ size = sizeof(struct btrfs_list_comparer_set) +
+ BTRFS_LIST_NCOMPS_INCREASE * sizeof(struct btrfs_list_comparer);
+ set = calloc(1, size);
+ if (!set) {
+ fprintf(stderr, "memory allocation failed\n");
+ exit(1);
+ }
+
+ set->total = BTRFS_LIST_NCOMPS_INCREASE;
+
+ return set;
+}
+
+void btrfs_list_free_comparer_set(struct btrfs_list_comparer_set *comp_set)
+{
+ free(comp_set);
+}
+
+static int btrfs_list_setup_comparer(struct btrfs_list_comparer_set **comp_set,
+ enum btrfs_list_comp_enum comparer, int is_descending)
+{
+ struct btrfs_list_comparer_set *set = *comp_set;
+ int size;
+
+ BUG_ON(!set);
+ BUG_ON(comparer >= BTRFS_LIST_COMP_MAX);
+ BUG_ON(set->ncomps > set->total);
+
+ if (set->ncomps == set->total) {
+ void *tmp;
+
+ size = set->total + BTRFS_LIST_NCOMPS_INCREASE;
+ size = sizeof(*set) + size * sizeof(struct btrfs_list_comparer);
+ tmp = set;
+ set = realloc(set, size);
+ if (!set) {
+ fprintf(stderr, "memory allocation failed\n");
+ free(tmp);
+ exit(1);
+ }
+
+ memset(&set->comps[set->total], 0,
+ BTRFS_LIST_NCOMPS_INCREASE *
+ sizeof(struct btrfs_list_comparer));
+ set->total += BTRFS_LIST_NCOMPS_INCREASE;
+ *comp_set = set;
+ }
+
+ BUG_ON(set->comps[set->ncomps].comp_func);
+
+ set->comps[set->ncomps].comp_func = all_comp_funcs[comparer];
+ set->comps[set->ncomps].is_descending = is_descending;
+ set->ncomps++;
+ return 0;
+}
+
+static int sort_comp(struct root_info *entry1, struct root_info *entry2,
+ struct btrfs_list_comparer_set *set)
+{
+ int rootid_compared = 0;
+ int i, ret = 0;
+
+ if (!set || !set->ncomps)
+ goto comp_rootid;
+
+ for (i = 0; i < set->ncomps; i++) {
+ if (!set->comps[i].comp_func)
+ break;
+
+ ret = set->comps[i].comp_func(entry1, entry2,
+ set->comps[i].is_descending);
+ if (ret)
+ return ret;
+
+ if (set->comps[i].comp_func == comp_entry_with_rootid)
+ rootid_compared = 1;
+ }
+
+ if (!rootid_compared) {
+comp_rootid:
+ ret = comp_entry_with_rootid(entry1, entry2, 0);
+ }
+
+ return ret;
+}
+
+static int sort_tree_insert(struct root_lookup *sort_tree,
+ struct root_info *ins,
+ struct btrfs_list_comparer_set *comp_set)
+{
+ struct rb_node **p = &sort_tree->root.rb_node;
+ struct rb_node *parent = NULL;
+ struct root_info *curr;
+ int ret;
+
+ while (*p) {
+ parent = *p;
+ curr = rb_entry(parent, struct root_info, sort_node);
+
+ ret = sort_comp(ins, curr, comp_set);
+ if (ret < 0)
+ p = &(*p)->rb_left;
+ else if (ret > 0)
+ p = &(*p)->rb_right;
+ else
+ return -EEXIST;
+ }
+
+ rb_link_node(&ins->sort_node, parent, p);
+ rb_insert_color(&ins->sort_node, &sort_tree->root);