Lines Matching full:bucket
54 /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
57 struct hash_entry *bucket;
93 slot. A bucket is the collection of all entries hashing to the same slot.
96 In the ideal case, the length of each bucket is roughly the number of
99 entry is linear in time with the size of the bucket. Consequently, a
119 /* If a deletion empties a bucket and causes the ratio of used buckets to
171 /* Return the length of the longest chain (bucket). */
176 struct hash_entry const *bucket;
179 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
181 if (bucket->data)
183 struct hash_entry const *cursor = bucket;
203 struct hash_entry const *bucket;
207 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
209 if (bucket->data)
211 struct hash_entry const *cursor = bucket;
213 /* Count bucket head. */
217 /* Count bucket overflow. */
242 fprintf (stream, "max bucket length: %lu\n",
252 struct hash_entry const *bucket
253 = table->bucket + table->hasher (entry, table->n_buckets);
256 if (! (bucket < table->bucket_limit))
259 if (bucket->data == NULL)
262 for (cursor = bucket; cursor; cursor = cursor->next)
281 struct hash_entry const *bucket;
286 for (bucket = table->bucket; ; bucket++)
287 if (! (bucket < table->bucket_limit))
289 else if (bucket->data)
290 return bucket->data;
300 struct hash_entry const *bucket
301 = table->bucket + table->hasher (entry, table->n_buckets);
304 if (! (bucket < table->bucket_limit))
307 /* Find next entry in the same bucket. */
308 for (cursor = bucket; cursor; cursor = cursor->next)
312 /* Find first entry in any subsequent bucket. */
313 while (++bucket < table->bucket_limit)
314 if (bucket->data)
315 return bucket->data;
330 struct hash_entry const *bucket;
333 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
335 if (bucket->data)
337 for (cursor = bucket; cursor; cursor = cursor->next)
362 struct hash_entry const *bucket;
365 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
367 if (bucket->data)
369 for (cursor = bucket; cursor; cursor = cursor->next)
529 on entries which are already known to hash to the same bucket index.
574 if (xalloc_oversized (candidate, sizeof *table->bucket))
577 if (xalloc_oversized (table->n_buckets, sizeof *table->bucket))
580 table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
581 table->bucket_limit = table->bucket + table->n_buckets;
607 struct hash_entry *bucket;
609 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
611 if (bucket->data)
616 /* Free the bucket overflow. */
617 for (cursor = bucket->next; cursor; cursor = next)
630 /* Free the bucket head. */
632 (*table->data_freer) (bucket->data);
633 bucket->data = NULL;
634 bucket->next = NULL;
650 struct hash_entry *bucket;
657 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
659 if (bucket->data)
661 for (cursor = bucket; cursor; cursor = cursor->next)
675 /* Free all bucket overflowed entries. */
676 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
678 for (cursor = bucket->next; cursor; cursor = next)
695 free (table->bucket);
701 /* Get a new hash entry for a bucket overflow, possibly by reclying a
726 /* Free a hash entry which was part of some bucket overflow,
739 user data and set *BUCKET_HEAD to the head of the selected bucket.
747 struct hash_entry *bucket
748 = table->bucket + table->hasher (entry, table->n_buckets);
751 if (! (bucket < table->bucket_limit))
754 *bucket_head = bucket;
756 /* Test for empty bucket. */
757 if (bucket->data == NULL)
760 /* See if the entry is the first in the bucket. */
761 if ((*table->comparator) (entry, bucket->data))
763 void *data = bucket->data;
767 if (bucket->next)
769 struct hash_entry *next = bucket->next;
771 /* Bump the first overflow entry into the bucket head, then save
773 *bucket = *next;
778 bucket->data = NULL;
785 /* Scan the bucket overflow. */
786 for (cursor = bucket; cursor->next; cursor = cursor->next)
822 struct hash_entry *bucket;
838 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
839 if (bucket->data)
840 for (cursor = bucket; cursor; cursor = next)
844 = (new_table->bucket
854 if (cursor == bucket)
856 /* Allocate or recycle an entry, when moving from a bucket
857 header into a bucket overflow. */
870 bucket overflow into a bucket overflow. */
877 /* Free an existing entry, when moving from a bucket
878 overflow into a bucket header. Also take care of the
879 simple case of moving from a bucket header into a bucket
883 if (cursor != bucket)
888 free (table->bucket);
889 table->bucket = new_table->bucket;
911 struct hash_entry *bucket;
918 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
923 if (bucket->data)
930 /* Add ENTRY in the overflow of the bucket. */
933 new_entry->next = bucket->next;
934 bucket->next = new_entry;
939 /* Add ENTRY right in the bucket head. */
941 bucket->data = (void *) entry;
986 struct hash_entry *bucket;
988 data = hash_find_entry (table, entry, &bucket, true);
993 if (!bucket->data)
1031 struct hash_entry const *bucket;
1033 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1037 if (bucket)
1038 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1040 for (cursor = bucket; cursor; cursor = cursor->next)
