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 * 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 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 * 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 * 95 logfsmapfindentry(Map *m, void *key) 96 { 97 void *rv; 98 find(m, key, 0, &rv); 99 return rv; 100 } 101 102 char * 103 logfsmapnewentry(Map *m, void *key, void **entryp) 104 { 105 return find(m, key, 1, entryp); 106 } 107 108 int 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 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