coreutils/lib/hash.c

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)
283   struct hash_entry const *bucket;
288   for (bucket = table->bucket; ; bucket++)
289     if (! (bucket < table->bucket_limit))
291     else if (bucket->data)
292       return bucket->data;
302   struct hash_entry const *bucket
303     = table->bucket + table->hasher (entry, table->n_buckets);
306   if (! (bucket < table->bucket_limit))
309   /* Find next entry in the same bucket.  */
310   for (cursor = bucket; cursor; cursor = cursor->next)
314   /* Find first entry in any subsequent bucket.  */
315   while (++bucket < table->bucket_limit)
316     if (bucket->data)
317       return bucket->data;
332   struct hash_entry const *bucket;
335   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
337       if (bucket->data)
339           for (cursor = bucket; cursor; cursor = cursor->next)
364   struct hash_entry const *bucket;
367   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
369       if (bucket->data)
371           for (cursor = bucket; cursor; cursor = cursor->next)
531 /* Compute the size of the bucket array for the given CANDIDATE and
574    on entries which are already known to hash to the same bucket index,
618   table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
619   if (table->bucket == NULL)
621   table->bucket_limit = table->bucket + table->n_buckets;
647   struct hash_entry *bucket;
649   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
651       if (bucket->data)
656           /* Free the bucket overflow.  */
657           for (cursor = bucket->next; cursor; cursor = next)
670           /* Free the bucket head.  */
672             table->data_freer (bucket->data);
673           bucket->data = NULL;
674           bucket->next = NULL;
690   struct hash_entry *bucket;
697       for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
699           if (bucket->data)
701               for (cursor = bucket; cursor; cursor = cursor->next)
713   /* Free all bucket overflowed entries.  */
714   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
716       for (cursor = bucket->next; cursor; cursor = next)
733   free (table->bucket);
739 /* Get a new hash entry for a bucket overflow, possibly by recycling a
764 /* Free a hash entry which was part of some bucket overflow,
777    user data and set *BUCKET_HEAD to the head of the selected bucket.
785   struct hash_entry *bucket
786     = table->bucket + table->hasher (entry, table->n_buckets);
789   if (! (bucket < table->bucket_limit))
792   *bucket_head = bucket;
794   /* Test for empty bucket.  */
795   if (bucket->data == NULL)
798   /* See if the entry is the first in the bucket.  */
799   if (entry == bucket->data || table->comparator (entry, bucket->data))
801       void *data = bucket->data;
805           if (bucket->next)
807               struct hash_entry *next = bucket->next;
809               /* Bump the first overflow entry into the bucket head, then save
811               *bucket = *next;
816               bucket->data = NULL;
823   /* Scan the bucket overflow.  */
824   for (cursor = bucket; cursor->next; cursor = cursor->next)
851    entries, saving bucket heads for later, so that no allocations will
858   struct hash_entry *bucket;
861   for (bucket = src->bucket; bucket < src->bucket_limit; bucket++)
862     if (bucket->data)
867         /* Within each bucket, transfer overflow entries first and
868            then the bucket head, to minimize memory pressure.  After
870            bucket head, but moving overflow entries first may create
872            get to the bucket head.  */
873         for (cursor = bucket->next; cursor; cursor = next)
876             new_bucket = (dst->bucket + dst->hasher (data, dst->n_buckets));
886                    bucket overflow into a bucket overflow.  */
892                 /* Free an existing entry, when moving from a bucket
893                    overflow into a bucket header.  */
899         /* Now move the bucket head.  Be sure that if we fail due to
902         data = bucket->data;
903         bucket->next = NULL;
906         new_bucket = (dst->bucket + dst->hasher (data, dst->n_buckets));
913             /* Allocate or recycle an entry, when moving from a bucket
914                header into a bucket overflow.  */
926             /* Move from one bucket header to another.  */
930         bucket->data = NULL;
956   new_table->bucket = calloc (new_size, sizeof *new_table->bucket);
957   if (new_table->bucket == NULL)
960   new_table->bucket_limit = new_table->bucket + new_size;
970      table collide into a common bucket in the new table.  The worst
991       free (table->bucket);
992       table->bucket = new_table->bucket;
1001   /* We've allocated new_table->bucket (and possibly some entries),
1019   free (new_table->bucket);
1033   struct hash_entry *bucket;
1040   if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
1071           /* Update the bucket we are interested in.  */
1072           if (hash_find_entry (table, entry, &bucket, false) != NULL)
1079   if (bucket->data)
1086       /* Add ENTRY in the overflow of the bucket.  */
1089       new_entry->next = bucket->next;
1090       bucket->next = new_entry;
1095   /* Add ENTRY right in the bucket head.  */
1097   bucket->data = (void *) entry;
1112   struct hash_entry *bucket;
1114   data = hash_find_entry (table, entry, &bucket, true);
1119   if (!bucket->data)
1175   struct hash_entry *bucket = (struct hash_entry *) table->bucket;
1177   for ( ; bucket < table->bucket_limit; bucket++)
1181       if (bucket)
1182         printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1184       for (cursor = bucket; cursor; cursor = cursor->next)