1 /* hashtable.h -*- mode:c; coding:utf-8; -*- 2 * 3 * Copyright (c) 2010-2021 Takashi Kato <ktakashi@ymail.com> 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * $Id: $ 29 */ 30 #ifndef SAGITTARIUS_PRIVATE_HASHTABLE_H_ 31 #define SAGITTARIUS_PRIVATE_HASHTABLE_H_ 32 33 #include "sagittariusdefs.h" 34 #include "collection.h" 35 #include "clos.h" 36 37 typedef enum { 38 SG_HASH_EQ, 39 SG_HASH_EQV, 40 SG_HASH_EQUAL, 41 SG_HASH_STRING, 42 SG_HASH_GENERAL, 43 } SgHashType; 44 45 typedef struct SgHashCoreRec SgHashCore; 46 typedef struct SgHashIterRec SgHashIter; 47 48 typedef unsigned long SgHashVal; 49 /* hasher */ 50 typedef SgHashVal SgHashProc(const SgHashCore *hc, intptr_t key); 51 /* tester */ 52 typedef int SgHashCompareProc(const SgHashCore *hc, intptr_t key, 53 intptr_t entryKey); 54 55 typedef SgDictEntry SgHashEntry; 56 /* 57 TODO use comparator. 58 */ 59 struct SgHashCoreRec 60 { 61 void **buckets; 62 long bucketCount; 63 long entryCount; 64 long bucketsLog2Count; 65 void *access; 66 SgHashProc *hasher; 67 SgHashCompareProc *compare; 68 SgObject generalHasher; /* for make-hashtable */ 69 SgObject generalCompare; /* ditto */ 70 void *data; 71 /* how to create entry of this hash */ 72 void (*create_entry)(SgHashCore *, SgHashEntry *); 73 }; 74 75 struct SgHashIterRec 76 { 77 SgHashCore *core; 78 long bucket; 79 void *next; 80 SgObject table; /* need for weak hashtable */ 81 /* Iterator itself should have next operation */ 82 SgHashEntry *(*iter_next)(SgHashIter *, 83 SgObject *key /* out */, 84 SgObject *val /* out */); 85 }; 86 87 SG_CLASS_DECL(Sg_HashTableClass); 88 #define SG_CLASS_HASHTABLE (&Sg_HashTableClass) 89 90 /* 91 To make hashtable and weak-hashtable have the same interface. 92 */ 93 typedef struct SgHashOpTableRec 94 { 95 /* entry ref: table entry flags*/ 96 SgObject (*ref)(SgObject, SgHashEntry *, int); 97 /* entry set: table entry value flags */ 98 SgObject (*set)(SgObject, SgHashEntry *, SgObject, int); 99 /* we can't use delete since it's keyword on C++... */ 100 /* table key */ 101 SgObject (*remove)(SgObject, SgObject); 102 /* table mutableP */ 103 SgObject (*copy)(SgObject, int); 104 /* we also need this */ 105 void (*init_iter)(SgObject, SgHashIter *); 106 } SgHashOpTable; 107 108 struct SgHashTableRec 109 { 110 SG_HEADER; 111 char immutablep; 112 SgHashType type; 113 SgHashCore core; 114 SgHashOpTable *opTable; 115 }; 116 117 #define SG_HASH_NO_OVERWRITE SG_DICT_NO_OVERWRITE 118 #define SG_HASH_NO_CREATE SG_DICT_NO_CREATE 119 120 #define SG_HASHTABLE_P(obj) SG_ISA(obj, SG_CLASS_HASHTABLE) 121 #define SG_HASHTABLE(obj) ((SgHashTable*)(obj)) 122 #define SG_HASHTABLE_CORE(obj) (&SG_HASHTABLE(obj)->core) 123 #define SG_HASH_ENTRY_KEY SG_DICT_ENTRY_KEY 124 #define SG_HASH_ENTRY_VALUE SG_DICT_ENTRY_VALUE 125 #define SG_HASH_ENTRY_SET_VALUE SG_DICT_ENTRY_SET_VALUE 126 #define SG_HASHTABLE_OPTABLE(obj) SG_HASHTABLE(obj)->opTable 127 #define SG_HASHTABLE_TYPE(obj) SG_HASHTABLE(obj)->type 128 129 #define SG_HASHTABLE_ENTRY_REF(ht, e, f) \ 130 SG_HASHTABLE_OPTABLE(ht)->ref(ht, e, f) 131 #define SG_HASHTABLE_ENTRY_SET(ht, e, v, f) \ 132 SG_HASHTABLE_OPTABLE(ht)->set(ht, e, v, f) 133 134 #define SG_IMMUTABLE_HASHTABLE_P(obj) \ 135 (SG_HASHTABLE_P(obj) && SG_HASHTABLE(obj)->immutablep) 136 137 /* hash core seaerch flags */ 138 typedef enum { 139 SG_HASH_NO_ERROR = (1L<<0), /* don't raise an error on hashtable level */ 140 } SgHashRefFlag; 141 142 143 SG_CDECL_BEGIN 144 /* hash core */ 145 SG_EXTERN void Sg_HashCoreInitSimple(SgHashCore *core, 146 SgHashType type, 147 long initSize, 148 void *data); 149 SG_EXTERN void Sg_HashCoreInitGeneral(SgHashCore *core, 150 SgHashProc *hasher, 151 SgHashCompareProc *compare, 152 long initSize, 153 void *data); 154 SG_EXTERN int Sg_HashCoreTypeToProcs(SgHashType type, SgHashProc **hasher, 155 SgHashCompareProc **compare); 156 SG_EXTERN SgHashEntry* Sg_HashCoreSearch(SgHashCore *table, intptr_t key, 157 SgDictOp op, int flags); 158 /* core operation to copy hashtable structure */ 159 SG_EXTERN void Sg_HashCoreCopy(SgHashTable *dst, const SgHashTable *src); 160 SG_EXTERN void Sg_HashCoreClear(SgHashCore *ht, long k); 161 162 /* iterator */ 163 SG_EXTERN void Sg_HashIterInit(SgObject table, SgHashIter *itr); 164 /* this return entry itself for convenience */ 165 SG_EXTERN SgHashEntry* Sg_HashIterNext(SgHashIter *itr, 166 SgObject *key /* out */, 167 SgObject *val /* out */); 168 169 /* hasher */ 170 SG_EXTERN SgHashVal Sg_EqHash(SgObject obj, SgHashVal bound); 171 SG_EXTERN SgHashVal Sg_EqvHash(SgObject obj, SgHashVal bound); 172 SG_EXTERN SgHashVal Sg_EqualHash(SgObject obj, SgHashVal bound); 173 SG_EXTERN SgHashVal Sg_StringHash(SgString *str, SgHashVal bound); 174 175 SG_EXTERN SgObject Sg_MakeHashTableSimple(SgHashType type, long initSize); 176 SG_EXTERN SgObject Sg_InitHashTableSimple(SgHashTable *table, 177 SgHashType type, long initSize); 178 179 SG_EXTERN SgObject Sg_MakeHashTable(SgObject hasher, 180 SgObject compare, long initSize); 181 SG_EXTERN SgObject Sg_MakeHashTableWithComparator(SgObject comparator, 182 long initSize); 183 184 SG_EXTERN SgObject Sg_HashTableCopy(SgHashTable *table, int mutableP); 185 186 SG_EXTERN SgObject Sg_HashTableRef(SgHashTable *table, SgObject key, 187 SgObject fallback); 188 SG_EXTERN SgObject Sg_HashTableSet(SgHashTable *table, SgObject key, 189 SgObject value, int flags); 190 SG_EXTERN SgObject Sg_HashTableDelete(SgHashTable *table, SgObject key); 191 192 SG_EXTERN SgObject Sg_HashTableAddAll(SgHashTable *dst, SgHashTable *src); 193 SG_EXTERN SgObject Sg_HashTableKeys(SgHashTable *table); 194 SG_EXTERN SgObject Sg_HashTableValues(SgHashTable *table); 195 /* status for hash table */ 196 SG_EXTERN SgObject Sg_HashTableStat(SgHashTable *table); 197 198 SG_EXTERN long Sg_HashTableSize(SgHashTable *table); 199 200 SG_CDECL_END 201 202 #endif /* SAGITTARIUS_HASHTABLE_H_ */ 203 204 /* 205 end of file 206 Local Variables: 207 coding: utf-8-unix 208 End: 209 */ 210