00001
00002
00003
00004
00005
00006
00007 #ifndef __WVGDBMLIST_H
00008 #define __WVGDBMLIST_H
00009
00010 #include "wvgdbmhash.h"
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
00064
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
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
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
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
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
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
00195 retrieve(retrieve(HEAD));
00196 return saved.data();
00197 }
00198
00199 T *last()
00200 {
00201
00202
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;
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
00234
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
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
00273
00274
00275 void unlink()
00276 { list.unlink_after(prev); xcur = list.retrieve(prev);
00277 xnext = list.retrieve(xcur); }
00278
00279
00280
00281
00282
00283
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
00296
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