1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* hash - hashing table processing. 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 1998-1999, 2001, 2003, 2009-2012 Free Software Foundation, 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Inc. 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Written by Jim Meyering <meyering@ascend.com>, 1998. 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 605436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is free software: you can redistribute it and/or modify 7cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it under the terms of the GNU General Public License as published by 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation; either version 3 of the License, or 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 10cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This program is distributed in the hope that it will be useful, 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should have received a copy of the GNU General Public License 1705436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* A generic hash table package. */ 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Make sure USE_OBSTACK is defined to 1 if you want the allocator to use 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstacks instead of malloc, and recompile 'hash.c' with same setting. */ 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#ifndef HASH_H_ 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# define HASH_H_ 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# include <stdio.h> 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project# include <stdbool.h> 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* The __attribute__ feature is available in gcc versions 2.5 and later. 3105436638acc7c010349a69c3395f1a57c642dc62Ying Wang The warn_unused_result attribute appeared first in gcc-3.4.0. */ 3205436638acc7c010349a69c3395f1a57c642dc62Ying Wang# if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) 3305436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define _GL_ATTRIBUTE_WUR __attribute__ ((__warn_unused_result__)) 3405436638acc7c010349a69c3395f1a57c642dc62Ying Wang# else 3505436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define _GL_ATTRIBUTE_WUR /* empty */ 3605436638acc7c010349a69c3395f1a57c642dc62Ying Wang# endif 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3805436638acc7c010349a69c3395f1a57c642dc62Ying Wang# ifndef _GL_ATTRIBUTE_DEPRECATED 3905436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* The __attribute__((__deprecated__)) feature 4005436638acc7c010349a69c3395f1a57c642dc62Ying Wang is available in gcc versions 3.1 and newer. */ 4105436638acc7c010349a69c3395f1a57c642dc62Ying Wang# if __GNUC__ < 3 || (__GNUC__ == 3 && __GNUC_MINOR__ < 1) 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define _GL_ATTRIBUTE_DEPRECATED /* empty */ 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang# else 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define _GL_ATTRIBUTE_DEPRECATED __attribute__ ((__deprecated__)) 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wang# endif 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wang# endif 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef size_t (*Hash_hasher) (const void *, size_t); 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef bool (*Hash_comparator) (const void *, const void *); 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef void (*Hash_data_freer) (void *); 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef bool (*Hash_processor) (void *, void *); 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct hash_tuning 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* This structure is mainly used for 'hash_initialize', see the block 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang documentation of 'hash_reset_tuning' for more complete comments. */ 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wang float shrink_threshold; /* ratio of used buckets to trigger a shrink */ 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang float shrink_factor; /* ratio of new smaller size to original size */ 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang float growth_threshold; /* ratio of used buckets to trigger a growth */ 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang float growth_factor; /* ratio of new bigger size to original size */ 6205436638acc7c010349a69c3395f1a57c642dc62Ying Wang bool is_n_buckets; /* if CANDIDATE really means table size */ 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project }; 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct hash_tuning Hash_tuning; 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstruct hash_table; 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct hash_table Hash_table; 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Information and lookup. */ 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wangsize_t hash_get_n_buckets (const Hash_table *) _GL_ATTRIBUTE_PURE; 7305436638acc7c010349a69c3395f1a57c642dc62Ying Wangsize_t hash_get_n_buckets_used (const Hash_table *) _GL_ATTRIBUTE_PURE; 7405436638acc7c010349a69c3395f1a57c642dc62Ying Wangsize_t hash_get_n_entries (const Hash_table *) _GL_ATTRIBUTE_PURE; 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wangsize_t hash_get_max_bucket_length (const Hash_table *) _GL_ATTRIBUTE_PURE; 7605436638acc7c010349a69c3395f1a57c642dc62Ying Wangbool hash_table_ok (const Hash_table *) _GL_ATTRIBUTE_PURE; 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid hash_print_statistics (const Hash_table *, FILE *); 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid *hash_lookup (const Hash_table *, const void *); 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Walking. */ 8105436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid *hash_get_first (const Hash_table *) _GL_ATTRIBUTE_PURE; 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid *hash_get_next (const Hash_table *, const void *); 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t hash_get_entries (const Hash_table *, void **, size_t); 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectsize_t hash_do_for_each (const Hash_table *, Hash_processor, void *); 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Allocation and clean-up. */ 8705436638acc7c010349a69c3395f1a57c642dc62Ying Wangsize_t hash_string (const char *, size_t) _GL_ATTRIBUTE_PURE; 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid hash_reset_tuning (Hash_tuning *); 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source ProjectHash_table *hash_initialize (size_t, const Hash_tuning *, 9005436638acc7c010349a69c3395f1a57c642dc62Ying Wang Hash_hasher, Hash_comparator, 9105436638acc7c010349a69c3395f1a57c642dc62Ying Wang Hash_data_freer) _GL_ATTRIBUTE_WUR; 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid hash_clear (Hash_table *); 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid hash_free (Hash_table *); 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Insertion and deletion. */ 9605436638acc7c010349a69c3395f1a57c642dc62Ying Wangbool hash_rehash (Hash_table *, size_t) _GL_ATTRIBUTE_WUR; 9705436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid *hash_insert (Hash_table *, const void *) _GL_ATTRIBUTE_WUR; 9805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 9905436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Deprecate this interface. It has been renamed to hash_insert_if_absent. */ 10005436638acc7c010349a69c3395f1a57c642dc62Ying Wangint hash_insert0 (Hash_table *table, /* FIXME: remove in 2013 */ 10105436638acc7c010349a69c3395f1a57c642dc62Ying Wang const void *entry, 10205436638acc7c010349a69c3395f1a57c642dc62Ying Wang const void **matched_ent) _GL_ATTRIBUTE_DEPRECATED; 10305436638acc7c010349a69c3395f1a57c642dc62Ying Wangint hash_insert_if_absent (Hash_table *table, const void *entry, 10405436638acc7c010349a69c3395f1a57c642dc62Ying Wang const void **matched_ent); 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid *hash_delete (Hash_table *, const void *); 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#endif 108