uniconf/uniconfkey.cc

   1 /*
   2  * Worldvisions Weaver Software:
   3  *   Copyright (C) 2002 Net Integration Technologies, Inc.
   4  *
   5  * A UniConf hierarchical key path abstraction.
   6  */
   7 #include "wvassert.h"
   8 #include "wvstream.h"
   9 #include "uniconfkey.h"
  10 #include "wvhash.h"
  11 #include <climits>
  12 #include <assert.h>
  13 #include <strutils.h>
  14
  15 unsigned WvHash(const UniConfKey &k)
  16 {
  17     int numsegs = k.right - k.left;
  18     unsigned result;
  19     switch (numsegs)
  20     {
  21         case 0:
  22             result = 0;
  23             break;
  24         case 1:
  25             result = WvHash(k.store->segments[k.left]);
  26             break;
  27         default:
  28             result = WvHash(k.store->segments[k.left])
  29                 ^ WvHash(k.store->segments[k.right - 1])
  30                 ^ numsegs;
  31             break;
  32     }
  33     return result;
  34 }
  35
  36 // The initial value of 1 for the ref_count of these guarantees
  37 // that they won't ever be deleted
  38 UniConfKey::Store UniConfKey::EMPTY_store(1, 1);
  39 UniConfKey::Store UniConfKey::ANY_store(1, 1, "*");
  40 UniConfKey::Store UniConfKey::RECURSIVE_ANY_store(1, 1, "...");
  41
  42 UniConfKey UniConfKey::EMPTY(&EMPTY_store, 0, 0);
  43 UniConfKey UniConfKey::ANY(&ANY_store, 0, 1);
  44 UniConfKey UniConfKey::RECURSIVE_ANY(&RECURSIVE_ANY_store, 0, 1);
  45
  46
  47 UniConfKey::Store::Store(int size, int _ref_count,
  48         WvStringParm key) :
  49     segments(size),
  50     ref_count(_ref_count)
  51 {
  52     if (!key)
  53         return;
  54
  55     WvStringList parts;
  56     parts.split(key, "/");
  57
  58     segments.resize(parts.count());
  59     WvStringList::Iter part(parts);
  60     for (part.rewind(); part.next(); )
  61     {
  62         if (!*part)
  63             continue;
  64         segments.append(*part);
  65     }
  66     if (!!key && key[key.len()-1] == '/' && segments.used() > 0)
  67         segments.append(Segment());
  68 }
  69
  70
  71 UniConfKey &UniConfKey::collapse()
  72 {
  73     if ((right - left == 1 && !store->segments[right-1])
  74         || right == left)
  75     {
  76         if (--store->ref_count == 0)
  77             delete store;
  78         store = &EMPTY_store;
  79         left = right = 0;
  80         ++store->ref_count;
  81     }
  82     return *this;
  83 }
  84
  85
  86 void UniConfKey::unique()
  87 {
  88     if (store->ref_count == 1)
  89         return;
  90     store->ref_count--;
  91     Store *old_store = store;
  92     store = new Store(right - left, 1);
  93     for (int i=left; i<right; ++i)
  94         store->segments.append(old_store->segments[i]);
  95     right -= left;
  96     left = 0;
  97 }
  98
  99 UniConfKey::UniConfKey(const UniConfKey &_path, const UniConfKey &_key) :
 100     store(new Store(_path.numsegments() + _key.numsegments() + 1, 1)),
 101     left(0),
 102     right(0)
 103 {
 104     bool hastrailingslash = _key.isempty() || _key.hastrailingslash();
 105     for (int i=_path.left; i<_path.right; ++i)
 106     {
 107         const Segment &segment = _path.store->segments[i];
 108         if (!segment)
 109             continue;
 110         store->segments.append(segment);
 111         ++right;
 112     }
 113     for (int j=_key.left; j<_key.right; ++j)
 114     {
 115         const Segment &segment = _key.store->segments[j];
 116         if (!segment)
 117             continue;
 118         store->segments.append(segment);
 119         ++right;
 120     }
 121     if (hastrailingslash)
 122     {
 123         store->segments.append("");
 124         ++right;
 125     }
 126     collapse();
 127 }
 128
 129
 130 void UniConfKey::append(const UniConfKey &_key)
 131 {
 132     bool hastrailingslash = _key.isempty() || _key.hastrailingslash();
 133     unique();
 134     store->segments.resize(right - left + _key.right - _key.left + 1);
 135     for (int j=_key.left; j<_key.right; ++j)
 136     {
 137         const Segment &segment = _key.store->segments[j];
 138         if (!segment)
 139             continue;
 140         store->segments.replace(right, segment);
 141         ++right;
 142     }
 143     if (hastrailingslash)
 144     {
 145         store->segments.replace(right, "");
 146         ++right;
 147     }
 148     collapse();
 149 }
 150
 151
 152 void UniConfKey::prepend(const UniConfKey &_key)
 153 {
 154     unique();
 155     int shift = 0;
 156     for (int j=_key.left; j<_key.right; ++j)
 157     {
 158         if (!!_key.store->segments[j])
 159             ++shift;
 160     }
 161     store->segments.resize(shift + right - left, shift);
 162     for (int j=_key.left; j<_key.right; ++j)
 163     {
 164         const Segment &segment = _key.store->segments[j];
 165         if (!segment)
 166             continue;
 167         store->segments.replace(left + j - _key.left, segment);
 168         ++right;
 169     }
 170     collapse();
 171 }
 172
 173
 174 bool UniConfKey::iswild() const
 175 {
 176     for (int i=left; i<right; ++i)
 177         if (store->segments[i].iswild())
 178             return true;
 179     return false;
 180 }
 181
 182
 183 UniConfKey UniConfKey::pop(int n)
 184 {
 185     if (n == 0)
 186         return UniConfKey();
 187     unique();
 188     if (n > right - left)
 189         n = right - left;
 190     if (n < 0)
 191         n = 0;
 192     int old_left = left;
 193     left += n;
 194     UniConfKey result(store, old_left, left);
 195     collapse();
 196     return result.collapse();
 197 }
 198
 199
 200 UniConfKey UniConfKey::range(int i, int j) const
 201 {
 202     if (j > right - left)
 203         j = right - left;
 204     if (i < 0)
 205         i = 0;
 206     if (j < i)
 207         j = i;
 208     return UniConfKey(store, left + i, left + j).collapse();
 209 }
 210
 211
 212 WvString UniConfKey::printable() const
 213 {
 214     switch (right - left)
 215     {
 216         case 0:
 217             return WvString::empty;
 218         case 1:
 219             return store->segments[left];
 220         default:
 221         {
 222             WvDynBuf buf;
 223             for (int i=left; i<right; ++i)
 224             {
 225                 buf.putstr(store->segments[i]);
 226                 if (i < right-1)
 227                     buf.put('/');
 228             }
 229             return buf.getstr();
 230         }
 231     }
 232 }
 233
 234
 235 int UniConfKey::compareto(const UniConfKey &other) const
 236 {
 237     int i, j;
 238     for (i=left, j=other.left; i<right && j<other.right; ++i, ++j)
 239     {
 240         int val = strcasecmp(store->segments[i], other.store->segments[j]);
 241         if (val != 0)
 242             return val;
 243     }
 244     if (i == right)
 245     {
 246         if (j == other.right)
 247             return 0;
 248         else
 249             return -1;
 250     }
 251     else
 252         return 1;
 253 }
 254
 255
 256 bool UniConfKey::matches(const UniConfKey &pattern) const
 257 {
 258     // TODO: optimize this function
 259     if (*this == pattern)
 260         return true;
 261
 262     UniConfKey head(pattern.first());
 263
 264     // handle * wildcard
 265     if (head == UniConfKey::ANY)
 266     {
 267         if (isempty())
 268             return false;
 269         return removefirst().matches(pattern.removefirst());
 270     }
 271
 272     // handle ... wildcard
 273     if (head == UniConfKey::RECURSIVE_ANY)
 274     {
 275         UniConfKey tail(pattern.removefirst());
 276         if (tail.isempty())
 277             return true; // recursively matches anything
 278         for (int n = 0; ; ++n)
 279         {
 280             UniConfKey part(removefirst(n));
 281             if (part.matches(tail))
 282                 return true;
 283             if (part.isempty())
 284                 break;
 285         }
 286         return false;
 287     }
 288
 289     // no other wildcard arrangements currently supported
 290     return false;
 291 }
 292
 293
 294 bool UniConfKey::suborsame(const UniConfKey &key) const
 295 {
 296     int n = numsegments();
 297     if (hastrailingslash())
 298         n -= 1;
 299
 300     if (key.first(n) == first(n))
 301         return true;
 302     return false;
 303 }
 304
 305
 306 bool UniConfKey::suborsame(const UniConfKey &key, UniConfKey &subkey) const
 307 {
 308     int n = numsegments();
 309
 310     // Compensate for the directory-style naming convention of the
 311     // trailing slash.
 312     if (hastrailingslash())
 313         n -= 1;
 314
 315     if (key.first(n) == first(n))
 316     {
 317         subkey = key.removefirst(n);
 318         return true;
 319     }
 320     return false;
 321 }
 322
 323
 324 UniConfKey UniConfKey::subkey(const UniConfKey &key) const
 325 {
 326     UniConfKey answer;
 327     wvassert(suborsame(key, answer),
 328              "this = '%s'\nkey = '%s'", printable(), key);
 329     return answer;
 330 }