-/*
- * We use a hash table of size s=2^uid_hash_bits to map the uids into the
- * interval [0..s]. Hash collisions are treated by open addressing, i.e.
- * unused slots in the table are used to store different uids that hash to the
- * same slot.
- *
- * If a hash collision occurs, different slots are successively probed in order
- * to find an unused slot for the new uid. Probing is implemented via a second
- * hash function that maps the uid to h=(uid * PRIME2) | 1, which is always an
- * odd number.
- *
- * An odd number is sufficient to make sure each entry of the hash table gets
- * probed for probe_num between 0 and s-1 because s is a power of two, hence
- * the second hash value has never a common divisor with the hash table size.
- * IOW: h is invertible in the ring [0..s].
- */
-static uint32_t double_hash(uint32_t uid, uint32_t probe_num)
-{
- return (uid * PRIME1 + ((uid * PRIME2) | 1) * probe_num)
- % uid_hash_table_size;
-}
-
-static int uid_is_admissible(uint32_t uid, struct uid_range *urs)
-{
- struct uid_range *ur;
- int ret = 1;
-
- if (!urs) /* empty array means all uids are allowed */
- return 1;
- FOR_EACH_UID_RANGE(ur, urs)
- if (ur->low <= uid && ur->high >= uid)
- goto out;
- ret = 0;
-out:
- DEBUG_LOG("uid %u is %sadmissible\n", (unsigned)uid,
- ret? "" : "not ");
- return ret;
-}
-
-int search_uid(uint32_t uid, struct uid_range *urs,
- enum search_uid_flags flags, struct user_info **ui_ptr)
-{
- uint32_t p;
-
- for (p = 0; p < uid_hash_table_size; p++) {
- struct user_info *ui = uid_hash_table + double_hash(uid, p);
-
- if (!ui_used(ui)) {
- int ret;
- if (!flags)
- return -E_BAD_UID;
- ui->uid = uid;
- ui->flags |= UI_FL_SLOT_USED;
- if (!uid_is_admissible(uid, urs))
- return 0;
- ui->flags |= UI_FL_ADMISSIBLE;
- ret = open_user_table(ui, flags & CREATE_USER_TABLE);
- if (ret < 0)
- return ret;
-
- if (ui_ptr)
- *ui_ptr = ui;
- return 1;
- }
- if (ui->uid != uid)
- continue;
- if (ui_ptr)
- *ui_ptr = ui;
- return 0;
- }
- return flags? -E_HASH_TABLE_OVERFLOW : -E_BAD_UID;
-}
-
-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 *))
-{
- qsort(uid_hash_table, uid_hash_table_size, sizeof(struct user_info),
- comp);
-}
-