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 Sat Feb 21 21:05:28 2004 for WvStreams by doxygen 1.3.5