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