include/uniconfkey.h

   1 /* -*- Mode: C++ -*-
   2  * Worldvisions Weaver Software:
   3  *   Copyright (C) 2002 Net Integration Technologies, Inc.
   4  *
   5  * UniConfKeys are paths in the UniConf hierarchy.
   6  */
   7 #ifndef __UNICONFKEY_H
   8 #define __UNICONFKEY_H
   9
  10 #include "wvstring.h"
  11 #include "wvlinklist.h"
  12
  13
  14 // The Python headers try to #define ANY as void.  If we're building Python
  15 // wrappers, get rid of that.
  16 #undef ANY
  17
  18
  19 /**
  20  * Represents a UniConf key which is a path in a hierarchy structured much
  21  * like the traditional Unix filesystem.
  22  *
  23  * - Segments in the path are delimited by slashes.
  24  * - The empty string refers to the current level of the tree (eg. root).
  25  * - Keys are case insensitive yet preserve case information.
  26  * - Paired slashes are converted to single slashes.
  27  * - Trailing slashes are discarded.
  28  *
  29  * The following paths are equivalent when canonicalized:
  30  *
  31  * - foo/key (the canonical representation)
  32  * - Foo/Key (also canonical but preserves case)
  33  * - /foo/key (converted to foo/key)
  34  * - foo//key (converted to foo/key)
  35  * - foo/key/ (converted to foo/key)
  36  *
  37  * Keys that may contain slashes or nulls should be escaped in some fashion
  38  * prior to constructing a UniConfKey object. Simply prefixing slashes with
  39  * backslashes is inadequate because UniConfKey does not give any special
  40  * meaning to backslash.
  41  */
  42 class UniConfKey
  43 {
  44     class Segment : public WvString
  45     {
  46     public:
  47         Segment() :
  48             WvString(WvString::empty)
  49         {
  50         }
  51         Segment(WvStringParm str) :
  52             WvString((!str)? WvString::empty: str)
  53         {
  54         }
  55         Segment(const Segment &segment) :
  56             WvString(segment)
  57         {
  58         }
  59
  60         bool iswild() const
  61         {
  62             return *this == "*" || *this == "...";
  63         }
  64     };
  65
  66     class SegmentVector
  67     {
  68         int _size, _used;
  69         Segment *vec;
  70     public:
  71         SegmentVector(int size) :
  72             _size(size),
  73             _used(0),
  74             vec(new Segment[_size])
  75         {
  76         }
  77         ~SegmentVector()
  78         {
  79             deletev vec;
  80         }
  81
  82         void resize(int size, int shift = 0)
  83         {
  84             if (size <= _size)
  85             {
  86                 if (shift > 0)
  87                 {
  88                     for (int i=_used-1; i>=0; --i)
  89                         vec[i+shift] = vec[i];
  90                     _used += shift;
  91                 }
  92                 return;
  93             }
  94             Segment *old_vec = vec;
  95             vec = new Segment[size];
  96             if (old_vec)
  97             {
  98                 int limit = size-shift;
  99                 if (limit > _size)
 100                     limit = _size;
 101                 if (limit > _used)
 102                     limit = _used;
 103                 for (int i=0; i<limit; ++i)
 104                     vec[i+shift] = old_vec[i];
 105                 deletev old_vec;
 106             }
 107             _size = size;
 108             _used += shift;
 109         }
 110         void zap()
 111         {
 112             _used = 0;
 113         }
 114         int size() const
 115         {
 116             return _size;
 117         }
 118         int used() const
 119         {
 120             return _used;
 121         }
 122
 123         void append(const Segment &segment)
 124         {
 125             vec[_used++] = segment;
 126         }
 127         void append(WvStringParm string)
 128         {
 129             append(Segment(string));
 130         }
 131         void replace(int index, const Segment &segment)
 132         {
 133             vec[index] = segment;
 134             if (index >= _used)
 135                 _used = index + 1;
 136         }
 137         void replace(int index, WvStringParm string)
 138         {
 139             replace(index, Segment(string));
 140         }
 141         const Segment &operator [](int index) const
 142         {
 143             return vec[index];
 144         }
 145     };
 146
 147     struct Store
 148     {
 149         SegmentVector segments;
 150         int ref_count;
 151
 152         Store(int size, int _ref_count, WvStringParm key = WvString::null);
 153     };
 154
 155     Store *store;
 156     int left, right;
 157
 158     static Store EMPTY_store; /*!< represents "" (root) */
 159     static Store ANY_store;   /*!< represents "*" */
 160     static Store RECURSIVE_ANY_store; /*!< represents "..." */
 161
 162     UniConfKey(Store *_store, int _left, int _right) :
 163         store(_store),
 164         left(_left),
 165         right(_right)
 166     {
 167         store->ref_count++;
 168     }
 169
 170     void unique();
 171     void normalize();
 172     UniConfKey &collapse();
 173
 174 public:
 175     static UniConfKey EMPTY; /*!< represents "" (root) */
 176     static UniConfKey ANY;   /*!< represents "*" */
 177     static UniConfKey RECURSIVE_ANY; /*!< represents "..." */
 178
 179     /** Constructs an empty UniConfKey (the 'root'). */
 180     UniConfKey() :
 181         store(&EMPTY_store),
 182         left(0),
 183         right(0)
 184     {
 185         store->ref_count++;
 186     }
 187
 188     /**
 189      * Constructs a UniConfKey from a string.
 190      *
 191      * See the rules above for information about how the key string
 192      * is canonicalized.
 193      *
 194      * "key" is the key as a string
 195      */
 196     UniConfKey(WvStringParm key) :
 197         store(new Store(4, 1, key)),
 198         left(0),
 199         right(store->segments.used())
 200     {
 201     }
 202
 203     /**
 204      * Constructs a UniConfKey from a string.
 205      *
 206      * See the rules above for information about how the key string
 207      * is canonicalized.  This constructor only exists to help out the
 208      * C++ compiler with its automatic type conversions.
 209      *
 210      * "key" is the key as a string
 211      */
 212     UniConfKey(const char *key) :
 213         store(new Store(4, 1, WvFastString(key))),
 214         left(0),
 215         right(store->segments.used())
 216     {
 217     }
 218
 219     /** Constructs a UniConfKey from an int. */
 220     UniConfKey(int key) :
 221         store(new Store(1, 1, WvFastString(key))),
 222         left(0),
 223         right(store->segments.used())
 224     {
 225     }
 226
 227     /**
 228      * Copies a UniConfKey.
 229      * "other" is the key to copy
 230      */
 231     UniConfKey(const UniConfKey &other) :
 232         store(other.store),
 233         left(other.left),
 234         right(other.right)
 235     {
 236         store->ref_count++;
 237     }
 238
 239     /**
 240      * Constructs a UniConfKey by concatenating two keys.
 241      * "path" is the initial part of the new path
 242      * "key" is the tail of the new path
 243      */
 244     UniConfKey(const UniConfKey &path, const UniConfKey &key);
 245
 246     ~UniConfKey()
 247     {
 248         if (--store->ref_count == 0)
 249             delete store;
 250     }
 251
 252     /**
 253      * Appends a path to this path.
 254      * "other" is the path
 255      */
 256     void append(const UniConfKey &other);
 257
 258     /**
 259      * Prepends a path to this path.
 260      * "other" is the path
 261      */
 262     void prepend(const UniConfKey &other);
 263
 264     /**
 265      * Returns true if this path has zero segments (also known as root).
 266      * Returns: numsegments() == 0
 267      */
 268     bool isempty() const
 269     {
 270         return right == left;
 271     }
 272
 273     /** Returns true if the key contains a wildcard. */
 274     bool iswild() const;
 275
 276     /** Returns true if the key has a trailing slash. */
 277     bool hastrailingslash() const
 278     {
 279         return right > left && !store->segments[right-1];
 280     }
 281
 282     /**
 283      * Returns the number of segments in this path.
 284      *
 285      * The number of segments is equal to the number of slashes
 286      * in the path unless the path is "/" (the root), which has
 287      * zero segments.
 288      *
 289      * Returns: the number of segments
 290      */
 291     int numsegments() const
 292     {
 293         return right - left;
 294     }
 295
 296     /**
 297      * Returns the specified segment of the path.
 298      * "i" is the segment index
 299      * Returns: the segment
 300      */
 301     UniConfKey segment(int n) const
 302     {
 303         return range(n, n + 1);
 304     }
 305
 306     /**
 307      * Returns the path formed by the first n segments of this path and
 308      * removes them from the key.
 309      * Returns: the path
 310      */
 311     UniConfKey pop(int n = 1);
 312
 313     /**
 314      * Returns the path formed by the n first segments of this path.
 315      * "n" is the number of segments
 316      * Returns: the path
 317      */
 318     UniConfKey first(int n = 1) const
 319     {
 320         return range(0, n);
 321     }
 322
 323     /**
 324      * Returns the path formed by the n last segments of this path.
 325      * "n" is the number of segments
 326      * Returns: the path
 327      */
 328     UniConfKey last(int n = 1) const
 329     {
 330         return range(numsegments() - n, INT_MAX);
 331     }
 332
 333     /**
 334      * Returns the path formed by removing the first n segments of
 335      *   this path.
 336      * "n" is the number of segments
 337      * Returns: the path
 338      */
 339     UniConfKey removefirst(int n = 1) const
 340     {
 341         return range(n, INT_MAX);
 342     }
 343
 344     /**
 345      * Returns the path formed by removing the last n segments of
 346      *   this path.
 347      * "n" is the number of segments
 348      * Returns: the path
 349      */
 350     UniConfKey removelast(int n = 1) const
 351     {
 352         return range(0, numsegments() - n);
 353     }
 354
 355     /**
 356      * Returns a range of segments.
 357      * "i" is the first segment index, beginning if <= 0
 358      * "j" is the last segment index, end if >= numsegments()
 359      * Returns: the path, empty if j <= i
 360      */
 361     UniConfKey range(int i, int j) const;
 362
 363     /**
 364      * Returns the canonical string representation of the path.
 365      *
 366      * If the UniConfKey was constructed in part or whole from
 367      * strings, then the string returned here will have the same
 368      * case information as those strings but the arrangement of
 369      * slashes may differ.  That is, the identity
 370      * UniConfKey(string).printable() == string does not hold.
 371      *
 372      * Returns: the path as a string
 373      */
 374     WvString printable() const;
 375     operator WvString() const
 376         { return printable(); }
 377
 378     /**
 379      * Returns a (const char *) of printable() directly.
 380      */
 381     const char *cstr() const
 382         { return printable(); }
 383
 384     /**
 385      * Assigns this path to equal another.
 386      * "other" is the other path
 387      */
 388     UniConfKey &operator= (const UniConfKey &other)
 389     {
 390         if (--store->ref_count == 0)
 391             delete store;
 392         store = other.store;
 393         left = other.left;
 394         right = other.right;
 395         ++store->ref_count;
 396         return *this;
 397     }
 398
 399     /**
 400      * Compares two paths lexicographically.
 401      * Uses case-insensitive matching on the path string to produce
 402      * a total ordering of all paths.
 403      * "other" is the other path
 404      * Returns: 0 if *this == other, < 0 if *this < other, else > 0
 405      */
 406     int compareto(const UniConfKey &other) const;
 407
 408     /**
 409      * Determines if the key matches a pattern.
 410      * Patterns are simply keys that may have path segments consiting
 411      * entirely of "*".  Optional path segments are indicated by
 412      * the segment "..." which matches zero or more segments.
 413      *
 414      * Using wildcards to represent part of a segment is not supported yet.
 415      * "pattern" is the pattern
 416      * Returns: true if the key matches, false otherwise
 417      */
 418     bool matches(const UniConfKey &pattern) const;
 419
 420
 421     /**
 422      * Returns true if 'key' is a the same, or a subkey, of this UniConfKey.
 423      */
 424     bool suborsame(const UniConfKey &key) const;
 425     bool suborsame(const UniConfKey &key, UniConfKey &subkey) const;
 426
 427     /**
 428      * If this UniConfKey is a subkey of 'key', then return the subkey
 429      * portion.  Behaviour is undefined when this is not the same.  Use
 430      * suborsame() to check.
 431      */
 432     UniConfKey subkey(const UniConfKey &key) const;
 433
 434     /**
 435      * Determines if two paths are equal.
 436      * "other" is the other path
 437      * Returns: true in that case
 438      */
 439     bool operator== (const UniConfKey &other) const
 440         { return compareto(other) == 0; }
 441
 442     /**
 443      * Determines if two paths are unequal.
 444      * "other" is the other path
 445      * Returns: true in that case
 446      */
 447     bool operator!= (const UniConfKey &other) const
 448         { return compareto(other) != 0; }
 449
 450     /**
 451      * Determines if this path precedes the other lexicographically.
 452      * "other" is the other path
 453      * Returns: true in that case
 454      */
 455     bool operator< (const UniConfKey &other) const
 456         { return compareto(other) < 0; }
 457
 458     class Iter;
 459
 460     friend unsigned WvHash(const UniConfKey &k);
 461 };
 462
 463
 464 DeclareWvList(UniConfKey);
 465
 466 /** An iterator over the segments of a key. */
 467 class UniConfKey::Iter
 468 {
 469     const UniConfKey &key;
 470     int seg, max;
 471     UniConfKey curseg;
 472
 473 public:
 474     Iter(const UniConfKey &_key) : key(_key)
 475         { }
 476
 477     void rewind()
 478         { seg = -1; max = key.numsegments(); }
 479
 480     bool cur()
 481         { return seg >= 0 && seg < max; }
 482
 483     bool next()
 484         { seg++; curseg = key.segment(seg); return cur(); }
 485
 486     const UniConfKey *ptr() const
 487         { return &curseg; }
 488
 489     WvIterStuff(const UniConfKey);
 490 };
 491
 492 #endif // __UNICONFKEY_H