[bpt/guile.git] / libguile / hashtab.h

/* classes: h_files */

#ifndef SCM_HASHTAB_H
#define SCM_HASHTAB_H

/* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004, 2006, 2008, 2009, 2011 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 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
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301 USA
 */

\f

#include "libguile/__scm.h"

\f

#define SCM_HASHTABLE_P(x) (SCM_HAS_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_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_N_ITEMS(x)   (SCM_HASHTABLE (x)->n_items)
#define SCM_SET_HASHTABLE_N_ITEMS(x, n)   (SCM_HASHTABLE (x)->n_items = n)
#define SCM_HASHTABLE_INCREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)++)
#define SCM_HASHTABLE_DECREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)--)
#define SCM_HASHTABLE_UPPER(x)     (SCM_HASHTABLE (x)->upper)
#define SCM_HASHTABLE_LOWER(x)     (SCM_HASHTABLE (x)->lower)

#define SCM_HASHTABLE_N_BUCKETS(h) \
 SCM_SIMPLE_VECTOR_LENGTH (SCM_HASHTABLE_VECTOR (h))
#define SCM_HASHTABLE_BUCKET(h, i) \
  SCM_SIMPLE_VECTOR_REF (SCM_HASHTABLE_VECTOR (h), i)
#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 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 {
  unsigned long n_items;	/* number of items in table */
  unsigned long lower;		/* when to shrink */
  unsigned long upper;		/* when to grow */
  int size_index;		/* index into hashtable_size */
  int min_size_index;		/* minimum size_index */
  scm_t_hash_fn hash_fn;  /* for rehashing after a GC. */
} scm_t_hashtable;

\f

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);

SCM_API SCM scm_hash_table_p (SCM h);

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_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);
SCM_API SCM scm_hashq_create_handle_x (SCM table, SCM obj, SCM init);
SCM_API SCM scm_hashq_ref (SCM table, SCM obj, SCM dflt);
SCM_API SCM scm_hashq_set_x (SCM table, SCM obj, SCM val);
SCM_API SCM scm_hashq_remove_x (SCM table, SCM obj);
SCM_API SCM scm_hashv_get_handle (SCM table, SCM obj);
SCM_API SCM scm_hashv_create_handle_x (SCM table, SCM obj, SCM init);
SCM_API SCM scm_hashv_ref (SCM table, SCM obj, SCM dflt);
SCM_API SCM scm_hashv_set_x (SCM table, SCM obj, SCM val);
SCM_API SCM scm_hashv_remove_x (SCM table, SCM obj);
SCM_API SCM scm_hash_get_handle (SCM table, SCM obj);
SCM_API SCM scm_hash_create_handle_x (SCM table, SCM obj, SCM init);
SCM_API SCM scm_hash_ref (SCM table, SCM obj, SCM dflt);
SCM_API SCM scm_hash_set_x (SCM table, SCM obj, SCM val);
SCM_API SCM scm_hash_remove_x (SCM table, SCM obj);
SCM_API SCM scm_hashx_get_handle (SCM hash, SCM assoc, SCM table, SCM obj);
SCM_API SCM scm_hashx_create_handle_x (SCM hash, SCM assoc, SCM table, SCM obj, SCM init);
SCM_API SCM scm_hashx_ref (SCM hash, SCM assoc, SCM table, SCM obj, SCM dflt);
SCM_API SCM scm_hashx_set_x (SCM hash, SCM assoc, SCM table, SCM obj, SCM val);
SCM_API SCM scm_hashx_remove_x (SCM hash, SCM assoc, SCM table, SCM obj);
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 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 */

/*
  Local Variables:
  c-file-style: "gnu"
  End:
*/
Commit	Line	Data
0f2d19dd JB	1	/* classes: h_files */
0f2d19dd JB	2
0527e687 DH	3	#ifndef SCM_HASHTAB_H
	4	#define SCM_HASHTAB_H
	5
54a9b981	6	/* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004, 2006, 2008, 2009, 2011 Free Software Foundation, Inc.
0527e687	7	*
73be1d9e	8	* This library is free software; you can redistribute it and/or
53befeb7 NJ	9	* modify it under the terms of the GNU Lesser General Public License
	10	* as published by the Free Software Foundation; either version 3 of
	11	* the License, or (at your option) any later version.
0527e687	12	*
53befeb7 NJ	13	* This library is distributed in the hope that it will be useful, but
53befeb7 NJ	14	* WITHOUT ANY WARRANTY; without even the implied warranty of
73be1d9e MV	15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
73be1d9e MV	16	* Lesser General Public License for more details.
0527e687	17	*
73be1d9e MV	18	* You should have received a copy of the GNU Lesser General Public
73be1d9e MV	19	* License along with this library; if not, write to the Free Software
53befeb7 NJ	20	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
53befeb7 NJ	21	* 02110-1301 USA
73be1d9e	22	*/
0527e687	23
0f2d19dd	24	\f
0527e687	25
5e044c02	26	#include "libguile/__scm.h"
0f2d19dd	27
c35738c1 MD	28	\f
c35738c1 MD	29
dc7da0be	30	#define SCM_HASHTABLE_P(x) (SCM_HAS_TYP7 (x, scm_tc7_hashtable))
c35738c1 MD	31	#define SCM_VALIDATE_HASHTABLE(pos, arg) \
c35738c1 MD	32	SCM_MAKE_VALIDATE_MSG (pos, arg, HASHTABLE_P, "hash-table")
c99de5aa AW	33	#define SCM_HASHTABLE_VECTOR(h) SCM_CELL_OBJECT_1 (h)
	34	#define SCM_SET_HASHTABLE_VECTOR(x, v) SCM_SET_CELL_OBJECT_1 ((x), (v))
	35	#define SCM_HASHTABLE(x) ((scm_t_hashtable *) SCM_CELL_WORD_2 (x))
c35738c1 MD	36	#define SCM_HASHTABLE_N_ITEMS(x) (SCM_HASHTABLE (x)->n_items)
	37	#define SCM_SET_HASHTABLE_N_ITEMS(x, n) (SCM_HASHTABLE (x)->n_items = n)
	38	#define SCM_HASHTABLE_INCREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)++)
	39	#define SCM_HASHTABLE_DECREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)--)
	40	#define SCM_HASHTABLE_UPPER(x) (SCM_HASHTABLE (x)->upper)
	41	#define SCM_HASHTABLE_LOWER(x) (SCM_HASHTABLE (x)->lower)
	42
	43	#define SCM_HASHTABLE_N_BUCKETS(h) \
3ebc1832 MV	44	SCM_SIMPLE_VECTOR_LENGTH (SCM_HASHTABLE_VECTOR (h))
	45	#define SCM_HASHTABLE_BUCKET(h, i) \
	46	SCM_SIMPLE_VECTOR_REF (SCM_HASHTABLE_VECTOR (h), i)
c35738c1	47	#define SCM_SET_HASHTABLE_BUCKET(h, i, x) \
3ebc1832	48	SCM_SIMPLE_VECTOR_SET (SCM_HASHTABLE_VECTOR (h), i, x)
c35738c1	49
d587c9e8 LC	50	/* Function that computes a hash of OBJ modulo MAX. */
	51	typedef unsigned long (*scm_t_hash_fn) (SCM obj, unsigned long max,
	52	void *closure);
	53
	54	/* Function that returns the value associated with OBJ in ALIST according to
	55	some equality predicate. */
	56	typedef SCM (scm_t_assoc_fn) (SCM obj, SCM alist, void closure);
	57
a07010bf LC	58	/* Function to fold over the entries of a hash table. */
	59	typedef SCM (scm_t_hash_fold_fn) (void closure, SCM key, SCM value,
	60	SCM result);
	61
	62	/* Function to iterate over the handles (key-value pairs) of a hash
	63	table. */
	64	typedef SCM (scm_t_hash_handle_fn) (void closure, SCM handle);
	65
c35738c1	66	typedef struct scm_t_hashtable {
c35738c1 MD	67	unsigned long n_items; /* number of items in table */
	68	unsigned long lower; /* when to shrink */
	69	unsigned long upper; /* when to grow */
	70	int size_index; /* index into hashtable_size */
	71	int min_size_index; /* minimum size_index */
d587c9e8	72	scm_t_hash_fn hash_fn; /* for rehashing after a GC. */
c35738c1 MD	73	} scm_t_hashtable;
c35738c1 MD	74
0f2d19dd	75	\f
0f2d19dd	76
f59a096e	77	SCM_API SCM scm_vector_to_hash_table (SCM vector);
33b001fd	78	SCM_API SCM scm_c_make_hash_table (unsigned long k);
f59a096e	79	SCM_API SCM scm_make_hash_table (SCM n);
c35738c1 MD	80
c35738c1 MD	81	SCM_API SCM scm_hash_table_p (SCM h);
c35738c1	82
d587c9e8	83	SCM_INTERNAL void scm_i_rehash (SCM table, scm_t_hash_fn hash_fn,
102dbb6f	84	void closure, const char func_name);
00ffa0e7	85
d587c9e8 LC	86
	87	SCM_API SCM scm_hash_fn_get_handle (SCM table, SCM obj,
	88	scm_t_hash_fn hash_fn,
	89	scm_t_assoc_fn assoc_fn,
	90	void *closure);
	91	SCM_API SCM scm_hash_fn_create_handle_x (SCM table, SCM obj, SCM init,
	92	scm_t_hash_fn hash_fn,
	93	scm_t_assoc_fn assoc_fn,
	94	void *closure);
	95	SCM_API SCM scm_hash_fn_ref (SCM table, SCM obj, SCM dflt,
	96	scm_t_hash_fn hash_fn,
	97	scm_t_assoc_fn assoc_fn,
	98	void *closure);
	99	SCM_API SCM scm_hash_fn_set_x (SCM table, SCM obj, SCM val,
	100	scm_t_hash_fn hash_fn,
	101	scm_t_assoc_fn assoc_fn,
	102	void *closure);
	103	SCM_API SCM scm_hash_fn_remove_x (SCM table, SCM obj,
	104	scm_t_hash_fn hash_fn,
	105	scm_t_assoc_fn assoc_fn,
	106	void *closure);
a07010bf LC	107	SCM_API SCM scm_internal_hash_fold (scm_t_hash_fold_fn fn, void *closure,
	108	SCM init, SCM table);
	109	SCM_API void scm_internal_hash_for_each_handle (scm_t_hash_handle_fn fn,
	110	void *closure, SCM table);
c35738c1	111	SCM_API SCM scm_hash_clear_x (SCM table);
0f2d19dd	112
33b001fd MV	113	SCM_API SCM scm_hashq_get_handle (SCM table, SCM obj);
	114	SCM_API SCM scm_hashq_create_handle_x (SCM table, SCM obj, SCM init);
	115	SCM_API SCM scm_hashq_ref (SCM table, SCM obj, SCM dflt);
	116	SCM_API SCM scm_hashq_set_x (SCM table, SCM obj, SCM val);
	117	SCM_API SCM scm_hashq_remove_x (SCM table, SCM obj);
	118	SCM_API SCM scm_hashv_get_handle (SCM table, SCM obj);
	119	SCM_API SCM scm_hashv_create_handle_x (SCM table, SCM obj, SCM init);
	120	SCM_API SCM scm_hashv_ref (SCM table, SCM obj, SCM dflt);
	121	SCM_API SCM scm_hashv_set_x (SCM table, SCM obj, SCM val);
	122	SCM_API SCM scm_hashv_remove_x (SCM table, SCM obj);
	123	SCM_API SCM scm_hash_get_handle (SCM table, SCM obj);
	124	SCM_API SCM scm_hash_create_handle_x (SCM table, SCM obj, SCM init);
	125	SCM_API SCM scm_hash_ref (SCM table, SCM obj, SCM dflt);
	126	SCM_API SCM scm_hash_set_x (SCM table, SCM obj, SCM val);
	127	SCM_API SCM scm_hash_remove_x (SCM table, SCM obj);
	128	SCM_API SCM scm_hashx_get_handle (SCM hash, SCM assoc, SCM table, SCM obj);
	129	SCM_API SCM scm_hashx_create_handle_x (SCM hash, SCM assoc, SCM table, SCM obj, SCM init);
	130	SCM_API SCM scm_hashx_ref (SCM hash, SCM assoc, SCM table, SCM obj, SCM dflt);
	131	SCM_API SCM scm_hashx_set_x (SCM hash, SCM assoc, SCM table, SCM obj, SCM val);
a9cf5c71	132	SCM_API SCM scm_hashx_remove_x (SCM hash, SCM assoc, SCM table, SCM obj);
33b001fd	133	SCM_API SCM scm_hash_fold (SCM proc, SCM init, SCM hash);
c35738c1	134	SCM_API SCM scm_hash_for_each (SCM proc, SCM hash);
711a9fd7 MD	135	SCM_API SCM scm_hash_for_each_handle (SCM proc, SCM hash);
711a9fd7 MD	136	SCM_API SCM scm_hash_map_to_list (SCM proc, SCM hash);
3330f00f	137	SCM_API SCM scm_hash_count (SCM hash, SCM pred);
c99de5aa	138	SCM_INTERNAL void scm_i_hashtable_print (SCM exp, SCM port, scm_print_state *pstate);
102dbb6f	139	SCM_INTERNAL void scm_init_hashtab (void);
0f2d19dd	140
0527e687	141	#endif /* SCM_HASHTAB_H */
89e00824 ML	142
	143	/*
	144	Local Variables:
	145	c-file-style: "gnu"
	146	End:
	147	*/