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