1 #include "logfsos.h"
2 #include "logfs.h"
3 #include "local.h"
4
5 typedef struct MapNode MapNode;
6
7 struct MapNode {
8 MapNode *next;
9 uchar e[1]; // entry goes here, inline
10 };
11
12 struct Map {
13 int size;
14 int (*hash)(void *key, int size);
15 int (*compare)(void *entry, void *key);
16 int (*allocsize)(void *key);
17 void (*free)(void *entry);
18 MapNode *head[1];
19 };
20
21 char *
logfsmapnew(int size,int (* hash)(void * key,int size),int (* compare)(void * entry,void * key),int (* allocsize)(void * key),void (* free)(void *),Map ** mapp)22 logfsmapnew(int size, int (*hash)(void *key, int size), int (*compare)(void *entry, void *key), int (*allocsize)(void *key), void (*free)(void *), Map **mapp)
23 {
24 Map *p;
25 *mapp = p = logfsrealloc(nil, sizeof(Map) + (size - 1) * sizeof(MapNode *));
26 if(p == nil)
27 return Enomem;
28 p->size = size;
29 p->hash = hash;
30 p->compare = compare;
31 p->allocsize = allocsize;
32 p->free = free;
33 return nil;
34 }
35
36 void
logfsmapfree(FidMap ** mp)37 logfsmapfree(FidMap **mp)
38 {
39 FidMap *m;
40 int i;
41
42 m = *mp;
43 if(m == nil)
44 return;
45
46 for(i = 0; i < m->size; i++) {
47 MapNode *n, *next;
48 n = m->head[i];
49 while(n) {
50 next = n->next;
51 if(m->free)
52 (*m->free)(n->e);
53 logfsfreemem(n);
54 n = next;
55 }
56 }
57 logfsfreemem(m);
58 *mp = nil;
59 }
60
61 static char *
find(FidMap * m,void * key,int create,void ** ep)62 find(FidMap *m, void *key, int create, void **ep)
63 {
64 MapNode *n;
65 int i;
66
67 i = (*m->hash)(key, m->size);
68 n = m->head[i];
69 while(n && !(*m->compare)(n->e, key))
70 n = n->next;
71 if(n) {
72 if(create) {
73 *ep = nil;
74 return nil;
75 }
76 *ep = n->e;
77 return nil;
78 }
79 if(!create) {
80 *ep = nil;
81 return nil;
82 }
83 n = logfsrealloc(nil, (*m->allocsize)(key) + sizeof(MapNode *));
84 if(n == nil) {
85 *ep = nil;
86 return Enomem;
87 }
88 n->next = m->head[i];
89 m->head[i] = n;
90 *ep = n->e;
91 return nil;
92 }
93
94 void *
logfsmapfindentry(Map * m,void * key)95 logfsmapfindentry(Map *m, void *key)
96 {
97 void *rv;
98 find(m, key, 0, &rv);
99 return rv;
100 }
101
102 char *
logfsmapnewentry(Map * m,void * key,void ** entryp)103 logfsmapnewentry(Map *m, void *key, void **entryp)
104 {
105 return find(m, key, 1, entryp);
106 }
107
108 int
logfsmapdeleteentry(Map * m,void * key)109 logfsmapdeleteentry(Map *m, void *key)
110 {
111 MapNode **np, *n;
112 np = &m->head[(*m->hash)(key, m->size)];
113 while((n = *np) && !(*m->compare)(n->e, key))
114 np = &n->next;
115 if(n) {
116 *np = n->next;
117 if(m->free)
118 (*m->free)(n->e);
119 logfsfreemem(n);
120 return 1;
121 }
122 return 0; // not there
123 }
124
125 int
logfsmapwalk(Map * m,int (* func)(void * magic,void *),void * magic)126 logfsmapwalk(Map *m, int (*func)(void *magic, void *), void *magic)
127 {
128 int x;
129 MapNode *n;
130
131 for(x = 0; x < m->size; x++)
132 for(n = m->head[x]; n; n = n->next) {
133 int rv = (*func)(magic, n->e);
134 if(rv <= 0)
135 return rv;
136 }
137 return 1;
138 }
139
140