Mercurial

comparison dowa/d_memory.c @ 22:947b81010aba

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[Dowa & Seobeo] Updated so that Dowa hashmaps can use arena and not be broken. Split up web so taht it can handle different paths. Also fixes issues with hash collisions which was pain in the ass.
author June Park <parkjune1995@gmail.com>
date Tue, 07 Oct 2025 07:11:02 -0700
parents 09def63429b9
children 08a465eec50b
comparison
equal deleted inserted replaced
21:09def63429b9 22:947b81010aba
26 return currnet_ptr; 26 return currnet_ptr;
27 } 27 }
28 28
29 void Dowa_Arena_Destroy(Dowa_PArena p_arena) 29 void Dowa_Arena_Destroy(Dowa_PArena p_arena)
30 { 30 {
31 if (p_arena) 31 if (!p_arena) return;
32 { 32
33 if (p_arena->buffer) 33 if (p_arena->buffer)
34 free(p_arena->buffer); 34 free(p_arena->buffer);
35 free(p_arena); 35 free(p_arena);
36 } 36 }
37
38 void *Dowa_Arena_Copy(Dowa_PArena p_arena, const void *src, size_t size)
39 {
40 if (p_arena == NULL || src == NULL || size == 0)
41 return NULL;
42
43 void *dest = Dowa_Arena_Allocate(p_arena, size);
44 if (!dest)
45 return NULL;
46
47 memcpy(dest, src, size);
48 return dest;
37 } 49 }
38 50
39 // --- HashMap --- // 51 // --- HashMap --- //
40 Dowa_PHashMap Dowa_HashMap_Create(size_t capacity) 52 Dowa_PHashMap Dowa_HashMap_Create(size_t capacity)
41 { 53 {
51 free(p_hash_map); 63 free(p_hash_map);
52 return NULL; 64 return NULL;
53 } 65 }
54 p_hash_map->capacity = capacity; 66 p_hash_map->capacity = capacity;
55 p_hash_map->current_capacity = 0; 67 p_hash_map->current_capacity = 0;
68 p_hash_map->p_arena = NULL;
56 return p_hash_map; 69 return p_hash_map;
57 } 70 }
58 71
59 Dowa_PHashMap Dowa_HashMap_Create_With_Arena(size_t capacity, Dowa_PArena p_arena) 72 Dowa_PHashMap Dowa_HashMap_Create_With_Arena(size_t capacity, Dowa_PArena p_arena)
60 { 73 {
61 if (p_arena == NULL) 74 if (p_arena == NULL)
75 {
62 printf("Arena is NULL\n"); 76 printf("Arena is NULL\n");
63 return Dowa_HashMap_Create(capacity); 77 return Dowa_HashMap_Create(capacity);
78 }
64 79
65 Dowa_PHashMap p_hash_map; 80 Dowa_PHashMap p_hash_map;
66 p_hash_map = Dowa_Arena_Allocate(p_arena, sizeof(Dowa_HashMap)); 81 p_hash_map = Dowa_Arena_Allocate(p_arena, sizeof(Dowa_HashMap));
67 if (p_hash_map == NULL) 82 if (p_hash_map == NULL)
68 { 83 {
69 return NULL; 84 return NULL;
70 } 85 }
71 p_hash_map->entries = Dowa_Arena_Allocate(p_arena, sizeof(*p_hash_map->entries) * capacity); 86 p_hash_map->entries = Dowa_Arena_Allocate(p_arena, sizeof(*p_hash_map->entries) * capacity);
87 memset(p_hash_map->entries, 0, capacity * sizeof *p_hash_map->entries);
72 if (p_hash_map->entries == NULL) 88 if (p_hash_map->entries == NULL)
73 { 89 {
74 free(p_hash_map); 90 free(p_hash_map);
75 return NULL; 91 return NULL;
76 } 92 }
83 void Dowa_HashMap_Destroy(Dowa_PHashMap p_hash_map) 99 void Dowa_HashMap_Destroy(Dowa_PHashMap p_hash_map)
84 { 100 {
85 if (!p_hash_map) return; 101 if (!p_hash_map) return;
86 102
87 if (p_hash_map->p_arena) 103 if (p_hash_map->p_arena)
88 Dowa_Arena_Destroy(p_hash_map->p_arena); 104 {
105 // Free arena instead of the map...
106 // Dowa_Arena_Destroy(p_hash_map->p_arena);
107 return;
108 }
89 else 109 else
90 { 110 {
91 Dowa_PHashEntry entry; 111 Dowa_PHashEntry entry;
92 if (p_hash_map->entries) 112 if (p_hash_map->entries)
93 { 113 {
118 return hash_val % p_hash_map->capacity; 138 return hash_val % p_hash_map->capacity;
119 } 139 }
120 140
121 void *Dowa_HashMap_Get(Dowa_PHashMap p_hash_map, const char *key) 141 void *Dowa_HashMap_Get(Dowa_PHashMap p_hash_map, const char *key)
122 { 142 {
123 int idx_foo = Dowa_HashMap_Get_Position(p_hash_map, key); 143 int idx = Dowa_HashMap_Get_Position(p_hash_map, key);
124 void *value = p_hash_map->entries[idx_foo]; 144 Dowa_PHashEntry entry = p_hash_map->entries[idx];
125 if (value == NULL || strcmp(((Dowa_PHashEntry) value)->key, key) != 0) 145
126 { 146 while (entry)
127 return NULL; 147 {
128 } 148 if (strcmp(entry->key, key) == 0)
129 return ((Dowa_PHashEntry) value)->buffer; 149 {
130 } 150 return entry->buffer;
151 }
152 entry = entry->next;
153 }
154
155 return NULL;
156 }
157
131 158
132 int32 Dowa_HashMap_Push_Value_With_Type_NoCopy(Dowa_PHashMap p_hash_map, const char *key, 159 int32 Dowa_HashMap_Push_Value_With_Type_NoCopy(Dowa_PHashMap p_hash_map, const char *key,
133 void *value, size_t value_size, 160 void *value, size_t value_size,
134 Dowa_HashMap_ValueType type) 161 Dowa_HashMap_ValueType type)
135 { 162 {
136 int idx = Dowa_HashMap_Get_Position(p_hash_map, key); 163 int idx = Dowa_HashMap_Get_Position(p_hash_map, key);
137 Dowa_PHashEntry entry = p_hash_map->entries[idx]; 164 Dowa_PHashEntry entry = p_hash_map->entries[idx];
138 if (entry) 165 Dowa_PHashEntry prev = NULL;
139 free(entry->buffer); 166
140 else 167 // Old key
141 { 168 while (entry)
142 entry = p_hash_map->p_arena ? 169 {
143 Dowa_Arena_Allocate(p_hash_map->p_arena, sizeof(Dowa_HashEntry)) : 170 if (strcmp(entry->key, key) == 0)
144 malloc(sizeof(Dowa_HashEntry)); 171 {
145 if (entry == NULL) { perror("malloc or arena alloc"); return -1; } 172 if (!p_hash_map->p_arena && entry->buffer)
146 173 free(entry->buffer);
147 p_hash_map->entries[idx] = entry; 174 entry->buffer = value;
148 p_hash_map->current_capacity++; 175 entry->capacity = value_size;
149 entry->key = strdup(key); 176 entry->type = type;
150 } 177 return 0;
178 }
179 prev = entry;
180 entry = entry->next;
181 }
182
183 // New Key
184 entry = p_hash_map->p_arena ?
185 Dowa_Arena_Allocate(p_hash_map->p_arena, sizeof(Dowa_HashEntry)) :
186 malloc(sizeof(Dowa_HashEntry));
187 if (!entry) { perror("malloc or arena alloc"); return -1; }
188
189 entry->key = p_hash_map->p_arena ?
190 Dowa_Arena_Copy(p_hash_map->p_arena, key, strlen(key) + 1 /* \0 */) :
191 strdup(key);
151 entry->buffer = value; 192 entry->buffer = value;
152 entry->capacity = value_size; 193 entry->capacity = value_size;
153 entry->type = type; 194 entry->type = type;
195 entry->next = NULL;
196
197 if (prev)
198 prev->next = entry;
199 else
200 p_hash_map->entries[idx] = entry;
201
202 p_hash_map->current_capacity++;
154 return 0; 203 return 0;
155 } 204 }
156 205
157 int32 Dowa_HashMap_Push_Value_With_Type(Dowa_PHashMap p_hash_map, const char *key, 206 int32 Dowa_HashMap_Push_Value_With_Type(Dowa_PHashMap p_hash_map, const char *key,
158 void *value, size_t value_size, 207 void *value, size_t value_size,
159 Dowa_HashMap_ValueType type) 208 Dowa_HashMap_ValueType type)
160 { 209 {
161 int idx = Dowa_HashMap_Get_Position(p_hash_map, key); 210 int idx = Dowa_HashMap_Get_Position(p_hash_map, key);
162 Dowa_PHashEntry entry = p_hash_map->entries[idx]; 211 Dowa_PHashEntry entry = p_hash_map->entries[idx];
163 if (entry) 212 Dowa_PHashEntry prev = NULL;
164 free(entry->buffer); 213
165 else 214 // Check for existing key
166 { 215 while (entry)
167 entry = p_hash_map->p_arena ? 216 {
168 Dowa_Arena_Allocate(p_hash_map->p_arena, sizeof(Dowa_HashEntry)) : 217 if (strcmp(entry->key, key) == 0)
169 malloc(sizeof(Dowa_HashEntry)); 218 {
170 if (entry == NULL) { perror("malloc or arena alloc"); return -1; } 219 if (!p_hash_map->p_arena && entry->buffer)
171 220 free(entry->buffer);
172 p_hash_map->entries[idx] = entry; 221
173 p_hash_map->current_capacity++; 222 entry->buffer = p_hash_map->p_arena ?
174 entry->key = strdup(key); 223 Dowa_Arena_Allocate(p_hash_map->p_arena, value_size) :
175 } 224 malloc(value_size);
176 entry->buffer = p_hash_map->p_arena ? 225 if (!entry->buffer) { perror("malloc or arena alloc"); return -1; }
226
227 memcpy(entry->buffer, value, value_size);
228 entry->capacity = value_size;
229 entry->type = type;
230 return 0;
231 }
232 prev = entry;
233 entry = entry->next;
234 }
235
236 // New Key
237 entry = p_hash_map->p_arena ?
238 Dowa_Arena_Allocate(p_hash_map->p_arena, sizeof(Dowa_HashEntry)) :
239 malloc(sizeof(Dowa_HashEntry));
240 if (!entry) { perror("malloc or arena alloc"); return -1; }
241
242 entry->key = p_hash_map->p_arena ?
243 Dowa_Arena_Copy(p_hash_map->p_arena, key, strlen(key) + 1 /* \0 */) :
244 strdup(key);
245 if (!entry->key) { perror("strdup"); return -1; }
246
247 entry->buffer = p_hash_map->p_arena ?
177 Dowa_Arena_Allocate(p_hash_map->p_arena, value_size) : 248 Dowa_Arena_Allocate(p_hash_map->p_arena, value_size) :
178 malloc(value_size); 249 malloc(value_size);
179 250 if (!entry->buffer) { perror("malloc or arena alloc"); return -1; }
180 if (entry->buffer == NULL) { perror("malloc or arena alloc"); return -1; } 251
252 memcpy(entry->buffer, value, value_size);
181 entry->capacity = value_size; 253 entry->capacity = value_size;
182 entry->type = type; 254 entry->type = type;
183 memcpy(entry->buffer, value, value_size); 255 entry->next = NULL;
256
257 if (prev)
258 prev->next = entry;
259 else
260 p_hash_map->entries[idx] = entry;
261
262 p_hash_map->current_capacity++;
184 return 0; 263 return 0;
185 } 264 }
186 265
187 void Dowa_HashMap_Push_Value(Dowa_PHashMap p_hash_map, const char *key, void *value, size_t value_size) 266 void Dowa_HashMap_Push_Value(Dowa_PHashMap p_hash_map, const char *key, void *value, size_t value_size)
188 { 267 {
191 270
192 void Dowa_HashMap_Pop_Key(Dowa_PHashMap p_hash_map, const char *key) 271 void Dowa_HashMap_Pop_Key(Dowa_PHashMap p_hash_map, const char *key)
193 { 272 {
194 int idx = Dowa_HashMap_Get_Position(p_hash_map, key); 273 int idx = Dowa_HashMap_Get_Position(p_hash_map, key);
195 Dowa_PHashEntry entry = p_hash_map->entries[idx]; 274 Dowa_PHashEntry entry = p_hash_map->entries[idx];
196 if (entry) 275 if (entry && !(p_hash_map->p_arena))
197 { 276 {
198 free(entry->key); 277 free(entry->key);
199 free(entry->buffer); 278 free(entry->buffer);
200 free(entry); 279 free(entry);
201 } 280 }
210 { 289 {
211 printf("\n-----------\n\n"); 290 printf("\n-----------\n\n");
212 for (size_t i = 0; i < map->capacity; ++i) 291 for (size_t i = 0; i < map->capacity; ++i)
213 { 292 {
214 Dowa_PHashEntry e = map->entries[i]; 293 Dowa_PHashEntry e = map->entries[i];
215 if (!e) continue; 294 while (e)
216 printf("%s: ", e->key); 295 {
217 switch (e->type) 296 if (!e) break;
218 { 297 printf("%s: ", e->key);
219 case DOWA_HASH_MAP_TYPE_BUFFER: 298 switch (e->type)
220 { 299 {
221 unsigned char *p = e->buffer; 300 case DOWA_HASH_MAP_TYPE_BUFFER:
222 for (size_t j = 0; j < e->capacity; ++j) 301 {
223 { 302 unsigned char *p = e->buffer;
224 printf("%02x", p[j]); 303 for (size_t j = 0; j < e->capacity; ++j)
225 } 304 {
226 printf("\n"); 305 printf("%02x", p[j]);
227 } 306 }
228 break; 307 printf("\n");
229 case DOWA_HASH_MAP_TYPE_STRING: 308 }
230 { 309 break;
231 printf("%s\n", (char*)e->buffer); 310 case DOWA_HASH_MAP_TYPE_STRING:
232 } 311 {
233 break; 312 printf("%s\n", (char*)e->buffer);
234 case DOWA_HASH_MAP_TYPE_HASHMAP: 313 }
235 { 314 break;
236 printf("This is a hashmap with size of %zu, and pointer %p\n", (Dowa_PHashMap)e->capacity, (void *)e); 315 case DOWA_HASH_MAP_TYPE_HASHMAP:
237 } 316 {
238 break; 317 printf("This is a hashmap with size of %zu, and pointer %p\n", e->capacity, (void *)e);
239 case DOWA_HASH_MAP_TYPE_INT: 318 }
240 { 319 break;
241 printf("%d\n", *(int32*)e->buffer); 320 case DOWA_HASH_MAP_TYPE_INT:
242 } 321 {
243 break; 322 printf("%d\n", *(int32*)e->buffer);
244 default: 323 }
245 { 324 break;
246 printf("<unknown type>\n"); 325 default:
247 } 326 {
327 printf("<unknown type>\n");
328 }
329 }
330 e = e->next;
248 } 331 }
249 } 332 }
250 printf("-----------\n"); 333 printf("-----------\n");
251 } 334 }
252 335
275 size_t size = (size_t)st.st_size; 358 size_t size = (size_t)st.st_size;
276 FILE *f = fopen(fullpath, "rb"); 359 FILE *f = fopen(fullpath, "rb");
277 if (!f) { perror("fopen"); continue; } 360 if (!f) { perror("fopen"); continue; }
278 361
279 void *buf = p_hash_map->p_arena ? 362 void *buf = p_hash_map->p_arena ?
280 Dowa_Arena_Allocate(p_hash_map->p_arena, size) : 363 Dowa_Arena_Allocate(p_hash_map->p_arena, size+1) :
281 malloc(size); 364 malloc(size+1);
282 if (!buf) { perror("malloc"); fclose(f); closedir(dir); return -1; } 365 if (!buf) { perror("malloc"); fclose(f); closedir(dir); return -1; }
283 366
367
284 if (fread(buf, 1, size, f) != size) 368 if (fread(buf, 1, size, f) != size)
285 { 369 {
286 perror("fread"); 370 perror("fread");
287 free(buf); 371 if (!p_hash_map->p_arena) free(buf);
288 fclose(f); 372 fclose(f);
289 continue; 373 continue;
290 } 374 }
291 fclose(f); 375 fclose(f);
292 376
293 Dowa_HashMap_Push_Value_With_Type(p_hash_map, entry->d_name, buf, size, DOWA_HASH_MAP_TYPE_STRING); 377 // null-terminate since the files don't do this and we need this for print.
378 ((unsigned char*)buf)[size] = '\0';
379
380 Dowa_HashMap_Push_Value_With_Type(p_hash_map, entry->d_name, buf, size + 1, DOWA_HASH_MAP_TYPE_STRING);
294 free(buf); // Dowa_HashMap_PushValue made its own copy 381 free(buf); // Dowa_HashMap_PushValue made its own copy
295 } 382 }
296 else if (S_ISDIR(st.st_mode)) 383 else if (S_ISDIR(st.st_mode))
297 { 384 {
385 // TODO: Adjust the sizes of the recursive map?
298 Dowa_PHashMap p_child_map = Dowa_HashMap_Create_With_Arena(100, p_hash_map->p_arena); 386 Dowa_PHashMap p_child_map = Dowa_HashMap_Create_With_Arena(100, p_hash_map->p_arena);
299 if (!p_child_map) 387 if (!p_child_map)
300 { 388 {
301 perror("Dowa_HashMap_Create"); 389 perror("Dowa_HashMap_Create");
302 return -1; 390 return -1;