[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 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.
 *
 * 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"

#include "weaks.h"

\f

#define SCM_HASHTABLEF_WEAK_CAR SCM_WVECTF_WEAK_KEY
#define SCM_HASHTABLEF_WEAK_CDR SCM_WVECTF_WEAK_VALUE

SCM_API scm_t_bits scm_tc16_hashtable;

#define SCM_HASHTABLE_P(x)	   SCM_SMOB_PREDICATE (scm_tc16_hashtable, x)
#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_FLAGS(x)	   (SCM_HASHTABLE (x)->flags)
#define SCM_HASHTABLE_WEAK_KEY_P(x) \
  (SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CAR)
#define SCM_HASHTABLE_WEAK_VALUE_P(x) \
  (SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CDR)
#define SCM_HASHTABLE_DOUBLY_WEAK_P(x)				\
  ((SCM_HASHTABLE_FLAGS (x)					\
    & (SCM_HASHTABLEF_WEAK_CAR | SCM_HASHTABLEF_WEAK_CDR))	\
   == (SCM_HASHTABLEF_WEAK_CAR | SCM_HASHTABLEF_WEAK_CDR))
#define SCM_HASHTABLE_WEAK_P(x)	   SCM_HASHTABLE_FLAGS (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)

typedef struct scm_t_hashtable {
  int flags;			/* properties of table */
  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 */
  unsigned long (*hash_fn) ();  /* for rehashing after a GC. */
} scm_t_hashtable;

\f

#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);
SCM_API SCM scm_make_weak_key_hash_table (SCM k);
SCM_API SCM scm_make_weak_value_hash_table (SCM k);
SCM_API SCM scm_make_doubly_weak_hash_table (SCM k);

SCM_API SCM scm_hash_table_p (SCM h);
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_INTERNAL 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_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_INTERNAL void scm_hashtab_prehistory (void);
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
102dbb6f	6	/* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004, 2006, 2008 Free Software Foundation, Inc.
0527e687	7	*
73be1d9e MV	8	* This library is free software; you can redistribute it and/or
	9	* modify it under the terms of the GNU Lesser General Public
	10	* License as published by the Free Software Foundation; either
	11	* version 2.1 of the License, or (at your option) any later version.
0527e687	12	*
73be1d9e	13	* This library is distributed in the hope that it will be useful,
0f2d19dd	14	* but 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
92205699	20	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
73be1d9e	21	*/
0527e687	22
0f2d19dd	23	\f
0527e687	24
5e044c02	25	#include "libguile/__scm.h"
0f2d19dd	26
c35738c1 MD	27	#include "weaks.h"
	28
	29	\f
	30
	31	#define SCM_HASHTABLEF_WEAK_CAR SCM_WVECTF_WEAK_KEY
	32	#define SCM_HASHTABLEF_WEAK_CDR SCM_WVECTF_WEAK_VALUE
	33
ecc9f40f	34	SCM_API scm_t_bits scm_tc16_hashtable;
cdc5f676	35
f5710d53	36	#define SCM_HASHTABLE_P(x) SCM_SMOB_PREDICATE (scm_tc16_hashtable, x)
c35738c1 MD	37	#define SCM_VALIDATE_HASHTABLE(pos, arg) \
c35738c1 MD	38	SCM_MAKE_VALIDATE_MSG (pos, arg, HASHTABLE_P, "hash-table")
f5710d53 MV	39	#define SCM_HASHTABLE_VECTOR(h) SCM_SMOB_OBJECT (h)
	40	#define SCM_SET_HASHTABLE_VECTOR(x, v) SCM_SET_SMOB_OBJECT ((x), (v))
	41	#define SCM_HASHTABLE(x) ((scm_t_hashtable *) SCM_SMOB_DATA_2 (x))
c35738c1 MD	42	#define SCM_HASHTABLE_FLAGS(x) (SCM_HASHTABLE (x)->flags)
	43	#define SCM_HASHTABLE_WEAK_KEY_P(x) \
	44	(SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CAR)
	45	#define SCM_HASHTABLE_WEAK_VALUE_P(x) \
	46	(SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CDR)
	47	#define SCM_HASHTABLE_DOUBLY_WEAK_P(x) \
	48	((SCM_HASHTABLE_FLAGS (x) \
	49	& (SCM_HASHTABLEF_WEAK_CAR \| SCM_HASHTABLEF_WEAK_CDR)) \
	50	== (SCM_HASHTABLEF_WEAK_CAR \| SCM_HASHTABLEF_WEAK_CDR))
	51	#define SCM_HASHTABLE_WEAK_P(x) SCM_HASHTABLE_FLAGS (x)
	52	#define SCM_HASHTABLE_N_ITEMS(x) (SCM_HASHTABLE (x)->n_items)
	53	#define SCM_SET_HASHTABLE_N_ITEMS(x, n) (SCM_HASHTABLE (x)->n_items = n)
	54	#define SCM_HASHTABLE_INCREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)++)
	55	#define SCM_HASHTABLE_DECREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)--)
	56	#define SCM_HASHTABLE_UPPER(x) (SCM_HASHTABLE (x)->upper)
	57	#define SCM_HASHTABLE_LOWER(x) (SCM_HASHTABLE (x)->lower)
	58
	59	#define SCM_HASHTABLE_N_BUCKETS(h) \
3ebc1832 MV	60	SCM_SIMPLE_VECTOR_LENGTH (SCM_HASHTABLE_VECTOR (h))
	61	#define SCM_HASHTABLE_BUCKET(h, i) \
	62	SCM_SIMPLE_VECTOR_REF (SCM_HASHTABLE_VECTOR (h), i)
c35738c1	63	#define SCM_SET_HASHTABLE_BUCKET(h, i, x) \
3ebc1832	64	SCM_SIMPLE_VECTOR_SET (SCM_HASHTABLE_VECTOR (h), i, x)
c35738c1 MD	65
	66	typedef struct scm_t_hashtable {
	67	int flags; /* properties of table */
	68	unsigned long n_items; /* number of items in table */
	69	unsigned long lower; /* when to shrink */
	70	unsigned long upper; /* when to grow */
	71	int size_index; /* index into hashtable_size */
	72	int min_size_index; /* minimum size_index */
d3a80924	73	unsigned long (hash_fn) (); / for rehashing after a GC. */
c35738c1 MD	74	} scm_t_hashtable;
c35738c1 MD	75
0f2d19dd	76	\f
0f2d19dd	77
1cc91f1b	78	#if 0
92c2555f MV	79	typedef unsigned int scm_t_hash_fn (SCM obj, unsigned int d, void *closure);
	80	typedef SCM scm_t_assoc_fn (SCM key, SCM alist, void *closure);
	81	typedef SCM scm_t_delete_fn (SCM elt, SCM list);
1cc91f1b	82	#endif
0f2d19dd	83
f59a096e	84	SCM_API SCM scm_vector_to_hash_table (SCM vector);
33b001fd	85	SCM_API SCM scm_c_make_hash_table (unsigned long k);
f59a096e	86	SCM_API SCM scm_make_hash_table (SCM n);
c35738c1 MD	87	SCM_API SCM scm_make_weak_key_hash_table (SCM k);
	88	SCM_API SCM scm_make_weak_value_hash_table (SCM k);
	89	SCM_API SCM scm_make_doubly_weak_hash_table (SCM k);
	90
	91	SCM_API SCM scm_hash_table_p (SCM h);
	92	SCM_API SCM scm_weak_key_hash_table_p (SCM h);
	93	SCM_API SCM scm_weak_value_hash_table_p (SCM h);
	94	SCM_API SCM scm_doubly_weak_hash_table_p (SCM h);
	95
102dbb6f LC	96	SCM_INTERNAL void scm_i_rehash (SCM table, unsigned long (*hash_fn)(),
102dbb6f LC	97	void closure, const char func_name);
00ffa0e7	98
33b001fd MV	99	SCM_API SCM scm_hash_fn_get_handle (SCM table, SCM obj, unsigned long (hash_fn) (), SCM (assoc_fn) (), void * closure);
	100	SCM_API SCM scm_hash_fn_create_handle_x (SCM table, SCM obj, SCM init, unsigned long (hash_fn) (), SCM (assoc_fn) (), void * closure);
	101	SCM_API SCM scm_hash_fn_ref (SCM table, SCM obj, SCM dflt, unsigned long (hash_fn) (), SCM (assoc_fn) (), void * closure);
	102	SCM_API SCM scm_hash_fn_set_x (SCM table, SCM obj, SCM val, unsigned long (hash_fn) (), SCM (assoc_fn) (), void * closure);
a9cf5c71	103	SCM_API SCM scm_hash_fn_remove_x (SCM table, SCM obj, unsigned long (hash_fn) (), SCM (assoc_fn) (), void * closure);
33b001fd	104	SCM_API SCM scm_internal_hash_fold (SCM (fn) (), void closure, SCM init, SCM table);
711a9fd7	105	SCM_API void scm_internal_hash_for_each_handle (SCM (fn) (), void closure, SCM table);
c35738c1	106	SCM_API SCM scm_hash_clear_x (SCM table);
0f2d19dd	107
33b001fd MV	108	SCM_API SCM scm_hashq_get_handle (SCM table, SCM obj);
	109	SCM_API SCM scm_hashq_create_handle_x (SCM table, SCM obj, SCM init);
	110	SCM_API SCM scm_hashq_ref (SCM table, SCM obj, SCM dflt);
	111	SCM_API SCM scm_hashq_set_x (SCM table, SCM obj, SCM val);
	112	SCM_API SCM scm_hashq_remove_x (SCM table, SCM obj);
	113	SCM_API SCM scm_hashv_get_handle (SCM table, SCM obj);
	114	SCM_API SCM scm_hashv_create_handle_x (SCM table, SCM obj, SCM init);
	115	SCM_API SCM scm_hashv_ref (SCM table, SCM obj, SCM dflt);
	116	SCM_API SCM scm_hashv_set_x (SCM table, SCM obj, SCM val);
	117	SCM_API SCM scm_hashv_remove_x (SCM table, SCM obj);
	118	SCM_API SCM scm_hash_get_handle (SCM table, SCM obj);
	119	SCM_API SCM scm_hash_create_handle_x (SCM table, SCM obj, SCM init);
	120	SCM_API SCM scm_hash_ref (SCM table, SCM obj, SCM dflt);
	121	SCM_API SCM scm_hash_set_x (SCM table, SCM obj, SCM val);
	122	SCM_API SCM scm_hash_remove_x (SCM table, SCM obj);
	123	SCM_API SCM scm_hashx_get_handle (SCM hash, SCM assoc, SCM table, SCM obj);
	124	SCM_API SCM scm_hashx_create_handle_x (SCM hash, SCM assoc, SCM table, SCM obj, SCM init);
	125	SCM_API SCM scm_hashx_ref (SCM hash, SCM assoc, SCM table, SCM obj, SCM dflt);
	126	SCM_API SCM scm_hashx_set_x (SCM hash, SCM assoc, SCM table, SCM obj, SCM val);
a9cf5c71	127	SCM_API SCM scm_hashx_remove_x (SCM hash, SCM assoc, SCM table, SCM obj);
33b001fd	128	SCM_API SCM scm_hash_fold (SCM proc, SCM init, SCM hash);
c35738c1	129	SCM_API SCM scm_hash_for_each (SCM proc, SCM hash);
711a9fd7 MD	130	SCM_API SCM scm_hash_for_each_handle (SCM proc, SCM hash);
711a9fd7 MD	131	SCM_API SCM scm_hash_map_to_list (SCM proc, SCM hash);
102dbb6f LC	132	SCM_INTERNAL void scm_hashtab_prehistory (void);
102dbb6f LC	133	SCM_INTERNAL void scm_init_hashtab (void);
0f2d19dd	134
0527e687	135	#endif /* SCM_HASHTAB_H */
89e00824 ML	136
	137	/*
	138	Local Variables:
	139	c-file-style: "gnu"
	140	End:
	141	*/