Реализация pintos find_bucket()
struct hash
{
size_t elem_cnt; /* Number of elements in table. */
size_t bucket_cnt; /* Number of buckets, a power of 2. */
struct list *buckets; /* Array of `bucket_cnt' lists. */
hash_hash_func *hash; /* Hash function. */
hash_less_func *less; /* Comparison function. */
void *aux; /* Auxiliary data for `hash' and `less'. */
};
static struct list *
find_bucket (struct hash *h, struct hash_elem *e)
{
size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
return &h->buckets[bucket_idx];
}
Я искал структуру данных пинто, но на самом деле ничего не понял.
- Почему bucket_cnt внутри хеша должен быть степенью 2?
- Что значит
size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
Я думаю, что только h->hash(e, h->aux) достаточно для хеширования, но есть еще кое-что, что 'h->bucket_cnt -1'. что это значит и зачем это нужно?