X-Git-Url: http://git.hcoop.net/bpt/guile.git/blobdiff_plain/a9cf5c7168fb8ee959d867f7cc2a4efd1acea1e0..4af0d97ee65f298be33d5959cd36a5bea8797be9:/libguile/hashtab.h diff --git a/libguile/hashtab.h b/libguile/hashtab.h index 5ef30a1c8..dcebcb81e 100644 --- a/libguile/hashtab.h +++ b/libguile/hashtab.h @@ -3,21 +3,22 @@ #ifndef SCM_HASHTAB_H #define SCM_HASHTAB_H -/* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004 Free Software Foundation, Inc. +/* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004, 2006, 2008, 2009 Free Software Foundation, Inc. * * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 3 of + * the License, or (at your option) any later version. * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of + * This library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301 USA */ @@ -31,17 +32,12 @@ #define SCM_HASHTABLEF_WEAK_CAR SCM_WVECTF_WEAK_KEY #define SCM_HASHTABLEF_WEAK_CDR SCM_WVECTF_WEAK_VALUE -extern scm_t_bits scm_tc16_hashtable; - -#define SCM_HASHTABLE_P(x) SCM_SMOB_PREDICATE (scm_tc16_hashtable, x) +#define SCM_HASHTABLE_P(x) (!SCM_IMP (x) && SCM_TYP7(x) == scm_tc7_hashtable) #define SCM_VALIDATE_HASHTABLE(pos, arg) \ SCM_MAKE_VALIDATE_MSG (pos, arg, HASHTABLE_P, "hash-table") -#define SCM_HASHTABLE_VECTOR(h) SCM_SMOB_OBJECT (h) -#define SCM_SET_HASHTABLE_VECTOR(x, v) SCM_SET_SMOB_OBJECT ((x), (v)) -#define SCM_HASHTABLE(x) ((scm_t_hashtable *) SCM_SMOB_DATA_2 (x)) -#define SCM_HASHTABLE_NEXT(x) SCM_SMOB_OBJECT_3 (x) -#define SCM_HASHTABLE_NEXTLOC(x) SCM_SMOB_OBJECT_3_LOC (x) -#define SCM_SET_HASHTABLE_NEXT(x, n) SCM_SET_SMOB_OBJECT_3 ((x), (n)) +#define SCM_HASHTABLE_VECTOR(h) SCM_CELL_OBJECT_1 (h) +#define SCM_SET_HASHTABLE_VECTOR(x, v) SCM_SET_CELL_OBJECT_1 ((x), (v)) +#define SCM_HASHTABLE(x) ((scm_t_hashtable *) SCM_CELL_WORD_2 (x)) #define SCM_HASHTABLE_FLAGS(x) (SCM_HASHTABLE (x)->flags) #define SCM_HASHTABLE_WEAK_KEY_P(x) \ (SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CAR) @@ -66,6 +62,26 @@ extern scm_t_bits scm_tc16_hashtable; #define SCM_SET_HASHTABLE_BUCKET(h, i, x) \ SCM_SIMPLE_VECTOR_SET (SCM_HASHTABLE_VECTOR (h), i, x) +/* Function that computes a hash of OBJ modulo MAX. */ +typedef unsigned long (*scm_t_hash_fn) (SCM obj, unsigned long max, + void *closure); + +/* Function that returns the value associated with OBJ in ALIST according to + some equality predicate. */ +typedef SCM (*scm_t_assoc_fn) (SCM obj, SCM alist, void *closure); + +/* Function that returns true if the given object is the one we are + looking for, for scm_hash_fn_ref_by_hash. */ +typedef int (*scm_t_hash_predicate_fn) (SCM obj, void *closure); + +/* Function to fold over the entries of a hash table. */ +typedef SCM (*scm_t_hash_fold_fn) (void *closure, SCM key, SCM value, + SCM result); + +/* Function to iterate over the handles (key-value pairs) of a hash + table. */ +typedef SCM (*scm_t_hash_handle_fn) (void *closure, SCM handle); + typedef struct scm_t_hashtable { int flags; /* properties of table */ unsigned long n_items; /* number of items in table */ @@ -73,18 +89,11 @@ typedef struct scm_t_hashtable { unsigned long upper; /* when to grow */ int size_index; /* index into hashtable_size */ int min_size_index; /* minimum size_index */ - unsigned long (*hash_fn) (); - void *closure; + scm_t_hash_fn hash_fn; /* for rehashing after a GC. */ } scm_t_hashtable; -#if 0 -typedef unsigned int scm_t_hash_fn (SCM obj, unsigned int d, void *closure); -typedef SCM scm_t_assoc_fn (SCM key, SCM alist, void *closure); -typedef SCM scm_t_delete_fn (SCM elt, SCM list); -#endif - SCM_API SCM scm_vector_to_hash_table (SCM vector); SCM_API SCM scm_c_make_hash_table (unsigned long k); SCM_API SCM scm_make_hash_table (SCM n); @@ -97,15 +106,38 @@ SCM_API SCM scm_weak_key_hash_table_p (SCM h); SCM_API SCM scm_weak_value_hash_table_p (SCM h); SCM_API SCM scm_doubly_weak_hash_table_p (SCM h); -SCM_API void scm_i_rehash (SCM table, unsigned long (*hash_fn)(), void *closure, const char*func_name); - -SCM_API SCM scm_hash_fn_get_handle (SCM table, SCM obj, unsigned long (*hash_fn) (), SCM (*assoc_fn) (), void * closure); -SCM_API SCM scm_hash_fn_create_handle_x (SCM table, SCM obj, SCM init, unsigned long (*hash_fn) (), SCM (*assoc_fn) (), void * closure); -SCM_API SCM scm_hash_fn_ref (SCM table, SCM obj, SCM dflt, unsigned long (*hash_fn) (), SCM (*assoc_fn) (), void * closure); -SCM_API SCM scm_hash_fn_set_x (SCM table, SCM obj, SCM val, unsigned long (*hash_fn) (), SCM (*assoc_fn) (), void * closure); -SCM_API SCM scm_hash_fn_remove_x (SCM table, SCM obj, unsigned long (*hash_fn) (), SCM (*assoc_fn) (), void * closure); -SCM_API SCM scm_internal_hash_fold (SCM (*fn) (), void *closure, SCM init, SCM table); -SCM_API void scm_internal_hash_for_each_handle (SCM (*fn) (), void *closure, SCM table); +SCM_INTERNAL void scm_i_rehash (SCM table, scm_t_hash_fn hash_fn, + void *closure, const char *func_name); + + +SCM_API SCM scm_hash_fn_get_handle (SCM table, SCM obj, + scm_t_hash_fn hash_fn, + scm_t_assoc_fn assoc_fn, + void *closure); +SCM_INTERNAL +SCM scm_hash_fn_get_handle_by_hash (SCM table, unsigned long raw_hash, + scm_t_hash_predicate_fn predicate_fn, + void *closure); +SCM_API SCM scm_hash_fn_create_handle_x (SCM table, SCM obj, SCM init, + scm_t_hash_fn hash_fn, + scm_t_assoc_fn assoc_fn, + void *closure); +SCM_API SCM scm_hash_fn_ref (SCM table, SCM obj, SCM dflt, + scm_t_hash_fn hash_fn, + scm_t_assoc_fn assoc_fn, + void *closure); +SCM_API SCM scm_hash_fn_set_x (SCM table, SCM obj, SCM val, + scm_t_hash_fn hash_fn, + scm_t_assoc_fn assoc_fn, + void *closure); +SCM_API SCM scm_hash_fn_remove_x (SCM table, SCM obj, + scm_t_hash_fn hash_fn, + scm_t_assoc_fn assoc_fn, + void *closure); +SCM_API SCM scm_internal_hash_fold (scm_t_hash_fold_fn fn, void *closure, + SCM init, SCM table); +SCM_API void scm_internal_hash_for_each_handle (scm_t_hash_handle_fn fn, + void *closure, SCM table); SCM_API SCM scm_hash_clear_x (SCM table); SCM_API SCM scm_hashq_get_handle (SCM table, SCM obj); @@ -132,8 +164,9 @@ SCM_API SCM scm_hash_fold (SCM proc, SCM init, SCM hash); SCM_API SCM scm_hash_for_each (SCM proc, SCM hash); SCM_API SCM scm_hash_for_each_handle (SCM proc, SCM hash); SCM_API SCM scm_hash_map_to_list (SCM proc, SCM hash); -SCM_API void scm_hashtab_prehistory (void); -SCM_API void scm_init_hashtab (void); +SCM_API SCM scm_hash_count (SCM hash, SCM pred); +SCM_INTERNAL void scm_i_hashtable_print (SCM exp, SCM port, scm_print_state *pstate); +SCM_INTERNAL void scm_init_hashtab (void); #endif /* SCM_HASHTAB_H */