Lines Matching refs: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",
246 /* Hash KEY and return a pointer to the selected bucket.
254 return table->bucket + n;
263 struct hash_entry const *bucket = safe_hasher (table, entry);
266 if (bucket->data == NULL)
269 for (cursor = bucket; cursor; cursor = cursor->next)
290 struct hash_entry const *bucket;
295 for (bucket = table->bucket; ; bucket++)
296 if (! (bucket < table->bucket_limit))
298 else if (bucket->data)
299 return bucket->data;
309 struct hash_entry const *bucket = safe_hasher (table, entry);
312 /* Find next entry in the same bucket. */
313 cursor = bucket;
322 /* Find first entry in any subsequent bucket. */
323 while (++bucket < table->bucket_limit)
324 if (bucket->data)
325 return bucket->data;
340 struct hash_entry const *bucket;
343 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
345 if (bucket->data)
347 for (cursor = bucket; cursor; cursor = cursor->next)
372 struct hash_entry const *bucket;
375 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
377 if (bucket->data)
379 for (cursor = bucket; cursor; cursor = cursor->next)
539 /* Compute the size of the bucket array for the given CANDIDATE and
582 on entries which are already known to hash to the same bucket index,
626 table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
627 if (table->bucket == NULL)
629 table->bucket_limit = table->bucket + table->n_buckets;
655 struct hash_entry *bucket;
657 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
659 if (bucket->data)
664 /* Free the bucket overflow. */
665 for (cursor = bucket->next; cursor; cursor = next)
678 /* Free the bucket head. */
680 table->data_freer (bucket->data);
681 bucket->data = NULL;
682 bucket->next = NULL;
698 struct hash_entry *bucket;
705 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
707 if (bucket->data)
709 for (cursor = bucket; cursor; cursor = cursor->next)
721 /* Free all bucket overflowed entries. */
722 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
724 for (cursor = bucket->next; cursor; cursor = next)
741 free (table->bucket);
747 /* Get a new hash entry for a bucket overflow, possibly by recycling a
772 /* Free a hash entry which was part of some bucket overflow,
785 user data and set *BUCKET_HEAD to the head of the selected bucket.
793 struct hash_entry *bucket = safe_hasher (table, entry);
796 *bucket_head = bucket;
798 /* Test for empty bucket. */
799 if (bucket->data == NULL)
802 /* See if the entry is the first in the bucket. */
803 if (entry == bucket->data || table->comparator (entry, bucket->data))
805 void *data = bucket->data;
809 if (bucket->next)
811 struct hash_entry *next = bucket->next;
813 /* Bump the first overflow entry into the bucket head, then save
815 *bucket = *next;
820 bucket->data = NULL;
827 /* Scan the bucket overflow. */
828 for (cursor = bucket; cursor->next; cursor = cursor->next)
855 entries, saving bucket heads for later, so that no allocations will
862 struct hash_entry *bucket;
865 for (bucket = src->bucket; bucket < src->bucket_limit; bucket++)
866 if (bucket->data)
871 /* Within each bucket, transfer overflow entries first and
872 then the bucket head, to minimize memory pressure. After
874 bucket head, but moving overflow entries first may create
876 get to the bucket head. */
877 for (cursor = bucket->next; cursor; cursor = next)
887 bucket overflow into a bucket overflow. */
893 /* Free an existing entry, when moving from a bucket
894 overflow into a bucket header. */
900 /* Now move the bucket head. Be sure that if we fail due to
903 data = bucket->data;
904 bucket->next = NULL;
911 /* Allocate or recycle an entry, when moving from a bucket
912 header into a bucket overflow. */
924 /* Move from one bucket header to another. */
928 bucket->data = NULL;
954 new_table->bucket = calloc (new_size, sizeof *new_table->bucket);
955 if (new_table->bucket == NULL)
958 new_table->bucket_limit = new_table->bucket + new_size;
968 table collide into a common bucket in the new table. The worst
989 free (table->bucket);
990 table->bucket = new_table->bucket;
999 /* We've allocated new_table->bucket (and possibly some entries),
1017 bucket);
1042 struct hash_entry *bucket;
1045 to indicate "not found", and hash_find_entry uses "bucket->data == NULL"
1046 to indicate an empty bucket. */
1051 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
1086 /* Update the bucket we are interested in. */
1087 if (hash_find_entry (table, entry, &bucket, false) != NULL)
1094 if (bucket->data)
1101 /* Add ENTRY in the overflow of the bucket. */
1104 new_entry->next = bucket->next;
1105 bucket->next = new_entry;
1110 /* Add ENTRY right in the bucket head. */
1112 bucket->data = (void *) entry;
1151 struct hash_entry *bucket;
1153 data = hash_find_entry (table, entry, &bucket, true);
1158 if (!bucket->data)
1214 struct hash_entry *bucket = (struct hash_entry *) table->bucket;
1216 for ( ; bucket < table->bucket_limit; bucket++)
1220 if (bucket)
1221 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1223 for (cursor = bucket; cursor; cursor = cursor->next)
