- struct idev_node *old_buckets = tbl->buckets;
- int size = tbl->size * 2;
- int i;
-
- if (!(tbl->buckets = new_array(struct idev_node, size)))
- out_of_memory("ihash_create");
- memset(tbl->buckets, 0, size * sizeof (struct idev_node));
- tbl->size = size;
- tbl->entries = 0;
-
- for (i = size / 2; i-- > 0; ) {
- int64 key = old_buckets[i].key;
- if (key == 0)
- continue;
- ihash_node(tbl, key)->data = old_buckets[i].data;
- }
-
- free(old_buckets);
-}
-
-/* This returns the node for the indicated key, either newly created,
- * or already existing. */
-static struct idev_node *ihash_node(struct ihash_table *tbl, int64 key)
-{
- uint32 bkt;
-
- if (tbl->entries > HASH_LOAD_LIMIT(tbl->size))
- expand_ihash(tbl);
-
-#if SIZEOF_INT64 < 8
- /* Based on Jenkins One-at-a-time hash. */
- {
- uchar *keyp = (uchar*)&key;
- int i;
-
- for (bkt = 0, i = 0; i < SIZEOF_INT64; i++) {
- bkt += keyp[i];
- bkt += (bkt << 10);
- bkt ^= (bkt >> 6);
- }
- bkt += (bkt << 3);
- bkt ^= (bkt >> 11);
- bkt += (bkt << 15);
- }
-#else
-#define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
- /* Based on Jenkins hashword() from lookup3.c. */
- {
- uint32 a, b, c;
-
- /* Set up the internal state */
- a = b = c = 0xdeadbeef + (8 << 2);
-
- b += (uint32)(key >> 32);
- a += (uint32)key;
- c ^= b; c -= rot(b, 14);
- a ^= c; a -= rot(c, 11);
- b ^= a; b -= rot(a, 25);
- c ^= b; c -= rot(b, 16);
- a ^= c; a -= rot(c, 4);
- b ^= a; b -= rot(a, 14);
- c ^= b; c -= rot(b, 24);
- bkt = c;
- }
-#endif
-
- /* If it already exists, return it. */
- while (1) {
- bkt &= tbl->size - 1;
- if (tbl->buckets[bkt].key == key)
- return &tbl->buckets[bkt];
- if (tbl->buckets[bkt].key == 0)
- break;
- bkt++;
- }
-
- /* Otherwise, take over this empty spot and then return it. */
- tbl->buckets[bkt].key = key;
- tbl->entries++;
- return &tbl->buckets[bkt];
-}
-
-struct idev_node *idev_node(int64 dev, int64 ino)
-{
- static struct idev_node *dev_node = NULL;
- struct ihash_table *tbl;