Fix sorting of the uid hash table.
authorAndre Noll <maan@systemlinux.org>
Sun, 9 Nov 2008 14:33:16 +0000 (15:33 +0100)
committerAndre Noll <maan@systemlinux.org>
Sun, 9 Nov 2008 14:33:16 +0000 (15:33 +0100)
We must not blindy sort the whole table because in interactive mode
this table may be modified by later commands and lookup_uid() gets
confused if the entries have been permuted. So introduce
uid_hash_table_sort_idx, an array of indices that describes the current
sorting of the hash table. The order of the entries in the table itsself
never gets changed any more with this patch.

Also, simplify the uid comparators by introducing a wrapper that does
the casts which were previously contained in each comparator.

select.c
user.c
user.h

index a3519fe..f200953 100644 (file)
--- a/select.c
+++ b/select.c
@@ -366,10 +366,10 @@ static int print_user_summary_line(struct user_info *ui, void *data)
        return ret;
 }
 
-static int name_comp(const void *a, const void *b)
+static int name_comp(struct user_info *a, struct user_info *b)
 {
-       char *x = ((struct user_info *)a)->pw_name;
-       char *y = ((struct user_info *)b)->pw_name;
+       char *x = a->pw_name;
+       char *y = b->pw_name;
 
        if (!x)
                return 1;
@@ -378,55 +378,57 @@ static int name_comp(const void *a, const void *b)
        return strcmp(x, y);
 }
 
-static int uid_comp(const void *a, const void *b)
+static int uid_comp(struct user_info *a, struct user_info *b)
 {
-       return -NUM_COMPARE(((struct user_info *)a)->uid,
-               ((struct user_info *)b)->uid);
+       return -NUM_COMPARE(a->uid, b->uid);
 }
 
-static int dir_count_comp(const void *a, const void *b)
+static int dir_count_comp(struct user_info *a, struct user_info *b)
 {
-       return NUM_COMPARE(((struct user_info *)a)->dirs,
-               ((struct user_info *)b)->dirs);
+       return NUM_COMPARE(a->dirs, b->dirs);
 }
 
-static int file_count_comp(const void *a, const void *b)
+static int file_count_comp(struct user_info *a, struct user_info *b)
 {
-       return NUM_COMPARE(((struct user_info *)a)->files,
-               ((struct user_info *)b)->files);
+       return NUM_COMPARE(a->files, b->files);
 }
 
-static int size_comp(const void *a, const void *b)
+static int size_comp(struct user_info *a, struct user_info *b)
 {
-       return NUM_COMPARE(((struct user_info *)a)->bytes,
-               ((struct user_info *)b)->bytes);
+       return NUM_COMPARE(a->bytes, b->bytes);
 }
 
 static int print_user_summary(struct format_info *fi)
 {
-       /*
-        * The comparators for sorting the user summary.
-        *
-        * This is an array of pointers to functions taking two constant void *
-        * pointers and returning an int.
-        */
-       int (*summary_comparators[])(const void *, const void *) = {
-               [user_summary_sort_arg_name] = name_comp,
-               [user_summary_sort_arg_uid] = uid_comp,
-               [user_summary_sort_arg_dir_count] = dir_count_comp,
-               [user_summary_sort_arg_file_count] = file_count_comp,
-               [user_summary_sort_arg_size] = size_comp,
-       };
+       int ret;
+       int (*comp)(struct user_info *a, struct user_info *b);
 
        if (!select_conf.no_headers_given) {
-               int ret = output("User summary\n");
+               ret = output("User summary\n");
                if (ret < 0)
                        return ret;
        }
-       int ret = for_each_admissible_user(compute_user_summary, fi);
+       ret = for_each_admissible_user(compute_user_summary, fi);
        if (ret < 0)
                return ret;
-       sort_hash_table(summary_comparators[select_conf.user_summary_sort_arg]);
+       switch (select_conf.user_summary_sort_arg) {
+       case user_summary_sort_arg_name:
+               comp = name_comp;
+               break;
+       case user_summary_sort_arg_uid:
+               comp = uid_comp;
+               break;
+       case user_summary_sort_arg_dir_count:
+               comp = dir_count_comp;
+               break;
+       case user_summary_sort_arg_file_count:
+               comp = file_count_comp;
+               break;
+       case user_summary_sort_arg_size:
+               comp = size_comp;
+               break;
+       }
+       sort_hash_table(comp);
        return for_each_admissible_user(print_user_summary_line, fi);
 }
 
diff --git a/user.c b/user.c
index 3f368e2..1bdd34b 100644 (file)
--- a/user.c
+++ b/user.c
@@ -50,6 +50,9 @@ static struct user_info *uid_hash_table;
 /** This is always a power of two. It is set in create_hash_table(). */
 static uint32_t uid_hash_table_size;
 
+/* Array of indices to the entries of \a uid_hash_table. */
+static int *uid_hash_table_sort_idx;
+
 /** The number of used slots in the hash table. */
 static uint32_t num_uids = 0;
 
@@ -276,11 +279,13 @@ err:
 int for_each_admissible_user(int (*func)(struct user_info *, void *),
                void *data)
 {
-       struct user_info *ui;
+       int i;
 
        assert(uid_hash_table);
-       FOR_EACH_USER(ui) {
+       for (i = 0; i < uid_hash_table_size; i++) {
                int ret;
+               struct user_info *ui = uid_hash_table +
+                       uid_hash_table_sort_idx[i];
 
                if (!ui_used(ui) || !ui_admissible(ui))
                        continue;
@@ -296,9 +301,14 @@ int for_each_admissible_user(int (*func)(struct user_info *, void *),
 
 void create_hash_table(unsigned bits)
 {
+       int i;
+
        uid_hash_table_size = 1 << bits;
        uid_hash_table = adu_calloc(uid_hash_table_size *
                sizeof(struct user_info));
+       uid_hash_table_sort_idx = adu_malloc(uid_hash_table_size * sizeof(int));
+       for (i = 0; i < uid_hash_table_size; i++)
+               uid_hash_table_sort_idx[i] = i;
 }
 
 void close_user_tables(void)
@@ -330,6 +340,8 @@ void close_user_tables(void)
        }
        free(uid_hash_table);
        uid_hash_table = NULL;
+       free(uid_hash_table_sort_idx);
+       uid_hash_table_sort_idx = NULL;
 }
 
 /*
@@ -387,10 +399,20 @@ static char *get_uid_list_name(void)
        return make_message("%s/uid_list", conf.database_dir_arg);
 }
 
-void sort_hash_table(int (*comp)(const void *, const void *))
+static int (*hash_table_comparator)(struct user_info *a, struct user_info *b);
+
+static int comp_wrapper(const void *a, const void *b)
+{
+       struct user_info *x = uid_hash_table + *(unsigned *)a;
+       struct user_info *y = uid_hash_table + *(unsigned *)b;
+       return hash_table_comparator(x, y);
+}
+
+void sort_hash_table(int (*comp)(struct user_info *, struct user_info *))
 {
-       qsort(uid_hash_table, uid_hash_table_size, sizeof(struct user_info),
-               comp);
+       hash_table_comparator = comp;
+       qsort(uid_hash_table_sort_idx, uid_hash_table_size,
+               sizeof(*uid_hash_table_sort_idx), comp_wrapper);
 }
 
 int open_admissible_user_tables(struct uid_range *admissible_uids)
diff --git a/user.h b/user.h
index 7a06876..d317023 100644 (file)
--- a/user.h
+++ b/user.h
@@ -38,7 +38,7 @@ int read_uid_file(void);
 int write_uid_file(void);
 
 void create_hash_table(unsigned bits);
-void sort_hash_table(int (*comp)(const void *, const void *));
+void sort_hash_table(int (*comp)(struct user_info *, struct user_info *));
 
 int for_each_admissible_user(int (*func)(struct user_info *, void *),
                void *data);