1 /* 2 * hash.h - Public API for hashtables 3 * 4 * Copyright (c) 2000-2020 Shiro Kawai <shiro@acm.org> 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * 3. Neither the name of the authors nor the names of its contributors 18 * may be used to endorse or promote products derived from this 19 * software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 /* This file is included from gauche.h */ 35 36 #ifndef GAUCHE_HASH_H 37 #define GAUCHE_HASH_H 38 39 /*================================================================ 40 * ScmHashCore 41 */ 42 43 /* Hash types */ 44 typedef enum { 45 SCM_HASH_EQ, 46 SCM_HASH_EQV, 47 SCM_HASH_EQUAL, 48 SCM_HASH_STRING, 49 SCM_HASH_GENERAL, 50 51 SCM_HASH_WORD 52 } ScmHashType; 53 54 typedef struct ScmHashCoreRec ScmHashCore; 55 typedef struct ScmHashIterRec ScmHashIter; 56 57 /* Called when the hashtable needs to calculate a hash value from 58 the key given to Scm_HashCoreSearch. Returns a hash value. */ 59 typedef u_long ScmHashProc(const ScmHashCore *hc, intptr_t key); 60 61 /* Called when the hashtable needs to compare the given key KEY 62 with an entry's key ENTRYKEY. */ 63 typedef int ScmHashCompareProc(const ScmHashCore *hc, intptr_t key, 64 intptr_t entrykey); 65 66 struct ScmHashCoreRec { 67 void **buckets; 68 int numBuckets; 69 int numEntries; 70 int numBucketsLog2; 71 void *accessfn; /* actual type hidden */ 72 ScmHashProc *hashfn; 73 ScmHashCompareProc *cmpfn; 74 void *data; 75 }; 76 77 SCM_EXTERN void Scm_HashCoreInitSimple(ScmHashCore *core, 78 ScmHashType type, 79 unsigned int initSize, 80 void *data); 81 82 SCM_EXTERN void Scm_HashCoreInitGeneral(ScmHashCore *core, 83 ScmHashProc *hashfn, 84 ScmHashCompareProc *cmpfn, 85 unsigned int initSize, 86 void *data); 87 88 SCM_EXTERN int Scm_HashCoreTypeToProcs(ScmHashType type, 89 ScmHashProc **hashfn, 90 ScmHashCompareProc **cmpfn); 91 92 SCM_EXTERN void Scm_HashCoreCopy(ScmHashCore *dst, const ScmHashCore *src); 93 94 SCM_EXTERN ScmDictEntry *Scm_HashCoreSearch(ScmHashCore *core, 95 intptr_t key, 96 ScmDictOp op); 97 98 SCM_EXTERN int Scm_HashCoreNumEntries(ScmHashCore *core); 99 100 SCM_EXTERN void Scm_HashCoreClear(ScmHashCore *core); 101 102 struct ScmHashIterRec { 103 ScmHashCore *core; 104 int bucket; 105 void *next; 106 }; 107 108 SCM_EXTERN void Scm_HashIterInit(ScmHashIter *iter, ScmHashCore *core); 109 SCM_EXTERN ScmDictEntry *Scm_HashIterNext(ScmHashIter *iter); 110 111 /* 112 * Hash functions 113 */ 114 SCM_EXTERN u_long Scm_EqHash(ScmObj obj); 115 SCM_EXTERN u_long Scm_EqvHash(ScmObj obj); 116 SCM_EXTERN u_long Scm_HashString(ScmString *str, u_long bound); 117 SCM_EXTERN u_long Scm_PortableHash(ScmObj obj, u_long salt); 118 SCM_EXTERN ScmSmallInt Scm_DefaultHash(ScmObj obj); 119 SCM_EXTERN ScmSmallInt Scm_RecursiveHash(ScmObj obj, 120 ScmSmallInt salt, 121 u_long flags); 122 SCM_EXTERN ScmSmallInt Scm_SmallIntHash(ScmSmallInt val, 123 ScmSmallInt salt, 124 u_long flags); 125 SCM_EXTERN ScmSmallInt Scm_Int64Hash(int64_t val, 126 ScmSmallInt salt, 127 u_long flags); 128 SCM_EXTERN u_long Scm_CombineHashValue(u_long a, u_long b); 129 130 SCM_EXTERN ScmSmallInt Scm_HashSaltRef(void); 131 SCM_EXTERN ScmSmallInt Scm_HashSaltSet(ScmSmallInt); 132 SCM_EXTERN ScmSmallInt Scm_PortableHashSalt(ScmObj newval); 133 134 SCM_EXTERN ScmObj Scm_CurrentRecursiveHash(ScmObj); 135 136 SCM_EXTERN u_long Scm_Hash(ScmObj obj); /* DEPRECATED */ 137 138 /*================================================================ 139 * ScmHashTable 140 */ 141 142 struct ScmHashTableRec { 143 SCM_HEADER; 144 ScmHashType type; 145 ScmHashCore core; 146 }; 147 148 SCM_CLASS_DECL(Scm_HashTableClass); 149 #define SCM_CLASS_HASH_TABLE (&Scm_HashTableClass) 150 #define SCM_HASH_TABLE(obj) ((ScmHashTable*)(obj)) 151 #define SCM_HASH_TABLE_P(obj) SCM_ISA(obj, SCM_CLASS_HASH_TABLE) 152 153 #define SCM_HASH_TABLE_CORE(obj) (&SCM_HASH_TABLE(obj)->core) 154 155 SCM_EXTERN ScmObj Scm_MakeHashTableSimple(ScmHashType type, 156 unsigned int initSize); 157 SCM_EXTERN ScmObj Scm_MakeHashTableFull(ScmHashProc *hashfn, 158 ScmHashCompareProc *cmpfn, 159 unsigned int initSize, 160 void *data); 161 162 SCM_EXTERN ScmHashType Scm_HashTableType(ScmHashTable *tab); 163 164 SCM_EXTERN ScmObj Scm_HashTableCopy(ScmHashTable *tab); 165 166 SCM_EXTERN ScmObj Scm_HashTableRef(ScmHashTable *ht, 167 ScmObj key, ScmObj fallback); 168 SCM_EXTERN ScmObj Scm_HashTableSet(ScmHashTable *ht, 169 ScmObj key, ScmObj value, int flags); 170 SCM_EXTERN ScmObj Scm_HashTableDelete(ScmHashTable *ht, ScmObj key); 171 172 173 SCM_EXTERN ScmObj Scm_HashTableKeys(ScmHashTable *table); 174 SCM_EXTERN ScmObj Scm_HashTableValues(ScmHashTable *table); 175 176 SCM_EXTERN ScmObj Scm_HashTableStat(ScmHashTable *table); 177 178 179 /*==================================================================== 180 * For backward compatibility. DEPRECATED. 181 */ 182 183 #if GAUCHE_API_VERSION < 1000 184 185 #define SCM_HASHTABLE(x) SCM_HASH_TABLE(x) 186 #define SCM_HASHTABLEP(x) SCM_HASH_TABLE_P(x) 187 #define SCM_CLASS_HASHTABLE SCM_CLASS_HASH_TABLE 188 #define SCM_HASH_ADDRESS SCM_HASH_EQ 189 190 typedef struct ScmHashEntryRec { 191 void *key; 192 void *value; 193 } ScmHashEntry; 194 195 SCM_EXTERN ScmHashEntry *Scm_HashTableGet(ScmHashTable *hash, ScmObj key); 196 SCM_EXTERN ScmHashEntry *Scm_HashTableAdd(ScmHashTable *hash, 197 ScmObj key, ScmObj value); 198 SCM_EXTERN ScmHashEntry *Scm_HashTablePut(ScmHashTable *hash, 199 ScmObj key, ScmObj value); 200 201 SCM_EXTERN ScmObj Scm_MakeHashTable(ScmHashProc *hashfn, 202 ScmHashCompareProc *cmpfn, 203 unsigned int initSize); 204 205 #endif /*GAUCHE_API_VERSION < 1000*/ 206 207 #endif /* GAUCHE_HASH_H */ 208 209