X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Fhash.h;h=9994f5f6656048423e1b09934e0118ca5a373672;hb=6a0fd2e2d7d6a7e787ada21ffbe5f8ac0e3a06f1;hp=27b6fa45a67398a93231bd3ddc12e2d2c0e74144;hpb=89f2b4892655a929a506eff123c9126a88e2c8eb;p=gnulib.git diff --git a/lib/hash.h b/lib/hash.h index 27b6fa45a..9994f5f66 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -1,11 +1,12 @@ /* hash - hashing table processing. - Copyright (C) 1998, 1999 Free Software Foundation, Inc. + Copyright (C) 1998-1999, 2001, 2003, 2009-2014 Free Software Foundation, + Inc. Written by Jim Meyering , 1998. - This program is free software; you can redistribute it and/or modify + This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2, or (at your option) - any later version. + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -13,108 +14,94 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software Foundation, - Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + along with this program. If not, see . */ /* A generic hash table package. */ /* Make sure USE_OBSTACK is defined to 1 if you want the allocator to use - obstacks instead of malloc, and recompile `hash.c' with same setting. */ + obstacks instead of malloc, and recompile 'hash.c' with same setting. */ -#ifndef PARAMS -# if PROTOTYPES || __STDC__ -# define PARAMS(Args) Args +#ifndef HASH_H_ +# define HASH_H_ + +# include +# include + +/* The __attribute__ feature is available in gcc versions 2.5 and later. + The warn_unused_result attribute appeared first in gcc-3.4.0. */ +# if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) +# define _GL_ATTRIBUTE_WUR __attribute__ ((__warn_unused_result__)) # else -# define PARAMS(Args) () +# define _GL_ATTRIBUTE_WUR /* empty */ # endif -#endif -typedef unsigned (*Hash_hasher) PARAMS ((const void *, unsigned)); -typedef bool (*Hash_comparator) PARAMS ((const void *, const void *)); -typedef void (*Hash_data_freer) PARAMS ((void *)); -typedef bool (*Hash_processor) PARAMS ((void *, void *)); +# ifndef _GL_ATTRIBUTE_DEPRECATED +/* The __attribute__((__deprecated__)) feature + is available in gcc versions 3.1 and newer. */ +# if __GNUC__ < 3 || (__GNUC__ == 3 && __GNUC_MINOR__ < 1) +# define _GL_ATTRIBUTE_DEPRECATED /* empty */ +# else +# define _GL_ATTRIBUTE_DEPRECATED __attribute__ ((__deprecated__)) +# endif +# endif -struct hash_entry - { - void *data; - struct hash_entry *next; - }; +typedef size_t (*Hash_hasher) (const void *, size_t); +typedef bool (*Hash_comparator) (const void *, const void *); +typedef void (*Hash_data_freer) (void *); +typedef bool (*Hash_processor) (void *, void *); struct hash_tuning { - /* This structure is mainly used for `hash_initialize', see the block - documentation of `hash_reset_tuning' for more complete comments. */ - - float shrink_threshold; /* ratio of used buckets to trigger a shrink */ - float shrink_factor; /* ratio of new smaller size to original size */ - float growth_threshold; /* ratio of used buckets to trigger a growth */ - float growth_factor; /* ratio of new bigger size to original size */ - bool is_n_buckets; /* if CANDIDATE really means table size */ + /* This structure is mainly used for 'hash_initialize', see the block + documentation of 'hash_reset_tuning' for more complete comments. */ + + float shrink_threshold; /* ratio of used buckets to trigger a shrink */ + float shrink_factor; /* ratio of new smaller size to original size */ + float growth_threshold; /* ratio of used buckets to trigger a growth */ + float growth_factor; /* ratio of new bigger size to original size */ + bool is_n_buckets; /* if CANDIDATE really means table size */ }; typedef struct hash_tuning Hash_tuning; -struct hash_table - { - /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1, - for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets - are not empty, there are N_ENTRIES active entries in the table. */ - struct hash_entry *bucket; - struct hash_entry *bucket_limit; - unsigned n_buckets; - unsigned n_buckets_used; - unsigned n_entries; - - /* Tuning arguments, kept in a physicaly separate structure. */ - const Hash_tuning *tuning; - - /* Three functions are given to `hash_initialize', see the documentation - block for this function. In a word, HASHER randomizes a user entry - into a number up from 0 up to some maximum minus 1; COMPARATOR returns - true if two user entries compare equally; and DATA_FREER is the cleanup - function for a user entry. */ - Hash_hasher hasher; - Hash_comparator comparator; - Hash_data_freer data_freer; - - /* A linked list of freed struct hash_entry structs. */ - struct hash_entry *free_entry_list; - -#if USE_OBSTACK - /* Whenever obstacks are used, it is possible to allocate all overflowed - entries into a single stack, so they all can be freed in a single - operation. It is not clear if the speedup is worth the trouble. */ - struct obstack entry_stack; -#endif - }; +struct hash_table; typedef struct hash_table Hash_table; /* Information and lookup. */ -unsigned hash_get_n_buckets PARAMS ((const Hash_table *)); -unsigned hash_get_n_buckets_used PARAMS ((const Hash_table *)); -unsigned hash_get_n_entries PARAMS ((const Hash_table *)); -unsigned hash_get_max_bucket_length PARAMS ((const Hash_table *)); -bool hash_table_ok PARAMS ((const Hash_table *)); -void hash_print_statistics PARAMS ((const Hash_table *, FILE *)); -void *hash_lookup PARAMS ((const Hash_table *, const void *)); +size_t hash_get_n_buckets (const Hash_table *) _GL_ATTRIBUTE_PURE; +size_t hash_get_n_buckets_used (const Hash_table *) _GL_ATTRIBUTE_PURE; +size_t hash_get_n_entries (const Hash_table *) _GL_ATTRIBUTE_PURE; +size_t hash_get_max_bucket_length (const Hash_table *) _GL_ATTRIBUTE_PURE; +bool hash_table_ok (const Hash_table *) _GL_ATTRIBUTE_PURE; +void hash_print_statistics (const Hash_table *, FILE *); +void *hash_lookup (const Hash_table *, const void *); /* Walking. */ -void *hash_get_first PARAMS ((const Hash_table *)); -void *hash_get_next PARAMS ((const Hash_table *, const void *)); -unsigned hash_get_entries PARAMS ((const Hash_table *, void **, unsigned)); -unsigned hash_do_for_each PARAMS ((const Hash_table *, Hash_processor, void *)); +void *hash_get_first (const Hash_table *) _GL_ATTRIBUTE_PURE; +void *hash_get_next (const Hash_table *, const void *); +size_t hash_get_entries (const Hash_table *, void **, size_t); +size_t hash_do_for_each (const Hash_table *, Hash_processor, void *); /* Allocation and clean-up. */ -unsigned hash_string PARAMS ((const char *, unsigned)); -void hash_reset_tuning PARAMS ((Hash_tuning *)); -Hash_table *hash_initialize PARAMS ((unsigned, const Hash_tuning *, - Hash_hasher, Hash_comparator, - Hash_data_freer)); -void hash_clear PARAMS ((Hash_table *)); -void hash_free PARAMS ((Hash_table *)); +size_t hash_string (const char *, size_t) _GL_ATTRIBUTE_PURE; +void hash_reset_tuning (Hash_tuning *); +Hash_table *hash_initialize (size_t, const Hash_tuning *, + Hash_hasher, Hash_comparator, + Hash_data_freer) _GL_ATTRIBUTE_WUR; +void hash_clear (Hash_table *); +void hash_free (Hash_table *); /* Insertion and deletion. */ -bool hash_rehash PARAMS ((Hash_table *, unsigned)); -void *hash_insert PARAMS ((Hash_table *, const void *)); -void *hash_delete PARAMS ((Hash_table *, const void *)); +bool hash_rehash (Hash_table *, size_t) _GL_ATTRIBUTE_WUR; +void *hash_insert (Hash_table *, const void *) _GL_ATTRIBUTE_WUR; + +/* Deprecate this interface. It has been renamed to hash_insert_if_absent. */ +int hash_insert0 (Hash_table *table, /* FIXME: remove in 2013 */ + const void *entry, + const void **matched_ent) _GL_ATTRIBUTE_DEPRECATED; +int hash_insert_if_absent (Hash_table *table, const void *entry, + const void **matched_ent); +void *hash_delete (Hash_table *, const void *); + +#endif