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