6 /* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004, 2006, 2008, 2009 Free Software Foundation, Inc.
8 * This library is free software; you can redistribute it and/or
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.
13 * This library is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "libguile/__scm.h"
32 #define SCM_HASHTABLEF_WEAK_CAR SCM_WVECTF_WEAK_KEY
33 #define SCM_HASHTABLEF_WEAK_CDR SCM_WVECTF_WEAK_VALUE
35 #define SCM_HASHTABLE_P(x) (!SCM_IMP (x) && SCM_TYP7(x) == scm_tc7_hashtable)
36 #define SCM_VALIDATE_HASHTABLE(pos, arg) \
37 SCM_MAKE_VALIDATE_MSG (pos, arg, HASHTABLE_P, "hash-table")
38 #define SCM_HASHTABLE_VECTOR(h) SCM_CELL_OBJECT_1 (h)
39 #define SCM_SET_HASHTABLE_VECTOR(x, v) SCM_SET_CELL_OBJECT_1 ((x), (v))
40 #define SCM_HASHTABLE(x) ((scm_t_hashtable *) SCM_CELL_WORD_2 (x))
41 #define SCM_HASHTABLE_FLAGS(x) (SCM_HASHTABLE (x)->flags)
42 #define SCM_HASHTABLE_WEAK_KEY_P(x) \
43 (SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CAR)
44 #define SCM_HASHTABLE_WEAK_VALUE_P(x) \
45 (SCM_HASHTABLE_FLAGS (x) & SCM_HASHTABLEF_WEAK_CDR)
46 #define SCM_HASHTABLE_DOUBLY_WEAK_P(x) \
47 ((SCM_HASHTABLE_FLAGS (x) \
48 & (SCM_HASHTABLEF_WEAK_CAR | SCM_HASHTABLEF_WEAK_CDR)) \
49 == (SCM_HASHTABLEF_WEAK_CAR | SCM_HASHTABLEF_WEAK_CDR))
50 #define SCM_HASHTABLE_WEAK_P(x) SCM_HASHTABLE_FLAGS (x)
51 #define SCM_HASHTABLE_N_ITEMS(x) (SCM_HASHTABLE (x)->n_items)
52 #define SCM_SET_HASHTABLE_N_ITEMS(x, n) (SCM_HASHTABLE (x)->n_items = n)
53 #define SCM_HASHTABLE_INCREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)++)
54 #define SCM_HASHTABLE_DECREMENT(x) (SCM_HASHTABLE_N_ITEMS(x)--)
55 #define SCM_HASHTABLE_UPPER(x) (SCM_HASHTABLE (x)->upper)
56 #define SCM_HASHTABLE_LOWER(x) (SCM_HASHTABLE (x)->lower)
58 #define SCM_HASHTABLE_N_BUCKETS(h) \
59 SCM_SIMPLE_VECTOR_LENGTH (SCM_HASHTABLE_VECTOR (h))
60 #define SCM_HASHTABLE_BUCKET(h, i) \
61 SCM_SIMPLE_VECTOR_REF (SCM_HASHTABLE_VECTOR (h), i)
62 #define SCM_SET_HASHTABLE_BUCKET(h, i, x) \
63 SCM_SIMPLE_VECTOR_SET (SCM_HASHTABLE_VECTOR (h), i, x)
65 /* Function that computes a hash of OBJ modulo MAX. */
66 typedef unsigned long (*scm_t_hash_fn
) (SCM obj
, unsigned long max
,
69 /* Function that returns the value associated with OBJ in ALIST according to
70 some equality predicate. */
71 typedef SCM (*scm_t_assoc_fn
) (SCM obj
, SCM alist
, void *closure
);
73 /* Function that returns true if the given object is the one we are
74 looking for, for scm_hash_fn_ref_by_hash. */
75 typedef int (*scm_t_hash_predicate_fn
) (SCM obj
, void *closure
);
77 /* Function to fold over the entries of a hash table. */
78 typedef SCM (*scm_t_hash_fold_fn
) (void *closure
, SCM key
, SCM value
,
81 /* Function to iterate over the handles (key-value pairs) of a hash
83 typedef SCM (*scm_t_hash_handle_fn
) (void *closure
, SCM handle
);
85 typedef struct scm_t_hashtable
{
86 int flags
; /* properties of table */
87 unsigned long n_items
; /* number of items in table */
88 unsigned long lower
; /* when to shrink */
89 unsigned long upper
; /* when to grow */
90 int size_index
; /* index into hashtable_size */
91 int min_size_index
; /* minimum size_index */
92 scm_t_hash_fn hash_fn
; /* for rehashing after a GC. */
97 SCM_API SCM
scm_vector_to_hash_table (SCM vector
);
98 SCM_API SCM
scm_c_make_hash_table (unsigned long k
);
99 SCM_API SCM
scm_make_hash_table (SCM n
);
100 SCM_API SCM
scm_make_weak_key_hash_table (SCM k
);
101 SCM_API SCM
scm_make_weak_value_hash_table (SCM k
);
102 SCM_API SCM
scm_make_doubly_weak_hash_table (SCM k
);
104 SCM_API SCM
scm_hash_table_p (SCM h
);
105 SCM_API SCM
scm_weak_key_hash_table_p (SCM h
);
106 SCM_API SCM
scm_weak_value_hash_table_p (SCM h
);
107 SCM_API SCM
scm_doubly_weak_hash_table_p (SCM h
);
109 SCM_INTERNAL
void scm_i_rehash (SCM table
, scm_t_hash_fn hash_fn
,
110 void *closure
, const char *func_name
);
113 SCM_API SCM
scm_hash_fn_get_handle (SCM table
, SCM obj
,
114 scm_t_hash_fn hash_fn
,
115 scm_t_assoc_fn assoc_fn
,
118 SCM
scm_hash_fn_get_handle_by_hash (SCM table
, unsigned long raw_hash
,
119 scm_t_hash_predicate_fn predicate_fn
,
121 SCM_API SCM
scm_hash_fn_create_handle_x (SCM table
, SCM obj
, SCM init
,
122 scm_t_hash_fn hash_fn
,
123 scm_t_assoc_fn assoc_fn
,
125 SCM_API SCM
scm_hash_fn_ref (SCM table
, SCM obj
, SCM dflt
,
126 scm_t_hash_fn hash_fn
,
127 scm_t_assoc_fn assoc_fn
,
129 SCM_API SCM
scm_hash_fn_set_x (SCM table
, SCM obj
, SCM val
,
130 scm_t_hash_fn hash_fn
,
131 scm_t_assoc_fn assoc_fn
,
133 SCM_API SCM
scm_hash_fn_remove_x (SCM table
, SCM obj
,
134 scm_t_hash_fn hash_fn
,
135 scm_t_assoc_fn assoc_fn
,
137 SCM_API SCM
scm_internal_hash_fold (scm_t_hash_fold_fn fn
, void *closure
,
138 SCM init
, SCM table
);
139 SCM_API
void scm_internal_hash_for_each_handle (scm_t_hash_handle_fn fn
,
140 void *closure
, SCM table
);
141 SCM_API SCM
scm_hash_clear_x (SCM table
);
143 SCM_API SCM
scm_hashq_get_handle (SCM table
, SCM obj
);
144 SCM_API SCM
scm_hashq_create_handle_x (SCM table
, SCM obj
, SCM init
);
145 SCM_API SCM
scm_hashq_ref (SCM table
, SCM obj
, SCM dflt
);
146 SCM_API SCM
scm_hashq_set_x (SCM table
, SCM obj
, SCM val
);
147 SCM_API SCM
scm_hashq_remove_x (SCM table
, SCM obj
);
148 SCM_API SCM
scm_hashv_get_handle (SCM table
, SCM obj
);
149 SCM_API SCM
scm_hashv_create_handle_x (SCM table
, SCM obj
, SCM init
);
150 SCM_API SCM
scm_hashv_ref (SCM table
, SCM obj
, SCM dflt
);
151 SCM_API SCM
scm_hashv_set_x (SCM table
, SCM obj
, SCM val
);
152 SCM_API SCM
scm_hashv_remove_x (SCM table
, SCM obj
);
153 SCM_API SCM
scm_hash_get_handle (SCM table
, SCM obj
);
154 SCM_API SCM
scm_hash_create_handle_x (SCM table
, SCM obj
, SCM init
);
155 SCM_API SCM
scm_hash_ref (SCM table
, SCM obj
, SCM dflt
);
156 SCM_API SCM
scm_hash_set_x (SCM table
, SCM obj
, SCM val
);
157 SCM_API SCM
scm_hash_remove_x (SCM table
, SCM obj
);
158 SCM_API SCM
scm_hashx_get_handle (SCM hash
, SCM assoc
, SCM table
, SCM obj
);
159 SCM_API SCM
scm_hashx_create_handle_x (SCM hash
, SCM assoc
, SCM table
, SCM obj
, SCM init
);
160 SCM_API SCM
scm_hashx_ref (SCM hash
, SCM assoc
, SCM table
, SCM obj
, SCM dflt
);
161 SCM_API SCM
scm_hashx_set_x (SCM hash
, SCM assoc
, SCM table
, SCM obj
, SCM val
);
162 SCM_API SCM
scm_hashx_remove_x (SCM hash
, SCM assoc
, SCM table
, SCM obj
);
163 SCM_API SCM
scm_hash_fold (SCM proc
, SCM init
, SCM hash
);
164 SCM_API SCM
scm_hash_for_each (SCM proc
, SCM hash
);
165 SCM_API SCM
scm_hash_for_each_handle (SCM proc
, SCM hash
);
166 SCM_API SCM
scm_hash_map_to_list (SCM proc
, SCM hash
);
167 SCM_INTERNAL
void scm_i_hashtable_print (SCM exp
, SCM port
, scm_print_state
*pstate
);
168 SCM_INTERNAL
void scm_init_hashtab (void);
170 #endif /* SCM_HASHTAB_H */