1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* hash - hashing table processing. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 3cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004 Free 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Software Foundation, Inc. 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 6cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Written by Jim Meyering, 1992. 7cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 8cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This program is free software; you can redistribute it and/or modify 9cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it under the terms of the GNU General Public License as published by 10cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the Free Software Foundation; either version 2, or (at your option) 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project any later version. 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This program is distributed in the hope that it will be useful, 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should have received a copy of the GNU General Public License 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project along with this program; if not, write to the Free Software Foundation, 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* A generic hash table package. */ 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project of malloc. If you change USE_OBSTACK, you have to recompile! */ 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifdef HAVE_CONFIG_H 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# include <config.h> 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "hash.h" 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "xalloc.h" 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <limits.h> 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdio.h> 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <stdlib.h> 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# include "obstack.h" 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# ifndef obstack_chunk_alloc 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# define obstack_chunk_alloc malloc 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# endif 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# ifndef obstack_chunk_free 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# define obstack_chunk_free free 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# endif 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifndef SIZE_MAX 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# define SIZE_MAX ((size_t) -1) 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct hash_table 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1, 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project are not empty, there are N_ENTRIES active entries in the table. */ 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket; 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket_limit; 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_buckets; 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_buckets_used; 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_entries; 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Tuning arguments, kept in a physicaly separate structure. */ 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project const Hash_tuning *tuning; 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Three functions are given to `hash_initialize', see the documentation 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project block for this function. In a word, HASHER randomizes a user entry 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project into a number up from 0 up to some maximum minus 1; COMPARATOR returns 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project true if two user entries compare equally; and DATA_FREER is the cleanup 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project function for a user entry. */ 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_hasher hasher; 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_comparator comparator; 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_data_freer data_freer; 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* A linked list of freed struct hash_entry structs. */ 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *free_entry_list; 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Whenever obstacks are used, it is possible to allocate all overflowed 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entries into a single stack, so they all can be freed in a single 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project operation. It is not clear if the speedup is worth the trouble. */ 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct obstack entry_stack; 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project }; 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* A hash table contains many internal entries, each holding a pointer to 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project some user provided data (also called a user entry). An entry indistinctly 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project refers to both the internal entry and its associated user entry. A user 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry contents may be hashed by a randomization function (the hashing 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project function, or just `hasher' for short) into a number (or `slot') between 0 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project and the current table size. At each slot position in the hash table, 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project starts a linked chain of entries for which the user data all hash to this 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project slot. A bucket is the collection of all entries hashing to the same slot. 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project A good `hasher' function will distribute entries rather evenly in buckets. 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project In the ideal case, the length of each bucket is roughly the number of 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entries divided by the table size. Finding the slot for a data is usually 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project done in constant time by the `hasher', and the later finding of a precise 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry is linear in time with the size of the bucket. Consequently, a 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project larger hash table size (that is, a larger number of buckets) is prone to 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project yielding shorter chains, *given* the `hasher' function behaves properly. 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Long buckets slow down the lookup algorithm. One might use big hash table 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sizes in hope to reduce the average length of buckets, but this might 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project become inordinate, as unused slots in the hash table take some space. The 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project best bet is to make sure you are using a good `hasher' function (beware 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project that those are not that easy to write! :-), and to use a table size 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project larger than the actual number of entries. */ 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* If an insertion makes the ratio of nonempty buckets to table size larger 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project than the growth threshold (a number between 0.0 and 1.0), then increase 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the table size by multiplying by the growth factor (a number greater than 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1.0). The growth threshold defaults to 0.8, and the growth factor 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project defaults to 1.414, meaning that the table will have doubled its size 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project every second time 80% of the buckets get used. */ 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define DEFAULT_GROWTH_THRESHOLD 0.8 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define DEFAULT_GROWTH_FACTOR 1.414 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* If a deletion empties a bucket and causes the ratio of used buckets to 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table size to become smaller than the shrink threshold (a number between 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project number greater than the shrink threshold but smaller than 1.0). The shrink 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project threshold and factor default to 0.0 and 1.0, meaning that the table never 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project shrinks. */ 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define DEFAULT_SHRINK_THRESHOLD 0.0 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#define DEFAULT_SHRINK_FACTOR 1.0 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Use this to initialize or reset a TUNING structure to 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project some sensible values. */ 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic const Hash_tuning default_tuning = 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DEFAULT_SHRINK_THRESHOLD, 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DEFAULT_SHRINK_FACTOR, 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DEFAULT_GROWTH_THRESHOLD, 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project DEFAULT_GROWTH_FACTOR, 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project false 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project }; 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Information and lookup. */ 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* The following few functions provide information about the overall hash 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table organization: the number of entries, number of buckets and maximum 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project length of buckets. */ 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 145cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return the number of buckets in the hash table. The table size, the total 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project number of buckets (used plus unused), or the maximum number of slots, are 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the same quantity. */ 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_n_buckets (const Hash_table *table) 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return table->n_buckets; 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 154cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 155cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return the number of slots in use (non-empty buckets). */ 156cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 157cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 158cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_n_buckets_used (const Hash_table *table) 159cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 160cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return table->n_buckets_used; 161cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 162cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 163cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return the number of active entries. */ 164cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 165cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_n_entries (const Hash_table *table) 167cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 168cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return table->n_entries; 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return the length of the longest chain (bucket). */ 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_max_bucket_length (const Hash_table *table) 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket; 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t max_bucket_length = 0; 178cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 182cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *cursor = bucket; 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t bucket_length = 1; 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 186cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (cursor = cursor->next, cursor) 187cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket_length++; 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket_length > max_bucket_length) 190cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project max_bucket_length = bucket_length; 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return max_bucket_length; 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Do a mild validation of a hash table, by traversing it and checking two 198cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project statistics. */ 199cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbool 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_table_ok (const Hash_table *table) 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket; 204cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_buckets_used = 0; 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_entries = 0; 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 207cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 210cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 211cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *cursor = bucket; 212cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 213cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Count bucket head. */ 214cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project n_buckets_used++; 215cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project n_entries++; 216cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 217cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Count bucket overflow. */ 218cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (cursor = cursor->next, cursor) 219cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project n_entries++; 220cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 221cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 222cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 223cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries) 224cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 225cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 226cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 227cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 228cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 229cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 230cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_print_statistics (const Hash_table *table, FILE *stream) 231cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 232cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_entries = hash_get_n_entries (table); 233cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_buckets = hash_get_n_buckets (table); 234cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t n_buckets_used = hash_get_n_buckets_used (table); 235cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t max_bucket_length = hash_get_max_bucket_length (table); 236cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 237cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stream, "# entries: %lu\n", (unsigned long int) n_entries); 238cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stream, "# buckets: %lu\n", (unsigned long int) n_buckets); 239cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stream, "# buckets used: %lu (%.2f%%)\n", 240cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (unsigned long int) n_buckets_used, 241cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (100.0 * n_buckets_used) / n_buckets); 242cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (stream, "max bucket length: %lu\n", 243cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (unsigned long int) max_bucket_length); 244cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 245cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 246cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* If ENTRY matches an entry already in the hash table, return the 247cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry from the table. Otherwise, return NULL. */ 248cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 249cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid * 250cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_lookup (const Hash_table *table, const void *entry) 251cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 252cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket 253cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project = table->bucket + table->hasher (entry, table->n_buckets); 254cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *cursor; 255cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 256cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (! (bucket < table->bucket_limit)) 257cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 258cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 259cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data == NULL) 260cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 261cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 262cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = cursor->next) 263cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->comparator (entry, cursor->data)) 264cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return cursor->data; 265cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 266cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 267cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 268cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 269cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Walking. */ 270cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 271cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* The functions in this page traverse the hash table and process the 272cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project contained entries. For the traversal to work properly, the hash table 273cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project should not be resized nor modified while any particular entry is being 274cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project processed. In particular, entries should not be added or removed. */ 275cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 276cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return the first data in the table, or NULL if the table is empty. */ 277cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 278cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid * 279cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_first (const Hash_table *table) 280cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 281cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket; 282cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 283cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->n_entries == 0) 284cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 285cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 286cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; ; bucket++) 287cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (! (bucket < table->bucket_limit)) 288cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 289cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else if (bucket->data) 290cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bucket->data; 291cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 292cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 293cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return the user data for the entry following ENTRY, where ENTRY has been 294cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project returned by a previous call to either `hash_get_first' or `hash_get_next'. 295cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Return NULL if there are no more entries. */ 296cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 297cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid * 298cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_next (const Hash_table *table, const void *entry) 299cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 300cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket 301cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project = table->bucket + table->hasher (entry, table->n_buckets); 302cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *cursor; 303cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 304cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (! (bucket < table->bucket_limit)) 305cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 306cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 307cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find next entry in the same bucket. */ 308cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = cursor->next) 309cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (cursor->data == entry && cursor->next) 310cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return cursor->next->data; 311cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 312cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Find first entry in any subsequent bucket. */ 313cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (++bucket < table->bucket_limit) 314cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 315cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return bucket->data; 316cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 317cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* None found. */ 318cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 319cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 320cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 321cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Fill BUFFER with pointers to active user entries in the hash table, then 322cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return the number of pointers copied. Do not copy more than BUFFER_SIZE 323cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project pointers. */ 324cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 325cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 326cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_get_entries (const Hash_table *table, void **buffer, 327cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t buffer_size) 328cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 329cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t counter = 0; 330cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket; 331cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *cursor; 332cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 333cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 334cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 335cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 336cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 337cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = cursor->next) 338cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 339cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (counter >= buffer_size) 340cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return counter; 341cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project buffer[counter++] = cursor->data; 342cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 343cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 344cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 345cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 346cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return counter; 347cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 348cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 349cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Call a PROCESSOR function for each entry of a hash table, and return the 350cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project number of entries for which the processor function returned success. A 351cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project pointer to some PROCESSOR_DATA which will be made available to each call to 352cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the processor function. The PROCESSOR accepts two arguments: the first is 353cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the user entry being walked into, the second is the value of PROCESSOR_DATA 354cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project as received. The walking continue for as long as the PROCESSOR function 355cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project returns nonzero. When it returns zero, the walking is interrupted. */ 356cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 357cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 358cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_do_for_each (const Hash_table *table, Hash_processor processor, 359cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void *processor_data) 360cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 361cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t counter = 0; 362cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket; 363cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *cursor; 364cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 365cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 366cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 367cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 368cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 369cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = cursor->next) 370cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 371cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!(*processor) (cursor->data, processor_data)) 372cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return counter; 373cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project counter++; 374cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 375cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 376cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 377cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 378cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return counter; 379cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 380cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 381cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Allocation and clean-up. */ 382cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 383cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1. 384cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This is a convenience routine for constructing other hashing functions. */ 385cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 386cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_DIFF_HASH 387cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 388cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see 389cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm, 390cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash 391cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project algorithms tend to be domain-specific, so what's good for [diffutils'] io.c 392cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project may not be good for your application." */ 393cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 394cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 395cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_string (const char *string, size_t n_buckets) 396cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 397cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# define ROTATE_LEFT(Value, Shift) \ 398cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift))) 399cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# define HASH_ONE_CHAR(Value, Byte) \ 400cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ((Byte) + ROTATE_LEFT (Value, 7)) 401cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 402cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t value = 0; 403cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned char ch; 404cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 405cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; (ch = *string); string++) 406cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project value = HASH_ONE_CHAR (value, ch); 407cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return value % n_buckets; 408cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 409cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# undef ROTATE_LEFT 410cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# undef HASH_ONE_CHAR 411cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 412cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 413cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#else /* not USE_DIFF_HASH */ 414cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 415cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* This one comes from `recode', and performs a bit better than the above as 416cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project per a few experiments. It is inspired from a hashing routine found in the 417cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project very old Cyber `snoop', itself written in typical Greg Mansfield style. 418cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (By the way, what happened to this excellent man? Is he still alive?) */ 419cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 420cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t 421cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_string (const char *string, size_t n_buckets) 422cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 423cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t value = 0; 424cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project unsigned char ch; 425cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 426cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (; (ch = *string); string++) 427cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project value = (value * 31 + ch) % n_buckets; 428cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return value; 429cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 430cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 431cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif /* not USE_DIFF_HASH */ 432cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 433cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd 434cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project number at least equal to 11. */ 435cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 436cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 437cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectis_prime (size_t candidate) 438cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 439cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t divisor = 3; 440cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t square = divisor * divisor; 441cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 442cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (square < candidate && (candidate % divisor)) 443cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 444cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project divisor++; 445cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project square += 4 * divisor; 446cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project divisor++; 447cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 448cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 449cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return (candidate % divisor ? true : false); 450cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 451cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 452cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Round a given CANDIDATE number up to the nearest prime, and return that 453cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project prime. Primes lower than 10 are merely skipped. */ 454cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 455cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic size_t 456cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnext_prime (size_t candidate) 457cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 458cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Skip small primes. */ 459cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (candidate < 10) 460cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project candidate = 10; 461cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 462cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Make it definitely odd. */ 463cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project candidate |= 1; 464cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 465cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (!is_prime (candidate)) 466cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project candidate += 2; 467cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 468cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return candidate; 469cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 470cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 471cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 472cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_reset_tuning (Hash_tuning *tuning) 473cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 474cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *tuning = default_tuning; 475cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 476cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 477cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* For the given hash TABLE, check the user supplied tuning structure for 478cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project reasonable values, and return true if there is no gross error with it. 479cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Otherwise, definitively reset the TUNING field to some acceptable default 480cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project in the hash table (that is, the user loses the right of further modifying 481cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tuning arguments), and return false. */ 482cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 483cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic bool 484cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectcheck_tuning (Hash_table *table) 485cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 486cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project const Hash_tuning *tuning = table->tuning; 487cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 488cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Be a bit stricter than mathematics would require, so that 489cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rounding errors in size calculations do not cause allocations to 490cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fail to grow or shrink as they should. The smallest allocation 491cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project is 11 (due to next_prime's algorithm), so an epsilon of 0.1 492cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project should be good enough. */ 493cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project float epsilon = 0.1f; 494cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 495cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (epsilon < tuning->growth_threshold 496cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && tuning->growth_threshold < 1 - epsilon 497cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && 1 + epsilon < tuning->growth_factor 498cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && 0 <= tuning->shrink_threshold 499cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && tuning->shrink_threshold + epsilon < tuning->shrink_factor 500cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && tuning->shrink_factor <= 1 501cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && tuning->shrink_threshold + epsilon < tuning->growth_threshold) 502cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 503cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 504cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->tuning = &default_tuning; 505cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 506cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 507cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 508cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Allocate and return a new hash table, or NULL upon failure. The initial 509cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project number of buckets is automatically selected so as to _guarantee_ that you 510cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project may insert at least CANDIDATE different user entries before any growth of 511cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the hash table size occurs. So, if have a reasonably tight a-priori upper 512cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bound on the number of entries you intend to insert in the hash table, you 513cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project may save some table memory and insertion time, by specifying it here. If 514cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE 515cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project argument has its meaning changed to the wanted number of buckets. 516cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 517cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project TUNING points to a structure of user-supplied values, in case some fine 518cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tuning is wanted over the default behavior of the hasher. If TUNING is 519cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project NULL, the default tuning parameters are used instead. 520cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 521cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project The user-supplied HASHER function should be provided. It accepts two 522cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a 523cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project slot number for that entry which should be in the range 0..TABLE_SIZE-1. 524cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This slot number is then returned. 525cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 526cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project The user-supplied COMPARATOR function should be provided. It accepts two 527cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project arguments pointing to user data, it then returns true for a pair of entries 528cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project that compare equal, or false otherwise. This function is internally called 529cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project on entries which are already known to hash to the same bucket index. 530cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 531cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project The user-supplied DATA_FREER function, when not NULL, may be later called 532cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project with the user data as an argument, just before the entry containing the 533cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project data gets freed. This happens from within `hash_free' or `hash_clear'. 534cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should specify this function only if you want these functions to free 535cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project all of your `data' data. This is typically the case when your data is 536cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project simply an auxiliary struct that you have malloc'd to aggregate several 537cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project values. */ 538cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 539cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectHash_table * 540cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_initialize (size_t candidate, const Hash_tuning *tuning, 541cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_hasher hasher, Hash_comparator comparator, 542cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_data_freer data_freer) 543cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 544cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_table *table; 545cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 546cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (hasher == NULL || comparator == NULL) 547cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 548cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 549cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table = malloc (sizeof *table); 550cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table == NULL) 551cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 552cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 553cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!tuning) 554cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project tuning = &default_tuning; 555cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->tuning = tuning; 556cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!check_tuning (table)) 557cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 558cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Fail if the tuning options are invalid. This is the only occasion 559cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project when the user gets some feedback about it. Once the table is created, 560cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if the user provides invalid tuning options, we silently revert to 561cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project using the defaults, and ignore further request to change the tuning 562cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project options. */ 563cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto fail; 564cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 565cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 566cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!tuning->is_n_buckets) 567cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 568cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project float new_candidate = candidate / tuning->growth_threshold; 569cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (SIZE_MAX <= new_candidate) 570cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto fail; 571cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project candidate = new_candidate; 572cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 573cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 574cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (xalloc_oversized (candidate, sizeof *table->bucket)) 575cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto fail; 576cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets = next_prime (candidate); 577cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (xalloc_oversized (table->n_buckets, sizeof *table->bucket)) 578cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project goto fail; 579cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 580cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->bucket = calloc (table->n_buckets, sizeof *table->bucket); 581cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->bucket_limit = table->bucket + table->n_buckets; 582cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets_used = 0; 583cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_entries = 0; 584cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 585cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->hasher = hasher; 586cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->comparator = comparator; 587cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->data_freer = data_freer; 588cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 589cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->free_entry_list = NULL; 590cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 591cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_init (&table->entry_stack); 592cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 593cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return table; 594cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 595cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fail: 596cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (table); 597cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 598cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 599cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 600cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Make all buckets empty, placing any chained entries on the free list. 601cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Apply the user-specified function data_freer (if any) to the datas of any 602cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project affected entries. */ 603cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 604cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 605cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_clear (Hash_table *table) 606cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 607cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket; 608cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 609cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 610cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 611cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 612cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 613cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *cursor; 614cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *next; 615cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 616cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Free the bucket overflow. */ 617cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket->next; cursor; cursor = next) 618cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 619cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->data_freer) 620cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (*table->data_freer) (cursor->data); 621cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project cursor->data = NULL; 622cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 623cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = cursor->next; 624cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Relinking is done one entry at a time, as it is to be expected 625cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project that overflows are either rare or short. */ 626cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project cursor->next = table->free_entry_list; 627cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->free_entry_list = cursor; 628cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 629cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 630cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Free the bucket head. */ 631cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->data_freer) 632cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (*table->data_freer) (bucket->data); 633cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket->data = NULL; 634cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket->next = NULL; 635cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 636cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 637cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 638cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets_used = 0; 639cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_entries = 0; 640cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 641cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 642cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Reclaim all storage associated with a hash table. If a data_freer 643cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project function has been supplied by the user when the hash table was created, 644cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project this function applies it to the data of each entry before freeing that 645cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry. */ 646cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 647cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 648cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_free (Hash_table *table) 649cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 650cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket; 651cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *cursor; 652cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *next; 653cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 654cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Call the user data_freer function. */ 655cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->data_freer && table->n_entries) 656cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 657cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 658cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 659cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 660cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 661cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = cursor->next) 662cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 663cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (*table->data_freer) (cursor->data); 664cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 665cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 666cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 667cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 668cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 669cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 670cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 671cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_free (&table->entry_stack, NULL); 672cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 673cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#else 674cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 675cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Free all bucket overflowed entries. */ 676cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 677cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 678cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket->next; cursor; cursor = next) 679cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 680cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = cursor->next; 681cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (cursor); 682cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 683cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 684cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 685cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Also reclaim the internal list of previously freed entries. */ 686cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = table->free_entry_list; cursor; cursor = next) 687cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 688cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = cursor->next; 689cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (cursor); 690cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 691cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 692cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 693cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 694cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Free the remainder of the hash table structure. */ 695cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (table->bucket); 696cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (table); 697cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 698cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 699cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Insertion and deletion. */ 700cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 701cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Get a new hash entry for a bucket overflow, possibly by reclying a 702cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project previously freed one. If this is not possible, allocate a new one. */ 703cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 704cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic struct hash_entry * 705cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectallocate_entry (Hash_table *table) 706cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 707cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *new; 708cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 709cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->free_entry_list) 710cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 711cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new = table->free_entry_list; 712cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->free_entry_list = new->next; 713cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 714cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 715cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 716cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 717cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new = obstack_alloc (&table->entry_stack, sizeof *new); 718cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#else 719cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new = malloc (sizeof *new); 720cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 721cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 722cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 723cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return new; 724cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 725cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 726cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Free a hash entry which was part of some bucket overflow, 727cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project saving it for later recycling. */ 728cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 729cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 730cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectfree_entry (Hash_table *table, struct hash_entry *entry) 731cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 732cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry->data = NULL; 733cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry->next = table->free_entry_list; 734cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->free_entry_list = entry; 735cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 736cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 737cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* This private function is used to help with insertion and deletion. When 738cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ENTRY matches an entry in the table, return a pointer to the corresponding 739cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project user data and set *BUCKET_HEAD to the head of the selected bucket. 740cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in 741cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the table, unlink the matching entry. */ 742cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 743cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void * 744cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_find_entry (Hash_table *table, const void *entry, 745cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry **bucket_head, bool delete) 746cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 747cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket 748cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project = table->bucket + table->hasher (entry, table->n_buckets); 749cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *cursor; 750cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 751cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (! (bucket < table->bucket_limit)) 752cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 753cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 754cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *bucket_head = bucket; 755cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 756cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Test for empty bucket. */ 757cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data == NULL) 758cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 759cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 760cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* See if the entry is the first in the bucket. */ 761cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((*table->comparator) (entry, bucket->data)) 762cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 763cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void *data = bucket->data; 764cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 765cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (delete) 766cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 767cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->next) 768cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 769cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *next = bucket->next; 770cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 771cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Bump the first overflow entry into the bucket head, then save 772cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the previous first overflow entry for later recycling. */ 773cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *bucket = *next; 774cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free_entry (table, next); 775cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 776cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 777cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 778cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket->data = NULL; 779cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 780cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 781cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 782cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return data; 783cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 784cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 785cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Scan the bucket overflow. */ 786cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor->next; cursor = cursor->next) 787cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 788cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((*table->comparator) (entry, cursor->next->data)) 789cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 790cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void *data = cursor->next->data; 791cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 792cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (delete) 793cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 794cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *next = cursor->next; 795cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 796cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Unlink the entry to delete, then save the freed entry for later 797cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project recycling. */ 798cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project cursor->next = next->next; 799cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free_entry (table, next); 800cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 801cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 802cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return data; 803cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 804cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 805cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 806cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* No entry found. */ 807cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 808cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 809cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 810cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* For an already existing hash table, change the number of buckets through 811cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project specifying CANDIDATE. The contents of the hash table are preserved. The 812cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new number of buckets is automatically selected so as to _guarantee_ that 813cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the table may receive at least CANDIDATE different user entries, including 814cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project those already in the table, before any other growth of the hash table size 815cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the 816cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project exact number of buckets desired. */ 817cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 818cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbool 819cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_rehash (Hash_table *table, size_t candidate) 820cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 821cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hash_table *new_table; 822cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket; 823cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *cursor; 824cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *next; 825cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 826cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_table = hash_initialize (candidate, table->tuning, table->hasher, 827cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->comparator, table->data_freer); 828cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (new_table == NULL) 829cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 830cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 831cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Merely reuse the extra old space into the new table. */ 832cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 833cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_free (&new_table->entry_stack, NULL); 834cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_table->entry_stack = table->entry_stack; 835cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 836cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_table->free_entry_list = table->free_entry_list; 837cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 838cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 839cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 840cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = next) 841cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 842cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void *data = cursor->data; 843cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *new_bucket 844cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project = (new_table->bucket 845cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project + new_table->hasher (data, new_table->n_buckets)); 846cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 847cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (! (new_bucket < new_table->bucket_limit)) 848cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 849cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 850cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project next = cursor->next; 851cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 852cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (new_bucket->data) 853cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 854cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (cursor == bucket) 855cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 856cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Allocate or recycle an entry, when moving from a bucket 857cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project header into a bucket overflow. */ 858cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *new_entry = allocate_entry (new_table); 859cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 860cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (new_entry == NULL) 861cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return false; 862cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 863cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_entry->data = data; 864cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_entry->next = new_bucket->next; 865cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_bucket->next = new_entry; 866cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 867cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 868cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 869cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Merely relink an existing entry, when moving from a 870cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket overflow into a bucket overflow. */ 871cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project cursor->next = new_bucket->next; 872cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_bucket->next = cursor; 873cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 874cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 875cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 876cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 877cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Free an existing entry, when moving from a bucket 878cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project overflow into a bucket header. Also take care of the 879cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project simple case of moving from a bucket header into a bucket 880cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project header. */ 881cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_bucket->data = data; 882cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_table->n_buckets_used++; 883cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (cursor != bucket) 884cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free_entry (new_table, cursor); 885cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 886cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 887cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 888cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (table->bucket); 889cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->bucket = new_table->bucket; 890cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->bucket_limit = new_table->bucket_limit; 891cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets = new_table->n_buckets; 892cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets_used = new_table->n_buckets_used; 893cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->free_entry_list = new_table->free_entry_list; 894cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* table->n_entries already holds its value. */ 895cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if USE_OBSTACK 896cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->entry_stack = new_table->entry_stack; 897cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 898cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (new_table); 899cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 900cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return true; 901cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 902cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 903cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* If ENTRY matches an entry already in the hash table, return the pointer 904cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project to the entry from the table. Otherwise, insert ENTRY and return ENTRY. 905cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Return NULL if the storage required for insertion cannot be allocated. */ 906cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 907cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid * 908cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_insert (Hash_table *table, const void *entry) 909cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 910cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void *data; 911cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket; 912cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 913cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* The caller cannot insert a NULL entry. */ 914cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (! entry) 915cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project abort (); 916cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 917cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If there's a matching entry already in the table, return that. */ 918cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL) 919cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return data; 920cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 921cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* ENTRY is not matched, it should be inserted. */ 922cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 923cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket->data) 924cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 925cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *new_entry = allocate_entry (table); 926cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 927cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (new_entry == NULL) 928cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 929cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 930cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Add ENTRY in the overflow of the bucket. */ 931cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 932cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_entry->data = (void *) entry; 933cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_entry->next = bucket->next; 934cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket->next = new_entry; 935cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_entries++; 936cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return (void *) entry; 937cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 938cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 939cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Add ENTRY right in the bucket head. */ 940cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 941cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bucket->data = (void *) entry; 942cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_entries++; 943cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets_used++; 944cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 945cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If the growth threshold of the buckets in use has been reached, increase 946cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the table size and rehash. There's no point in checking the number of 947cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entries: if the hashing function is ill-conditioned, rehashing is not 948cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project likely to improve it. */ 949cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 950cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->n_buckets_used 951cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project > table->tuning->growth_threshold * table->n_buckets) 952cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 953cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Check more fully, before starting real work. If tuning arguments 954cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project became invalid, the second check will rely on proper defaults. */ 955cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project check_tuning (table); 956cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->n_buckets_used 957cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project > table->tuning->growth_threshold * table->n_buckets) 958cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 959cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project const Hash_tuning *tuning = table->tuning; 960cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project float candidate = 961cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (tuning->is_n_buckets 962cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ? (table->n_buckets * tuning->growth_factor) 963cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project : (table->n_buckets * tuning->growth_factor 964cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project * tuning->growth_threshold)); 965cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 966cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (SIZE_MAX <= candidate) 967cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 968cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 969cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If the rehash fails, arrange to return NULL. */ 970cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!hash_rehash (table, candidate)) 971cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project entry = NULL; 972cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 973cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 974cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 975cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return (void *) entry; 976cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 977cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 978cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* If ENTRY is already in the table, remove it and return the just-deleted 979cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project data (the user may want to deallocate its storage). If ENTRY is not in the 980cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table, don't modify the table and return NULL. */ 981cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 982cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid * 983cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_delete (Hash_table *table, const void *entry) 984cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 985cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project void *data; 986cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *bucket; 987cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 988cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project data = hash_find_entry (table, entry, &bucket, true); 989cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!data) 990cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return NULL; 991cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 992cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_entries--; 993cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!bucket->data) 994cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 995cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project table->n_buckets_used--; 996cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 997cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* If the shrink threshold of the buckets in use has been reached, 998cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rehash into a smaller table. */ 999cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1000cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->n_buckets_used 1001cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project < table->tuning->shrink_threshold * table->n_buckets) 1002cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1003cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Check more fully, before starting real work. If tuning arguments 1004cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project became invalid, the second check will rely on proper defaults. */ 1005cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project check_tuning (table); 1006cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (table->n_buckets_used 1007cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project < table->tuning->shrink_threshold * table->n_buckets) 1008cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1009cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project const Hash_tuning *tuning = table->tuning; 1010cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t candidate = 1011cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project (tuning->is_n_buckets 1012cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project ? table->n_buckets * tuning->shrink_factor 1013cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project : (table->n_buckets * tuning->shrink_factor 1014cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project * tuning->growth_threshold)); 1015cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1016cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project hash_rehash (table, candidate); 1017cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1018cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1019cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1020cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1021cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return data; 1022cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1023cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1024cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Testing. */ 1025cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1026cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#if TESTING 1027cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1028cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 1029cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecthash_print (const Hash_table *table) 1030cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 1031cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry const *bucket; 1032cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1033cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 1034cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1035cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct hash_entry *cursor; 1036cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1037cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (bucket) 1038cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project printf ("%lu:\n", (unsigned long int) (bucket - table->bucket)); 1039cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1040cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (cursor = bucket; cursor; cursor = cursor->next) 1041cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 1042cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project char const *s = cursor->data; 1043cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* FIXME */ 1044cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (s) 1045cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project printf (" %s\n", s); 1046cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1047cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 1048cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 1049cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1050cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif /* TESTING */ 1051