Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members | Related Pages

wvondisklist.h

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 on disk database.
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             // this is the highest allocated value.  Preallocate the
00065             // next one so we don't lose our place.
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         //printf(" ret %d/%d (%d left)\n", i, saved.next, saved.buf->used());
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         //printf("save %d/%d/%p (%d bytes)\n", i, next, data, buf.used());
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             // corrupted or newly created!
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         // HEAD is not an actual element - it just points to the first one
00198         retrieve(retrieve(HEAD));
00199         return saved.data();
00200     }
00201     
00202     T *last()
00203     {
00204         // TAIL is not an actual element - it just points to the last one
00205         // (and nobody links to TAIL)
00206         retrieve(retrieve(TAIL)); 
00207         return saved.data();
00208     }
00209     
00210     void add_after(Index after, const T *data, bool auto_free = 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 (auto_free)
00222             delete data; // already done with it!
00223     }
00224     
00225     void append(const T &data, bool auto_free = false, void *id = NULL)
00226         { add_after(retrieve(TAIL), &data, auto_free, id); }
00227     void prepend(const T &data, bool auto_free = false, void *id = NULL)
00228         { add_after(HEAD, &data, auto_free, id); }
00229 
00230     void append(const T *data, bool auto_free = false, void *id = NULL)
00231         { add_after(retrieve(TAIL), data, auto_free, id); }
00232     void prepend(const T *data, bool auto_free = false, void *id = NULL)
00233         { add_after(HEAD, data, auto_free, id); }
00234 
00235 private:
00236     // this works in a WvList, but it's kind of hard in a OnDiskList.  So we
00237     // won't implement it.
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         // hash.remove(cur); // unalloc replaces this
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 // DeclareWvList-compatible macro for people who want to hackily see what
00299 // happens if they replace their WvList with a WvOnDiskList.
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

Generated on Tue Jul 12 02:59:27 2005 for WvStreams by  doxygen 1.4.0