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