Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

wvgdbmlist.h

Go to the documentation of this file.
00001 /* -*- Mode: C++ -*- 00002 * Worldvisions Weaver Software: 00003 * Copyright (C) 1997-2003 Net Integration Technologies, Inc. 00004 * 00005 * A linked list container backed by a gdbm database. 00006 */ 00007 #ifndef __WVGDBMLIST_H 00008 #define __WVGDBMLIST_H 00009 00010 #include "wvgdbmhash.h" 00011 00012 /** 00013 * A class based on WvGdbmHash that lets you store WvBufs and auto-assign 00014 * them Index values as keys. This is convenient for implementing various 00015 * data structures in the on-disk hash, since you can use Index values 00016 * wherever an in-memory structure would use a pointer. 00017 * 00018 * NOTE: Index values <= 0 have a special meaning, and will never be 00019 * assigned automatically. WvGdbmAlloc uses Index # -1 itself as the 00020 * beginning of the FREELIST. The others you can use as you wish. 00021 */ 00022 class WvGdbmAlloc 00023 { 00024 public: 00025 enum { FREELIST = -1 }; 00026 00027 typedef int32_t Index; 00028 typedef WvGdbmHash<Index, WvBuf> LinkHash; 00029 00030 LinkHash hash; 00031 00032 WvGdbmAlloc(WvStringParm filename) : hash(filename) 00033 { } 00034 00035 private: 00036 Index next(Index i) 00037 { 00038 WvBuf *buf = &hash[i]; 00039 Index next = wv_deserialize<Index>(*buf); 00040 return next; 00041 } 00042 00043 void link(Index prev, Index next) 00044 { 00045 unsigned char junk[16]; 00046 WvInPlaceBuf buf(junk, 0, 16); 00047 wv_serialize(buf, next); 00048 hash.add(prev, buf, true); 00049 } 00050 00051 public: 00052 void zap() 00053 { 00054 hash.zap(); 00055 link(FREELIST, 1); 00056 } 00057 00058 Index alloc() 00059 { 00060 Index i = next(FREELIST); 00061 if (!hash.exists(i)) 00062 { 00063 // this is the highest allocated value. Preallocate the 00064 // next one so we don't lose our place. 00065 assert(!hash.exists(i+1)); 00066 link(FREELIST, i+1); 00067 } 00068 else 00069 link(FREELIST, next(i)); 00070 return i; 00071 } 00072 00073 void unalloc(Index i) 00074 { 00075 link(i, next(FREELIST)); 00076 link(FREELIST, i); 00077 } 00078 }; 00079 00080 00081 /** 00082 * A class similar to WvList, but storing its values on disk in a WvGdbmHash. 00083 * 00084 * FIXME: I have no idea if this is fast, slow, stupid, or ingenious. I 00085 * suspect it's probably quite inefficient - doing it entirely without gdbm 00086 * and writing our own space allocator would probably make more sense. 00087 * 00088 * FIXME: we should use a common non-templated base class rather than 00089 * implementing everything inline. 00090 * 00091 * FIXME: if HEAD and TAIL weren't hardcoded, we could put more than one 00092 * list in the same WvGdbmHash. This would probably be pretty useful. 00093 */ 00094 template <typename T> 00095 class WvGdbmList 00096 { 00097 typedef WvGdbmAlloc::Index Index; 00098 WvGdbmAlloc alloc; 00099 WvGdbmAlloc::LinkHash &hash; 00100 00101 public: 00102 class Iter; 00103 friend class WvGdbmList::Iter; 00104 00105 enum { HEAD = 0, TAIL = -1000 }; 00106 00107 struct Link 00108 { 00109 Index next; 00110 WvBuf *buf; 00111 private: 00112 T *_data; 00113 00114 public: 00115 Link() 00116 { _data = NULL; buf = NULL; } 00117 ~Link() 00118 { zap(); } 00119 00120 T *data() 00121 { 00122 if (buf && !_data) 00123 { 00124 if (buf->used()) 00125 _data = wv_deserialize<T *>(*buf); 00126 else 00127 _data = NULL; 00128 buf = NULL; 00129 } 00130 return _data; 00131 } 00132 00133 void zap() 00134 { if (_data) delete _data; _data = NULL; } 00135 } saved; 00136 00137 Index retrieve(Index i) 00138 { 00139 saved.zap(); 00140 saved.buf = &hash[i]; 00141 saved.next = wv_deserialize<Index>(*saved.buf); 00142 //printf(" ret %d/%d (%d left)\n", i, saved.next, saved.buf->used()); 00143 return saved.next; 00144 } 00145 00146 void save(Index i, Index next, const T *data) 00147 { 00148 WvDynBuf buf; 00149 wv_serialize(buf, next); 00150 if (data) 00151 wv_serialize(buf, *data); 00152 //printf("save %d/%d/%p (%d bytes)\n", i, next, data, buf.used()); 00153 hash.add(i, buf, true); 00154 } 00155 00156 public: 00157 WvGdbmList(WvStringParm filename) : alloc(filename), hash(alloc.hash) 00158 { 00159 init(); 00160 } 00161 00162 void init() 00163 { 00164 if (!hash.exists(HEAD) || !hash.exists(TAIL)) 00165 { 00166 // corrupted or newly created! 00167 zap(); 00168 } 00169 } 00170 00171 void zap() 00172 { 00173 alloc.zap(); 00174 save(HEAD, HEAD, NULL); 00175 save(TAIL, HEAD, NULL); 00176 assert(!hash.exists(1)); 00177 } 00178 00179 size_t count() 00180 { 00181 int count = 0; 00182 for (int next = retrieve(HEAD); next != HEAD; next = retrieve(next)) 00183 count++; 00184 return count; 00185 } 00186 00187 bool isempty() 00188 { 00189 return retrieve(HEAD) == HEAD; 00190 } 00191 00192 T *first() 00193 { 00194 // HEAD is not an actual element - it just points to the first one 00195 retrieve(retrieve(HEAD)); 00196 return saved.data(); 00197 } 00198 00199 T *last() 00200 { 00201 // TAIL is not an actual element - it just points to the last one 00202 // (and nobody links to TAIL) 00203 retrieve(retrieve(TAIL)); 00204 return saved.data(); 00205 } 00206 00207 void add_after(Index after, const T *data, bool auto_free = false, 00208 void *id = NULL) 00209 { 00210 Index i = alloc.alloc(); 00211 retrieve(after); 00212 Index next = retrieve(after); 00213 save(i, next, data); 00214 save(after, i, saved.data()); 00215 00216 if (next == HEAD) 00217 save(TAIL, i, NULL); 00218 if (auto_free) 00219 delete data; // already done with it! 00220 } 00221 00222 void append(const T &data, bool auto_free = false, void *id = NULL) 00223 { add_after(retrieve(TAIL), &data, auto_free, id); } 00224 void prepend(const T &data, bool auto_free = false, void *id = NULL) 00225 { add_after(HEAD, &data, auto_free, id); } 00226 00227 void append(const T *data, bool auto_free = false, void *id = NULL) 00228 { add_after(retrieve(TAIL), data, auto_free, id); } 00229 void prepend(const T *data, bool auto_free = false, void *id = NULL) 00230 { add_after(HEAD, data, auto_free, id); } 00231 00232 private: 00233 // this works in a WvList, but it's kind of hard in a GdbmList. So we 00234 // won't implement it. 00235 void unlink(T *data); 00236 00237 public: 00238 void unlink_first() 00239 { unlink_after(HEAD); } 00240 00241 void unlink_after(Index prev) 00242 { 00243 Index cur = retrieve(prev); 00244 Index next = retrieve(cur); 00245 if (next == HEAD) 00246 save(TAIL, prev, NULL); 00247 retrieve(prev); 00248 save(prev, next, saved.data()); 00249 // hash.remove(cur); // unalloc replaces this 00250 alloc.unalloc(cur); 00251 } 00252 00253 class Iter 00254 { 00255 typedef WvGdbmList::Index Index; 00256 public: 00257 WvGdbmList &list; 00258 Index prev, xcur, xnext; 00259 00260 Iter(WvGdbmList &_list) : list(_list) 00261 { } 00262 00263 void rewind() 00264 { prev = HEAD; xcur = HEAD; xnext = list.retrieve(xcur); } 00265 bool cur() 00266 { return xcur != HEAD; } 00267 bool next() 00268 { prev = xcur; xcur = xnext; xnext = list.retrieve(xcur); 00269 return cur(); } 00270 00271 /** 00272 * Unlinks the current element from the list like in WvList. 00273 * You usually want xunlink() instead. 00274 */ 00275 void unlink() 00276 { list.unlink_after(prev); xcur = list.retrieve(prev); 00277 xnext = list.retrieve(xcur); } 00278 00279 /** 00280 * Unlinks the current element from the list like in WvList. 00281 * The iterator becomes invalid until next(), but next() does 00282 * exactly what it would have done if you hadn't done xunlink(). 00283 * See WvLink::Iter::xunlink() for the reasoning here. 00284 */ 00285 void xunlink() 00286 { list.unlink_after(prev); xcur = prev; } 00287 00288 T *ptr() const 00289 { return list.saved.data(); } 00290 WvIterStuff(T); 00291 }; 00292 }; 00293 00294 00295 // DeclareWvList-compatible macro for people who want to hackily see what 00296 // happens if they replace their WvList with a WvGdbmList. 00297 #define DeclareWvGdbmList(__type__) \ 00298 class __type__##List : public WvGdbmList<__type__> \ 00299 { \ 00300 public: \ 00301 __type__##List() : WvGdbmList<__type__>((srand(time(NULL)), \ 00302 random())) {} \ 00303 } 00304 00305 00306 #endif // __WVGDBMLIST_H

Generated on Tue Oct 5 01:09:20 2004 for WvStreams by doxygen 1.3.7