00001
00002
00003
00004
00005
00006
00007 #ifndef __WVONDISKLIST_H
00008 #define __WVONDISKLIST_H
00009
00010 #include "wvondiskhash.h"
00011
00022 template <class Backend>
00023 class WvOnDiskAlloc
00024 {
00025 public:
00026 enum { FREELIST = -1 };
00027
00028 typedef int32_t Index;
00029 typedef WvOnDiskHash<Index, WvBuf, Backend> LinkHash;
00030
00031 LinkHash hash;
00032
00033 WvOnDiskAlloc(WvStringParm filename) : hash(filename)
00034 { }
00035
00036 private:
00037 Index next(Index i)
00038 {
00039 WvBuf *buf = &hash[i];
00040 Index next = wv_deserialize<Index>(*buf);
00041 return next;
00042 }
00043
00044 void link(Index prev, Index next)
00045 {
00046 unsigned char junk[16];
00047 WvInPlaceBuf buf(junk, 0, 16);
00048 wv_serialize(buf, next);
00049 hash.add(prev, buf, true);
00050 }
00051
00052 public:
00053 void zap()
00054 {
00055 hash.zap();
00056 link(FREELIST, 1);
00057 }
00058
00059 Index alloc()
00060 {
00061 Index i = next(FREELIST);
00062 if (!hash.exists(i))
00063 {
00064
00065
00066 assert(!hash.exists(i+1));
00067 link(FREELIST, i+1);
00068 }
00069 else
00070 link(FREELIST, next(i));
00071 return i;
00072 }
00073
00074 void unalloc(Index i)
00075 {
00076 link(i, next(FREELIST));
00077 link(FREELIST, i);
00078 }
00079 };
00080
00081
00096 template <typename T, typename Backend = DefaultHash>
00097 class WvOnDiskList
00098 {
00099 typedef WvOnDiskAlloc<Backend> MyAlloc;
00100 typedef typename MyAlloc::Index Index;
00101 MyAlloc alloc;
00102 typename MyAlloc::LinkHash &hash;
00103
00104 public:
00105 class Iter;
00106 friend class WvOnDiskList::Iter;
00107
00108 enum { HEAD = 0, TAIL = -1000 };
00109
00110 struct Link
00111 {
00112 Index next;
00113 WvBuf *buf;
00114 private:
00115 T *_data;
00116
00117 public:
00118 Link()
00119 { _data = NULL; buf = NULL; }
00120 ~Link()
00121 { zap(); }
00122
00123 T *data()
00124 {
00125 if (buf && !_data)
00126 {
00127 if (buf->used())
00128 _data = wv_deserialize<T *>(*buf);
00129 else
00130 _data = NULL;
00131 buf = NULL;
00132 }
00133 return _data;
00134 }
00135
00136 void zap()
00137 { if (_data) delete _data; _data = NULL; }
00138 } saved;
00139
00140 Index retrieve(Index i)
00141 {
00142 saved.zap();
00143 saved.buf = &hash[i];
00144 saved.next = wv_deserialize<Index>(*saved.buf);
00145
00146 return saved.next;
00147 }
00148
00149 void save(Index i, Index next, const T *data)
00150 {
00151 WvDynBuf buf;
00152 wv_serialize(buf, next);
00153 if (data)
00154 wv_serialize(buf, *data);
00155
00156 hash.add(i, buf, true);
00157 }
00158
00159 public:
00160 WvOnDiskList(WvStringParm filename) : alloc(filename), hash(alloc.hash)
00161 {
00162 init();
00163 }
00164
00165 void init()
00166 {
00167 if (!hash.exists(HEAD) || !hash.exists(TAIL))
00168 {
00169
00170 zap();
00171 }
00172 }
00173
00174 void zap()
00175 {
00176 alloc.zap();
00177 save(HEAD, HEAD, NULL);
00178 save(TAIL, HEAD, NULL);
00179 assert(!hash.exists(1));
00180 }
00181
00182 size_t count()
00183 {
00184 int count = 0;
00185 for (int next = retrieve(HEAD); next != HEAD; next = retrieve(next))
00186 count++;
00187 return count;
00188 }
00189
00190 bool isempty()
00191 {
00192 return retrieve(HEAD) == HEAD;
00193 }
00194
00195 T *first()
00196 {
00197
00198 retrieve(retrieve(HEAD));
00199 return saved.data();
00200 }
00201
00202 T *last()
00203 {
00204
00205
00206 retrieve(retrieve(TAIL));
00207 return saved.data();
00208 }
00209
00210 void add_after(Index after, const T *data, bool autofree = false,
00211 void *id = NULL)
00212 {
00213 Index i = alloc.alloc();
00214 retrieve(after);
00215 Index next = retrieve(after);
00216 save(i, next, data);
00217 save(after, i, saved.data());
00218
00219 if (next == HEAD)
00220 save(TAIL, i, NULL);
00221 if (autofree)
00222 delete data;
00223 }
00224
00225 void append(const T &data, bool autofree = false, void *id = NULL)
00226 { add_after(retrieve(TAIL), &data, autofree, id); }
00227 void prepend(const T &data, bool autofree = false, void *id = NULL)
00228 { add_after(HEAD, &data, autofree, id); }
00229
00230 void append(const T *data, bool autofree = false, void *id = NULL)
00231 { add_after(retrieve(TAIL), data, autofree, id); }
00232 void prepend(const T *data, bool autofree = false, void *id = NULL)
00233 { add_after(HEAD, data, autofree, id); }
00234
00235 private:
00236
00237
00238 void unlink(T *data);
00239
00240 public:
00241 void unlink_first()
00242 { unlink_after(HEAD); }
00243
00244 void unlink_after(Index prev)
00245 {
00246 Index cur = retrieve(prev);
00247 Index next = retrieve(cur);
00248 if (next == HEAD)
00249 save(TAIL, prev, NULL);
00250 retrieve(prev);
00251 save(prev, next, saved.data());
00252
00253 alloc.unalloc(cur);
00254 }
00255
00256 class Iter
00257 {
00258 typedef typename WvOnDiskList::Index Index;
00259 public:
00260 WvOnDiskList &list;
00261 Index prev, xcur, xnext;
00262
00263 Iter(WvOnDiskList &_list) : list(_list)
00264 { }
00265
00266 void rewind()
00267 { prev = HEAD; xcur = HEAD; xnext = list.retrieve(xcur); }
00268 bool cur()
00269 { return xcur != HEAD; }
00270 bool next()
00271 { prev = xcur; xcur = xnext; xnext = list.retrieve(xcur);
00272 return cur(); }
00273
00278 void unlink()
00279 { list.unlink_after(prev); xcur = list.retrieve(prev);
00280 xnext = list.retrieve(xcur); }
00281
00288 void xunlink()
00289 { list.unlink_after(prev); xcur = prev; }
00290
00291 T *ptr() const
00292 { return list.saved.data(); }
00293 WvIterStuff(T);
00294 };
00295 };
00296
00297
00298
00299
00300 #define DeclareWvOnDiskList(__type__) \
00301 class __type__##List : public WvOnDiskList<__type__> \
00302 { \
00303 public: \
00304 __type__##List() : WvOnDiskList<__type__>((srand(time(NULL)), \
00305 random())) {} \
00306 }
00307
00308
00309 #endif // __WVONDISKLIST_H