1 #include "string_store.h"
2 #include <stdint.h>
3 #include <string.h>
4 #include <stdlib.h>
5 #include <stdio.h>
6 #include <unistd.h>
7 #include <fcntl.h>
8 #include <sys/mman.h>
9 #include <sys/stat.h>
10 #include <sys/types.h>
11
12 #ifdef RADB_MEM_GC
13 #include <gc/gc.h>
14 #endif
15
16 typedef struct entry_t {
17 uint32_t Link, Length;
18 } entry_t;
19
20 #define MAKE_VERSION(MAJOR, MINOR) (0xFF000000 + (MAJOR << 16) + (MINOR << 8))
21
22 #define SIGNATURE 0x53534152
23 #define VERSION MAKE_VERSION(1, 0)
24
25 typedef struct header_t {
26 uint32_t Signature, Version;
27 uint32_t NodeSize, ChunkSize;
28 uint32_t NumEntries, NumNodes, NumFreeNodes, FreeNode;
29 uint32_t FreeEntry, Reserved;
30 entry_t Entries[];
31 } header_t;
32
33 struct string_store_t {
34 #ifdef RADB_MEM_PER_STORE
35 void *Allocator;
36 void *(*alloc)(void *, size_t);
37 void *(*alloc_atomic)(void *, size_t);
38 void (*free)(void *, void *);
39 #endif
40 const char *Prefix;
41 header_t *Header;
42 void *Data;
43 size_t HeaderSize;
44 int HeaderFd, DataFd;
45 };
46
47 #define NODE_LINK(Node) (*(uint32_t *)(Node + NodeSize - 4))
48
49 #ifdef RADB_MEM_PER_STORE
radb_strdup(const char * String,void * Allocator,void * (* alloc_atomic)(void *,size_t))50 static inline const char *radb_strdup(const char *String, void *Allocator, void *(*alloc_atomic)(void *, size_t)) {
51 size_t Length = strlen(String);
52 char *Copy = alloc_atomic(Allocator, Length + 1);
53 strcpy(Copy, String);
54 return Copy;
55 }
56 #endif
57
string_store_create(const char * Prefix,size_t RequestedSize,size_t ChunkSize RADB_MEM_PARAMS)58 string_store_t *string_store_create(const char *Prefix, size_t RequestedSize, size_t ChunkSize RADB_MEM_PARAMS) {
59 #if defined(RADB_MEM_MALLOC)
60 string_store_t *Store = malloc(sizeof(string_store_t));
61 Store->Prefix = strdup(Prefix);
62 #elif defined(RADB_MEM_GC)
63 string_store_t *Store = GC_malloc(sizeof(string_store_t));
64 Store->Prefix = GC_strdup(Prefix);
65 #else
66 string_store_t *Store = alloc(Allocator, sizeof(string_store_t));
67 Store->Prefix = radb_strdup(Prefix, Allocator, alloc_atomic);
68 Store->Allocator = Allocator;
69 Store->alloc = alloc;
70 Store->alloc_atomic = alloc_atomic;
71 Store->free = free;
72 #endif
73 size_t NodeSize = 8;
74 while (NodeSize < RequestedSize) NodeSize *= 2;
75 if (!ChunkSize) ChunkSize = 512;
76 int NumEntries = (512 - sizeof(header_t)) / sizeof(entry_t);
77 int NumNodes = (ChunkSize + NodeSize - 1) / NodeSize;
78 char FileName[strlen(Prefix) + 10];
79 sprintf(FileName, "%s.entries", Prefix);
80 Store->HeaderFd = open(FileName, O_RDWR | O_CREAT, 0777);
81 Store->HeaderSize = sizeof(header_t) + NumEntries * sizeof(entry_t);
82 ftruncate(Store->HeaderFd, Store->HeaderSize);
83 Store->Header = mmap(NULL, Store->HeaderSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->HeaderFd, 0);
84 Store->Header->Signature = SIGNATURE;
85 Store->Header->Version = VERSION;
86 Store->Header->NodeSize = NodeSize;
87 Store->Header->ChunkSize = NumNodes;
88 Store->Header->NumEntries = NumEntries;
89 Store->Header->NumNodes = NumNodes;
90 Store->Header->NumFreeNodes = NumNodes;
91 Store->Header->FreeNode = 0;
92 Store->Header->FreeEntry = 0;
93 for (int I = 0; I < NumEntries; ++I) {
94 Store->Header->Entries[I].Link = INVALID_INDEX;
95 Store->Header->Entries[I].Length = 0;
96 }
97 sprintf(FileName, "%s.data", Prefix);
98 Store->DataFd = open(FileName, O_RDWR | O_CREAT, 0777);
99 ftruncate(Store->DataFd, NumNodes * NodeSize);
100 Store->Data = mmap(NULL, Store->Header->NumNodes * Store->Header->NodeSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->DataFd, 0);
101 for (int I = 1; I <= NumNodes; ++I) {
102 *(uint32_t *)(Store->Data + I * NodeSize - 4) = I;
103 }
104 //msync(Store->Header, Store->HeaderSize, MS_ASYNC);
105 //msync(Store->Data, Store->Header->NumNodes * NodeSize, MS_ASYNC);
106 return Store;
107 }
108
string_store_open(const char * Prefix RADB_MEM_PARAMS)109 string_store_t *string_store_open(const char *Prefix RADB_MEM_PARAMS) {
110 struct stat Stat[1];
111 char FileName[strlen(Prefix) + 10];
112 sprintf(FileName, "%s.entries", Prefix);
113 if (stat(FileName, Stat)) return NULL;
114 #if defined(RADB_MEM_MALLOC)
115 string_store_t *Store = malloc(sizeof(string_store_t));
116 Store->Prefix = strdup(Prefix);
117 #elif defined(RADB_MEM_GC)
118 string_store_t *Store = GC_malloc(sizeof(string_store_t));
119 Store->Prefix = GC_strdup(Prefix);
120 #else
121 string_store_t *Store = alloc(Allocator, sizeof(string_store_t));
122 Store->Prefix = radb_strdup(Prefix, Allocator, alloc_atomic);
123 Store->Allocator = Allocator;
124 Store->alloc = alloc;
125 Store->alloc_atomic = alloc_atomic;
126 Store->free = free;
127 #endif
128 Store->HeaderFd = open(FileName, O_RDWR, 0777);
129 Store->HeaderSize = Stat->st_size;
130 Store->Header = mmap(NULL, Store->HeaderSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->HeaderFd, 0);
131 if (Store->Header->Signature != SIGNATURE) {
132 puts("Header mismatch - aborting");
133 munmap(Store->Header, Store->HeaderSize);
134 close(Store->HeaderFd);
135 return NULL;
136 }
137 sprintf(FileName, "%s.data", Prefix);
138 Store->DataFd = open(FileName, O_RDWR, 0777);
139 Store->Data = mmap(NULL, Store->Header->NumNodes * Store->Header->NodeSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->DataFd, 0);
140 return Store;
141 }
142
string_store_close(string_store_t * Store)143 void string_store_close(string_store_t *Store) {
144 //msync(Store->Data, Store->Header->NumNodes * Store->Header->NodeSize, MS_SYNC);
145 //msync(Store->Header, Store->HeaderSize, MS_SYNC);
146 munmap(Store->Data, Store->Header->NumNodes * Store->Header->NodeSize);
147 munmap(Store->Header, Store->HeaderSize);
148 close(Store->DataFd);
149 close(Store->HeaderFd);
150 #if defined(RADB_MEM_MALLOC)
151 free((void *)Store->Prefix);
152 free(Store);
153 #elif defined(RADB_MEM_GC)
154 #else
155 Store->free(Store->Allocator, (void *)Store->Prefix);
156 Store->free(Store->Allocator, Store);
157 #endif
158 }
159
string_store_num_entries(string_store_t * Store)160 size_t string_store_num_entries(string_store_t *Store) {
161 return Store->Header->NumEntries;
162 }
163
string_store_size(string_store_t * Store,size_t Index)164 size_t string_store_size(string_store_t *Store, size_t Index) {
165 if (Index >= Store->Header->NumEntries) return 0;
166 return Store->Header->Entries[Index].Length;
167 }
168
string_store_get(string_store_t * Store,size_t Index,void * Buffer,size_t Space)169 size_t string_store_get(string_store_t *Store, size_t Index, void *Buffer, size_t Space) {
170 if (Index >= Store->Header->NumEntries) return 0;
171 size_t Length = Store->Header->Entries[Index].Length;
172 size_t Link = Store->Header->Entries[Index].Link;
173 size_t NodeSize = Store->Header->NodeSize;
174 void *Node = Store->Data + Link * NodeSize;
175 size_t Total = (Space < Length) ? Space : Length;
176 while (Length > NodeSize) {
177 if (Space < NodeSize - 4) {
178 memcpy(Buffer, Node, Space);
179 return Total;
180 }
181 memcpy(Buffer, Node, NodeSize - 4);
182 Buffer += NodeSize - 4;
183 Length -= NodeSize - 4;
184 Space -= NodeSize - 4;
185 Node = Store->Data + NodeSize * NODE_LINK(Node);
186 }
187 memcpy(Buffer, Node, (Space < Length) ? Space : Length);
188 return Total;
189 }
190
string_store_compare(string_store_t * Store,const void * Other,size_t Length,size_t Index)191 int string_store_compare(string_store_t *Store, const void *Other, size_t Length, size_t Index) {
192 if (Index >= Store->Header->NumEntries) return 1;
193 size_t Length2 = Store->Header->Entries[Index].Length;
194 size_t Link = Store->Header->Entries[Index].Link;
195 size_t NodeSize = Store->Header->NodeSize;
196 void *Node = Store->Data + Link * NodeSize;
197 while (Length2 > NodeSize) {
198 if (Length < NodeSize - 4) {
199 return memcmp(Other, Node, Length) ?: -1;
200 }
201 int Cmp = memcmp(Other, Node, NodeSize - 4);
202 if (Cmp) return Cmp;
203 Other += NodeSize - 4;
204 Length2 -= NodeSize - 4;
205 Length -= NodeSize - 4;
206 Node = Store->Data + NodeSize * NODE_LINK(Node);
207 }
208 if (Length < Length2) {
209 return memcmp(Other, Node, Length) ?: -1;
210 } else if (Length > Length2) {
211 return memcmp(Other, Node, Length2) ?: 1;
212 } else {
213 return memcmp(Other, Node, Length);
214 }
215 }
216
string_store_compare2(string_store_t * Store,size_t Index1,size_t Index2)217 int string_store_compare2(string_store_t *Store, size_t Index1, size_t Index2) {
218 if (Index1 >= Store->Header->NumEntries) return -1;
219 if (Index2 >= Store->Header->NumEntries) return 1;
220 size_t Length1 = Store->Header->Entries[Index1].Length;
221 size_t Length2 = Store->Header->Entries[Index2].Length;
222 size_t Link1 = Store->Header->Entries[Index1].Link;
223 size_t Link2 = Store->Header->Entries[Index2].Link;
224 size_t NodeSize = Store->Header->NodeSize;
225 void *Node1 = Store->Data + Link1 * NodeSize;
226 void *Node2 = Store->Data + Link2 * NodeSize;
227 while (Length1 > NodeSize && Length2 > NodeSize) {
228 int Cmp = memcmp(Node1, Node2, NodeSize - 4);
229 if (Cmp) return Cmp;
230 Length1 -= NodeSize - 4;
231 Length2 -= NodeSize - 4;
232 Node1 = Store->Data + NodeSize * NODE_LINK(Node1);
233 Node2 = Store->Data + NodeSize * NODE_LINK(Node2);
234 }
235 if (Length1 > NodeSize) {
236 if (Length2 > NodeSize - 4) {
237 int Cmp = memcmp(Node1, Node2, NodeSize - 4);
238 if (Cmp) return Cmp;
239 Length1 -= NodeSize - 4;
240 Length2 -= NodeSize - 4;
241 Node1 = Store->Data + NodeSize * NODE_LINK(Node1);
242 return memcmp(Node1, Node2 + NodeSize - 4, Length2) ?: 1;
243 } else {
244 return memcmp(Node1, Node2, Length2) ?: 1;
245 }
246 } else if (Length2 > NodeSize) {
247 if (Length1 > NodeSize - 4) {
248 int Cmp = memcmp(Node1, Node2, NodeSize - 4);
249 if (Cmp) return Cmp;
250 Length1 -= NodeSize - 4;
251 Length2 -= NodeSize - 4;
252 Node2 = Store->Data + NodeSize * NODE_LINK(Node2);
253 return memcmp(Node1 + NodeSize - 4, Node2, Length1) ?: -1;
254 } else {
255 return memcmp(Node1, Node2, Length1) ?: -1;
256 }
257 } else if (Length1 > Length2) {
258 return memcmp(Node1, Node2, Length2) ?: 1;
259 } else if (Length2 > Length1) {
260 return memcmp(Node1, Node2, Length1) ?: 1;
261 } else {
262 return memcmp(Node1, Node2, Length1);
263 }
264 }
265
string_store_set(string_store_t * Store,size_t Index,const void * Buffer,size_t Length)266 void string_store_set(string_store_t *Store, size_t Index, const void *Buffer, size_t Length) {
267 if (Index >= Store->Header->NumEntries) {
268 size_t NumEntries = (Index + 1) - Store->Header->NumEntries;
269 NumEntries += 512 - 1;
270 NumEntries /= 512;
271 NumEntries *= 512;
272 size_t HeaderSize = Store->HeaderSize + NumEntries * sizeof(entry_t);
273 ftruncate(Store->HeaderFd, HeaderSize);
274 #ifdef Linux
275 Store->Header = mremap(Store->Header, Store->HeaderSize, HeaderSize, MREMAP_MAYMOVE);
276 #else
277 munmap(Store->Header, Store->HeaderSize);
278 Store->Header = mmap(NULL, HeaderSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->HeaderFd, 0);
279 #endif
280 entry_t *Entries = Store->Header->Entries;
281 for (int I = Store->Header->NumEntries; I < Store->Header->NumEntries + NumEntries; ++I) {
282 Entries[I].Link = INVALID_INDEX;
283 Entries[I].Length = 0;
284 }
285 Store->Header->NumEntries += NumEntries;
286 Store->HeaderSize = HeaderSize;
287 }
288 size_t OldLength = Store->Header->Entries[Index].Length;
289 Store->Header->Entries[Index].Length = Length;
290 size_t NodeSize = Store->Header->NodeSize;
291 size_t OldNumBlocks = (OldLength > NodeSize) ? 1 + (OldLength - 5) / (NodeSize - 4) : (OldLength != 0);
292 size_t NewNumBlocks = (Length > NodeSize) ? 1 + (Length - 5) / (NodeSize - 4) : (Length != 0);
293 if (OldNumBlocks > NewNumBlocks) {
294 size_t FreeStart = Store->Header->Entries[Index].Link;
295 if (NewNumBlocks) {
296 void *Node = Store->Data + FreeStart * NodeSize;
297 while (Length > NodeSize) {
298 memcpy(Node, Buffer, NodeSize - 4);
299 Buffer += NodeSize - 4;
300 Length -= NodeSize - 4;
301 Node = Store->Data + NodeSize * NODE_LINK(Node);
302 }
303 FreeStart = NODE_LINK(Node);
304 memcpy(Node, Buffer, Length);
305 }
306 void *FreeEnd = Store->Data + FreeStart * NodeSize;
307 size_t NumFree = OldNumBlocks - NewNumBlocks;
308 Store->Header->NumFreeNodes += NumFree;
309 for (int I = NumFree; --I > 0;) FreeEnd = Store->Data + NodeSize * NODE_LINK(FreeEnd);
310 NODE_LINK(FreeEnd) = Store->Header->FreeNode;
311 Store->Header->FreeNode = FreeStart;
312 } else if (OldNumBlocks < NewNumBlocks) {
313 size_t NumRequired = NewNumBlocks - OldNumBlocks;
314 size_t NumFree = Store->Header->NumFreeNodes;
315 if (NumRequired > NumFree) {
316 int NumNodes = NumRequired - NumFree;
317 NumNodes += Store->Header->ChunkSize - 1;
318 NumNodes /= Store->Header->ChunkSize;
319 NumNodes *= Store->Header->ChunkSize;
320 size_t DataSize = (Store->Header->NumNodes + NumNodes) * NodeSize;
321 //msync(Store->Data, Store->Header->NumNodes * NodeSize, MS_SYNC);
322 ftruncate(Store->DataFd, DataSize);
323 #ifdef Linux
324 Store->Data = mremap(Store->Data, Store->Header->NumNodes * NodeSize, DataSize, MREMAP_MAYMOVE);
325 #else
326 munmap(Store->Data, Store->Header->NumNodes * NodeSize);
327 Store->Data = mmap(NULL, DataSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->DataFd, 0);
328 #endif
329 size_t FreeEnd;
330 if (NumFree > 0) {
331 FreeEnd = Store->Header->FreeNode;
332 for (int I = NumFree; --I > 0;) FreeEnd = NODE_LINK(Store->Data + FreeEnd * NodeSize);
333 FreeEnd = NODE_LINK(Store->Data + FreeEnd * NodeSize) = Store->Header->NumNodes;
334 } else {
335 FreeEnd = Store->Header->FreeNode = Store->Header->NumNodes;
336 }
337 Store->Header->NumNodes += NumNodes;
338 Store->Header->NumFreeNodes += NumNodes - NumRequired;
339 while (--NumNodes > 0) FreeEnd = NODE_LINK(Store->Data + FreeEnd * NodeSize) = FreeEnd + 1;
340 } else {
341 Store->Header->NumFreeNodes -= NumRequired;
342 }
343 if (OldNumBlocks) {
344 void *Node = Store->Data + Store->Header->Entries[Index].Link * NodeSize;
345 for (int I = OldNumBlocks; --I > 0;) {
346 memcpy(Node, Buffer, NodeSize - 4);
347 Buffer += NodeSize - 4;
348 Length -= NodeSize - 4;
349 Node = Store->Data + NodeSize * NODE_LINK(Node);
350 }
351 memcpy(Node, Buffer, NodeSize - 4);
352 Buffer += NodeSize - 4;
353 Length -= NodeSize - 4;
354 NODE_LINK(Node) = Store->Header->FreeNode;
355 } else {
356 Store->Header->Entries[Index].Link = Store->Header->FreeNode;
357 }
358 void *Node = Store->Data + Store->Header->FreeNode * NodeSize;
359 while (Length > NodeSize) {
360 memcpy(Node, Buffer, NodeSize - 4);
361 Buffer += NodeSize - 4;
362 Length -= NodeSize - 4;
363 Node = Store->Data + NodeSize * NODE_LINK(Node);
364 }
365 Store->Header->FreeNode = NODE_LINK(Node);
366 memcpy(Node, Buffer, Length);
367 } else {
368 void *Node = Store->Data + Store->Header->Entries[Index].Link * NodeSize;
369 while (Length > NodeSize) {
370 memcpy(Node, Buffer, NodeSize - 4);
371 Buffer += NodeSize - 4;
372 Length -= NodeSize - 4;
373 Node = Store->Data + NodeSize * NODE_LINK(Node);
374 }
375 memcpy(Node, Buffer, Length);
376 }
377 //msync(Store->Header, Store->HeaderSize, MS_ASYNC);
378 //msync(Store->Data, Store->Header->NumNodes * NodeSize, MS_ASYNC);
379 }
380
string_store_alloc(string_store_t * Store)381 size_t string_store_alloc(string_store_t *Store) {
382 size_t FreeEntry = Store->Header->FreeEntry;
383 size_t Index = Store->Header->Entries[FreeEntry].Link;
384 if (Index == INVALID_INDEX) {
385 Index = FreeEntry + 1;
386 if (Index >= Store->Header->NumEntries) {
387 size_t NumEntries = (Index + 1) - Store->Header->NumEntries;
388 NumEntries += 512 - 1;
389 NumEntries /= 512;
390 NumEntries *= 512;
391 size_t HeaderSize = Store->HeaderSize + NumEntries * sizeof(entry_t);
392 ftruncate(Store->HeaderFd, HeaderSize);
393 #ifdef Linux
394 Store->Header = mremap(Store->Header, Store->HeaderSize, HeaderSize, MREMAP_MAYMOVE);
395 #else
396 munmap(Store->Header, Store->HeaderSize);
397 Store->Header = mmap(NULL, HeaderSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->HeaderFd, 0);
398 #endif
399 entry_t *Entries = Store->Header->Entries;
400 for (int I = Store->Header->NumEntries; I < Store->Header->NumEntries + NumEntries; ++I) {
401 Entries[I].Link = INVALID_INDEX;
402 Entries[I].Length = 0;
403 }
404 Store->Header->NumEntries += NumEntries;
405 Store->HeaderSize = HeaderSize;
406 }
407 }
408 Store->Header->FreeEntry = Index;
409 return FreeEntry;
410 }
411
string_store_free(string_store_t * Store,size_t Index)412 void string_store_free(string_store_t *Store, size_t Index) {
413 size_t OldLength = Store->Header->Entries[Index].Length;
414 Store->Header->Entries[Index].Length = 0;
415 size_t NodeSize = Store->Header->NodeSize;
416 size_t OldNumBlocks = (OldLength > NodeSize) ? 1 + (OldLength - 5) / (NodeSize - 4) : (OldLength != 0);
417 if (OldNumBlocks > 0) {
418 size_t FreeStart = Store->Header->Entries[Index].Link;
419 void *FreeEnd = Store->Data + FreeStart * NodeSize;
420 Store->Header->NumFreeNodes += OldNumBlocks;
421 for (int I = OldNumBlocks; --I > 0;) FreeEnd = Store->Data + NodeSize * NODE_LINK(FreeEnd);
422 NODE_LINK(FreeEnd) = Store->Header->FreeNode;
423 Store->Header->FreeNode = FreeStart;
424 }
425 Store->Header->Entries[Index].Link = Store->Header->FreeEntry;
426 Store->Header->FreeEntry = Index;
427 }
428
string_store_writer_open(string_store_writer_t * Writer,string_store_t * Store,size_t Index)429 void string_store_writer_open(string_store_writer_t *Writer, string_store_t *Store, size_t Index) {
430 if (Index >= Store->Header->NumEntries) {
431 size_t NumEntries = (Index + 1) - Store->Header->NumEntries;
432 NumEntries += 512 - 1;
433 NumEntries /= 512;
434 NumEntries *= 512;
435 size_t HeaderSize = Store->HeaderSize + NumEntries * sizeof(entry_t);
436 ftruncate(Store->HeaderFd, HeaderSize);
437 #ifdef Linux
438 Store->Header = mremap(Store->Header, Store->HeaderSize, HeaderSize, MREMAP_MAYMOVE);
439 #else
440 munmap(Store->Header, Store->HeaderSize);
441 Store->Header = mmap(NULL, HeaderSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->HeaderFd, 0);
442 #endif
443 entry_t *Entries = Store->Header->Entries;
444 for (int I = Store->Header->NumEntries; I < Store->Header->NumEntries + NumEntries; ++I) {
445 Entries[I].Link = INVALID_INDEX;
446 Entries[I].Length = 0;
447 }
448 Store->Header->NumEntries += NumEntries;
449 Store->HeaderSize = HeaderSize;
450 }
451 size_t OldLength = Store->Header->Entries[Index].Length;
452 size_t NodeSize = Store->Header->NodeSize;
453 size_t OldNumBlocks = (OldLength > NodeSize) ? 1 + (OldLength - 5) / (NodeSize - 4) : (OldLength != 0);
454 if (OldNumBlocks > 0) {
455 size_t FreeStart = Store->Header->Entries[Index].Link;
456 void *FreeEnd = Store->Data + FreeStart * NodeSize;
457 Store->Header->NumFreeNodes += OldNumBlocks;
458 for (int I = OldNumBlocks; --I > 0;) FreeEnd = Store->Data + NodeSize * NODE_LINK(FreeEnd);
459 NODE_LINK(FreeEnd) = Store->Header->FreeNode;
460 Store->Header->FreeNode = FreeStart;
461 }
462 Writer->Store = Store;
463 Writer->Node = SIZE_MAX;
464 Writer->Index = Index;
465 Store->Header->Entries[Index].Length = 0;
466 Store->Header->Entries[Index].Link = INVALID_INDEX;
467 }
468
string_store_node_alloc(string_store_t * Store,size_t NodeSize)469 static inline size_t string_store_node_alloc(string_store_t *Store, size_t NodeSize) {
470 if (!Store->Header->NumFreeNodes) {
471 size_t NumNodes = Store->Header->ChunkSize;
472 size_t DataSize = (Store->Header->NumNodes + NumNodes) * NodeSize;
473 //msync(Store->Data, Store->Header->NumNodes * NodeSize, MS_SYNC);
474 ftruncate(Store->DataFd, DataSize);
475 #ifdef Linux
476 Store->Data = mremap(Store->Data, Store->Header->NumNodes * NodeSize, DataSize, MREMAP_MAYMOVE);
477 #else
478 munmap(Store->Data, Store->Header->NumNodes * NodeSize);
479 Store->Data = mmap(NULL, DataSize, PROT_READ | PROT_WRITE, MAP_SHARED, Store->DataFd, 0);
480 #endif
481 size_t Index = Store->Header->NumNodes;
482 size_t FreeEnd = Store->Header->FreeNode = Store->Header->NumNodes + 1;
483 Store->Header->NumNodes += NumNodes;
484 Store->Header->NumFreeNodes += --NumNodes ;
485 while (--NumNodes > 0) FreeEnd = NODE_LINK(Store->Data + FreeEnd * NodeSize) = FreeEnd + 1;
486 return Index;
487 } else {
488 --Store->Header->NumFreeNodes;
489 size_t Index = Store->Header->FreeNode;
490 Store->Header->FreeNode = NODE_LINK(Store->Data + NodeSize * Index);
491 return Index;
492 }
493 }
494
string_store_writer_write(string_store_writer_t * Writer,const void * Buffer,size_t Length)495 size_t string_store_writer_write(string_store_writer_t *Writer, const void *Buffer, size_t Length) {
496 if (Length == 0) return Length;
497 string_store_t *Store = Writer->Store;
498 Store->Header->Entries[Writer->Index].Length += Length;
499 size_t NodeSize = Store->Header->NodeSize;
500 size_t NodeIndex = Writer->Node;
501 size_t Remain = Length, Offset, Space;
502 if (NodeIndex == SIZE_MAX) {
503 NodeIndex = string_store_node_alloc(Store, NodeSize);
504 Store->Header->Entries[Writer->Index].Link = NodeIndex;
505 Space = NodeSize;
506 Offset = 0;
507 } else {
508 Space = Writer->Remain;
509 Offset = NodeSize - Space;
510 }
511 void *Node = Store->Data + NodeSize * NodeIndex;
512 if (Remain > Space) {
513 if (Space <= 4) {
514 uint32_t Save = NODE_LINK(Node);
515 size_t NewIndex = string_store_node_alloc(Store, NodeSize);
516 Node = Store->Data + NodeSize * NodeIndex;
517 NODE_LINK(Node) = NewIndex;
518 NodeIndex = NewIndex;
519 Node = Store->Data + NodeSize * NodeIndex;
520 *(uint32_t *)Node = Save;
521 Offset = 4 - Space;
522 Space = NodeSize - Offset;
523 }
524 while (Remain > Space) {
525 memcpy(Node + Offset, Buffer, Space - 4);
526 Buffer += Space - 4;
527 Remain -= Space - 4;
528 size_t NewIndex = string_store_node_alloc(Store, NodeSize);
529 Node = Store->Data + NodeSize * NodeIndex;
530 NODE_LINK(Node) = NewIndex;
531 NodeIndex = NewIndex;
532 Node = Store->Data + NodeSize * NodeIndex;
533 Offset = 0;
534 Space = NodeSize;
535 }
536 }
537 memcpy(Node + Offset, Buffer, Remain);
538 Writer->Node = NodeIndex;
539 Writer->Remain = Space - Remain;
540 return Length;
541 }
542
string_store_reader_open(string_store_reader_t * Reader,string_store_t * Store,size_t Index)543 void string_store_reader_open(string_store_reader_t *Reader, string_store_t *Store, size_t Index) {
544 Reader->Store = Store;
545 Reader->Offset = 0;
546 if (Index >= Store->Header->NumEntries) {
547 Reader->Node = INVALID_INDEX;
548 Reader->Remain = 0;
549 } else {
550 Reader->Node = Store->Header->Entries[Index].Link;
551 Reader->Remain = Store->Header->Entries[Index].Length;
552 }
553 }
554
string_store_reader_read(string_store_reader_t * Reader,void * Buffer,size_t Length)555 size_t string_store_reader_read(string_store_reader_t *Reader, void *Buffer, size_t Length) {
556 string_store_t *Store = Reader->Store;
557 size_t NodeSize = Store->Header->NodeSize;
558 size_t NodeIndex = Reader->Node;
559 if (NodeIndex == SIZE_MAX) return 0;
560 size_t Offset = Reader->Offset;
561 size_t Remain = Reader->Remain;
562 size_t Copied = 0;
563 for (;;) {
564 void *Node = Store->Data + NodeSize * NodeIndex;
565 if (Offset + Remain <= NodeSize) {
566 // Last node
567 if (Length <= Remain) {
568 memcpy(Buffer, Node + Offset, Length);
569 Reader->Node = NodeIndex;
570 Reader->Offset = Offset + Length;
571 Reader->Remain = Remain - Length;
572 return Copied + Length;
573 } else {
574 memcpy(Buffer, Node + Offset, Remain);
575 Reader->Node = SIZE_MAX;
576 return Copied + Remain;
577 }
578 } else {
579 size_t Available = NodeSize - Offset - 4;
580 if (Length <= Available) {
581 memcpy(Buffer, Node + Offset, Length);
582 Reader->Node = NodeIndex;
583 Reader->Offset = Offset + Length;
584 Reader->Remain = Remain - Length;
585 return Copied + Length;
586 } else {
587 memcpy(Buffer, Node + Offset, Available);
588 NodeIndex = NODE_LINK(Node);
589 Offset = 0;
590 Remain -= Available;
591 Copied += Available;
592 Buffer += Available;
593 Length -= Available;
594 }
595 }
596 }
597 }
598