libguile/hashtab.h

   1 /* classes: h_files */
   2
   3 #ifndef SCM_HASHTAB_H
   4 #define SCM_HASHTAB_H
   5
   6 /* Copyright (C) 1995,1996,1999,2000,2001, 2003, 2004, 2006, 2008, 2009 Free Software Foundation, Inc.
   7  *
   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.
  12  *
  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.
  17  *
  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
  21  * 02110-1301 USA
  22  */
  23
  24 \f
  25
  26 #include "libguile/__scm.h"
  27
  28 #include "weaks.h"
  29
  30 \f
  31
  32 #define SCM_HASHTABLEF_WEAK_CAR SCM_WVECTF_WEAK_KEY
  33 #define SCM_HASHTABLEF_WEAK_CDR SCM_WVECTF_WEAK_VALUE
  34
  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)
  57
  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)
  64
  65 /* Function that computes a hash of OBJ modulo MAX.  */
  66 typedef unsigned long (*scm_t_hash_fn) (SCM obj, unsigned long max,
  67                                         void *closure);
  68
  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);
  72
  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);
  76
  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,
  79                                    SCM result);
  80
  81 /* Function to iterate over the handles (key-value pairs) of a hash
  82    table.  */
  83 typedef SCM (*scm_t_hash_handle_fn) (void *closure, SCM handle);
  84
  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. */
  93 } scm_t_hashtable;
  94
  95 \f
  96
  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);
 103
 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);
 108
 109 SCM_INTERNAL void scm_i_rehash (SCM table, scm_t_hash_fn hash_fn,
 110                                 void *closure, const char *func_name);
 111
 112
 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,
 116                                     void *closure);
 117 SCM_INTERNAL
 118 SCM scm_hash_fn_get_handle_by_hash (SCM table, unsigned long raw_hash,
 119                                     scm_t_hash_predicate_fn predicate_fn,
 120                                     void *closure);
 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,
 124                                          void *closure);
 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,
 128                              void *closure);
 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,
 132                                void *closure);
 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,
 136                                   void *closure);
 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);
 142
 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);
 169
 170 #endif  /* SCM_HASHTAB_H */
 171
 172 /*
 173   Local Variables:
 174   c-file-style: "gnu"
 175   End:
 176 */