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