1 /*
2 * Copyright (C) 2019 Alexander Borisov
3 *
4 * Author: Alexander Borisov <borisov@lexbor.com>
5 */
6
7 #ifndef LEXBOR_HASH_H
8 #define LEXBOR_HASH_H
9
10 #ifdef __cplusplus
11 extern "C" {
12 #endif
13
14 #include "lexbor/core/dobject.h"
15 #include "lexbor/core/mraw.h"
16
17
18 #define LEXBOR_HASH_SHORT_SIZE 16
19 #define LEXBOR_HASH_TABLE_MIN_SIZE 32
20
21
22 typedef struct lexbor_hash_search lexbor_hash_search_t;
23 typedef struct lexbor_hash_insert lexbor_hash_insert_t;
24
25 #ifndef LEXBOR_HASH_EXTERN
26 LXB_EXTERN const lexbor_hash_insert_t *lexbor_hash_insert_raw;
27 LXB_EXTERN const lexbor_hash_insert_t *lexbor_hash_insert_lower;
28 LXB_EXTERN const lexbor_hash_insert_t *lexbor_hash_insert_upper;
29
30 LXB_EXTERN const lexbor_hash_search_t *lexbor_hash_search_raw;
31 LXB_EXTERN const lexbor_hash_search_t *lexbor_hash_search_lower;
32 LXB_EXTERN const lexbor_hash_search_t *lexbor_hash_search_upper;
33 #endif
34
35 /*
36 * FIXME:
37 * It is necessary to add the rebuild of a hash table
38 * and optimize collisions.
39 */
40
41 typedef struct lexbor_hash lexbor_hash_t;
42 typedef struct lexbor_hash_entry lexbor_hash_entry_t;
43
44 typedef uint32_t
45 (*lexbor_hash_id_f)(const lxb_char_t *key, size_t size);
46
47 typedef lxb_status_t
48 (*lexbor_hash_copy_f)(lexbor_hash_t *hash, lexbor_hash_entry_t *entry,
49 const lxb_char_t *key, size_t size);
50
51 typedef bool
52 (*lexbor_hash_cmp_f)(const lxb_char_t *first,
53 const lxb_char_t *second, size_t size);
54
55 struct lexbor_hash_entry {
56 union {
57 lxb_char_t *long_str;
58 lxb_char_t short_str[LEXBOR_HASH_SHORT_SIZE + 1];
59 } u;
60
61 size_t length;
62
63 lexbor_hash_entry_t *next;
64 };
65
66 struct lexbor_hash {
67 lexbor_dobject_t *entries;
68 lexbor_mraw_t *mraw;
69
70 lexbor_hash_entry_t **table;
71 size_t table_size;
72
73 size_t struct_size;
74 };
75
76 struct lexbor_hash_insert {
77 lexbor_hash_id_f hash; /* For generate a hash id. */
78 lexbor_hash_cmp_f cmp; /* For compare key. */
79 lexbor_hash_copy_f copy; /* For copy key. */
80 };
81
82 struct lexbor_hash_search {
83 lexbor_hash_id_f hash; /* For generate a hash id. */
84 lexbor_hash_cmp_f cmp; /* For compare key. */
85 };
86
87
88 LXB_API lexbor_hash_t *
89 lexbor_hash_create(void);
90
91 LXB_API lxb_status_t
92 lexbor_hash_init(lexbor_hash_t *hash, size_t table_size, size_t struct_size);
93
94 LXB_API void
95 lexbor_hash_clean(lexbor_hash_t *hash);
96
97 LXB_API lexbor_hash_t *
98 lexbor_hash_destroy(lexbor_hash_t *hash, bool destroy_obj);
99
100
101 LXB_API void *
102 lexbor_hash_insert(lexbor_hash_t *hash, const lexbor_hash_insert_t *insert,
103 const lxb_char_t *key, size_t length);
104
105 LXB_API void *
106 lexbor_hash_insert_by_entry(lexbor_hash_t *hash, lexbor_hash_entry_t *entry,
107 const lexbor_hash_search_t *search,
108 const lxb_char_t *key, size_t length);
109
110 LXB_API void
111 lexbor_hash_remove(lexbor_hash_t *hash, const lexbor_hash_search_t *search,
112 const lxb_char_t *key, size_t length);
113
114 LXB_API void *
115 lexbor_hash_search(lexbor_hash_t *hash, const lexbor_hash_search_t *search,
116 const lxb_char_t *key, size_t length);
117
118 LXB_API void
119 lexbor_hash_remove_by_hash_id(lexbor_hash_t *hash, uint32_t hash_id,
120 const lxb_char_t *key, size_t length,
121 const lexbor_hash_cmp_f cmp_func);
122
123 LXB_API void *
124 lexbor_hash_search_by_hash_id(lexbor_hash_t *hash, uint32_t hash_id,
125 const lxb_char_t *key, size_t length,
126 const lexbor_hash_cmp_f cmp_func);
127
128
129 LXB_API uint32_t
130 lexbor_hash_make_id(const lxb_char_t *key, size_t length);
131
132 LXB_API uint32_t
133 lexbor_hash_make_id_lower(const lxb_char_t *key, size_t length);
134
135 LXB_API uint32_t
136 lexbor_hash_make_id_upper(const lxb_char_t *key, size_t length);
137
138 LXB_API lxb_status_t
139 lexbor_hash_copy(lexbor_hash_t *hash, lexbor_hash_entry_t *entry,
140 const lxb_char_t *key, size_t length);
141
142 LXB_API lxb_status_t
143 lexbor_hash_copy_lower(lexbor_hash_t *hash, lexbor_hash_entry_t *entry,
144 const lxb_char_t *key, size_t length);
145
146 LXB_API lxb_status_t
147 lexbor_hash_copy_upper(lexbor_hash_t *hash, lexbor_hash_entry_t *entry,
148 const lxb_char_t *key, size_t length);
149
150
151 /*
152 * Inline functions
153 */
154 lxb_inline lexbor_mraw_t *
lexbor_hash_mraw(const lexbor_hash_t * hash)155 lexbor_hash_mraw(const lexbor_hash_t *hash)
156 {
157 return hash->mraw;
158 }
159
160 lxb_inline lxb_char_t *
lexbor_hash_entry_str(const lexbor_hash_entry_t * entry)161 lexbor_hash_entry_str(const lexbor_hash_entry_t *entry)
162 {
163 if (entry->length <= LEXBOR_HASH_SHORT_SIZE) {
164 return (lxb_char_t *) entry->u.short_str;
165 }
166
167 return entry->u.long_str;
168 }
169
170 lxb_inline lxb_char_t *
lexbor_hash_entry_str_set(lexbor_hash_entry_t * entry,lxb_char_t * data,size_t length)171 lexbor_hash_entry_str_set(lexbor_hash_entry_t *entry,
172 lxb_char_t *data, size_t length)
173 {
174 entry->length = length;
175
176 if (length <= LEXBOR_HASH_SHORT_SIZE) {
177 memcpy(entry->u.short_str, data, length);
178 return (lxb_char_t *) entry->u.short_str;
179 }
180
181 entry->u.long_str = data;
182 return entry->u.long_str;
183 }
184
185 lxb_inline void
lexbor_hash_entry_str_free(lexbor_hash_t * hash,lexbor_hash_entry_t * entry)186 lexbor_hash_entry_str_free(lexbor_hash_t *hash, lexbor_hash_entry_t *entry)
187 {
188 if (entry->length > LEXBOR_HASH_SHORT_SIZE) {
189 lexbor_mraw_free(hash->mraw, entry->u.long_str);
190 }
191
192 entry->length = 0;
193 }
194
195 lxb_inline lexbor_hash_entry_t *
lexbor_hash_entry_create(lexbor_hash_t * hash)196 lexbor_hash_entry_create(lexbor_hash_t *hash)
197 {
198 return (lexbor_hash_entry_t *) lexbor_dobject_calloc(hash->entries);
199 }
200
201 lxb_inline lexbor_hash_entry_t *
lexbor_hash_entry_destroy(lexbor_hash_t * hash,lexbor_hash_entry_t * entry)202 lexbor_hash_entry_destroy(lexbor_hash_t *hash, lexbor_hash_entry_t *entry)
203 {
204 return (lexbor_hash_entry_t *) lexbor_dobject_free(hash->entries, entry);
205 }
206
207 lxb_inline size_t
lexbor_hash_entries_count(lexbor_hash_t * hash)208 lexbor_hash_entries_count(lexbor_hash_t *hash)
209 {
210 return lexbor_dobject_allocated(hash->entries);
211 }
212
213
214 #ifdef __cplusplus
215 } /* extern "C" */
216 #endif
217
218 #endif /* LEXBOR_HASH_H */
219
