contrib/subversion/subversion/include/private/svn_element.h

   1 /**
   2  * @copyright
   3  * ====================================================================
   4  *    Licensed to the Apache Software Foundation (ASF) under one
   5  *    or more contributor license agreements.  See the NOTICE file
   6  *    distributed with this work for additional information
   7  *    regarding copyright ownership.  The ASF licenses this file
   8  *    to you under the Apache License, Version 2.0 (the
   9  *    "License"); you may not use this file except in compliance
  10  *    with the License.  You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  *    Unless required by applicable law or agreed to in writing,
  15  *    software distributed under the License is distributed on an
  16  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  17  *    KIND, either express or implied.  See the License for the
  18  *    specific language governing permissions and limitations
  19  *    under the License.
  20  * ====================================================================
  21  * @endcopyright
  22  *
  23  * @file svn_element.h
  24  * @brief Tree elements
  25  *
  26  * @since New in ???.
  27  */
  28
  29 #ifndef SVN_BRANCH_ELEMENT_H
  30 #define SVN_BRANCH_ELEMENT_H
  31
  32 #include <apr_pools.h>
  33 #include <apr_tables.h>
  34
  35 #include "svn_types.h"
  36
  37 #ifdef __cplusplus
  38 extern "C" {
  39 #endif /* __cplusplus */
  40
  41
  42 /* ====================================================================== */
  43
  44 /** Like apr_hash_get() but the hash key is an integer. */
  45 void *
  46 svn_eid__hash_get(apr_hash_t *ht,
  47                   int key);
  48
  49 /** Like apr_hash_set() but the hash key is an integer. */
  50 void
  51 svn_eid__hash_set(apr_hash_t *ht,
  52                   int key,
  53                   const void *val);
  54
  55 /** Like apr_hash_this_key() but the hash key is an integer. */
  56 int
  57 svn_eid__hash_this_key(apr_hash_index_t *hi);
  58
  59 struct svn_sort__item_t;
  60
  61 /** A hash iterator for iterating over an array or a hash table in
  62  * its natural order or in sorted order.
  63  *
  64  * For an array, the @a i and @a val members provide the index and value
  65  * of the current item.
  66  */
  67 typedef struct svn_eid__hash_iter_t
  68 {
  69   /* private: an array of (svn_sort__item_t) hash items for sorted iteration */
  70   const apr_array_header_t *array;
  71
  72   /* current element: iteration order index */
  73   int i;
  74   /* current element: key */
  75   int eid;
  76   /* current element: value */
  77   void *val;
  78 } svn_eid__hash_iter_t;
  79
  80 svn_eid__hash_iter_t *
  81 svn_eid__hash_sorted_first(apr_pool_t *pool,
  82                            apr_hash_t *ht,
  83                            int (*comparison_func)(const struct svn_sort__item_t *,
  84                                                   const struct svn_sort__item_t *));
  85
  86 svn_eid__hash_iter_t *
  87 svn_eid__hash_sorted_next(svn_eid__hash_iter_t *hi);
  88
  89 /** A sort ordering callback function that returns an indication whether
  90  * A sorts before or after or equal to B, by comparing their keys as EIDs.
  91  */
  92 int
  93 svn_eid__hash_sort_compare_items_by_eid(const struct svn_sort__item_t *a,
  94                                         const struct svn_sort__item_t *b);
  95
  96 #define SVN_EID__HASH_ITER_SORTED(i, ht, comparison_func, pool) \
  97   i = (void *)svn_eid__hash_sorted_first(pool, ht, comparison_func); \
  98   i; \
  99   i = (void *)svn_eid__hash_sorted_next((void *)i)
 100
 101 #define SVN_EID__HASH_ITER_SORTED_BY_EID(i, ht, pool) \
 102   SVN_EID__HASH_ITER_SORTED(i, ht, svn_eid__hash_sort_compare_items_by_eid, pool)
 103
 104
 105 /* ====================================================================== */
 106
 107 /**
 108  */
 109 typedef struct svn_element__branch_ref_t
 110 {
 111   svn_revnum_t rev;
 112   const char *branch_id;
 113   int eid;
 114 } svn_element__branch_ref_t;
 115
 116 /** Versioned payload of an element, excluding tree structure information.
 117  *
 118  * This specifies the properties and the text of a file or target of a
 119  * symlink, directly, or by reference to an existing committed element, or
 120  * by a delta against such a reference payload.
 121  *
 122  * ### An idea: If the sender and receiver agree, the payload for an element
 123  *     may be specified as "null" to designate that the payload is not
 124  *     available. For example, when a client performing a WC update has
 125  *     no read authorization for a given path, the server may send null
 126  *     payload and the client may record an 'absent' WC node. (This
 127  *     would not make sense in a commit.)
 128  */
 129 typedef struct svn_element__payload_t svn_element__payload_t;
 130
 131 /*
 132  * ========================================================================
 133  * Element Payload Interface
 134  * ========================================================================
 135  *
 136  * @defgroup svn_element_payload Element payload interface
 137  * @{
 138  */
 139
 140 /** Versioned payload of a node, excluding tree structure information.
 141  *
 142  * Payload is described by setting fields in one of the following ways.
 143  * Other fields SHOULD be null (or equivalent).
 144  *
 145  *   by reference:  (kind=unknown, ref)
 146  *   dir:           (kind=dir, props)
 147  *   file:          (kind=file, props, text)
 148  *   symlink:       (kind=symlink, props, target)
 149  *
 150  * ### Idea for the future: Specify payload as an (optional) reference
 151  *     plus (optional) overrides or deltas against the reference?
 152  */
 153 struct svn_element__payload_t
 154 {
 155   /* Is this a subbranch-root element, in other words a link to a nested
 156    * branch? If so, all other fields are irrelevant. */
 157   svn_boolean_t is_subbranch_root;
 158
 159   /* The node kind for this payload: dir, file, symlink, or unknown. */
 160   svn_node_kind_t kind;
 161
 162   /* Reference an existing, committed payload. (Use with kind=unknown if
 163    * there is no content in props/text/targe fields.)
 164    * The 'null' value is (SVN_INVALID_REVNUM, NULL, *). */
 165   svn_element__branch_ref_t branch_ref;
 166
 167   /* The pool in which the payload's content is allocated. Used when
 168    * resolving (populating the props/text/target in) a payload that was
 169    * originally defined by reference. */
 170   apr_pool_t *pool;
 171
 172   /* Properties (for kind != unknown).
 173    * Maps (const char *) name -> (svn_string_t) value.
 174    * An empty hash means no properties. (SHOULD NOT be NULL.)
 175    * ### Presently NULL means 'no change' in some contexts. */
 176   apr_hash_t *props;
 177
 178   /* File text (for kind=file; otherwise SHOULD be NULL). */
 179   svn_stringbuf_t *text;
 180
 181   /* Symlink target (for kind=symlink; otherwise SHOULD be NULL). */
 182   const char *target;
 183
 184 };
 185
 186 /* Return true iff PAYLOAD satisfies all its invariants.
 187  */
 188 svn_boolean_t
 189 svn_element__payload_invariants(const svn_element__payload_t *payload);
 190
 191 /** Duplicate a node-payload @a old into @a result_pool.
 192  */
 193 svn_element__payload_t *
 194 svn_element__payload_dup(const svn_element__payload_t *old,
 195                          apr_pool_t *result_pool);
 196
 197 /* Return true iff the payload of LEFT is identical to that of RIGHT.
 198  * References are not supported. Node kind 'unknown' is not supported.
 199  */
 200 svn_boolean_t
 201 svn_element__payload_equal(const svn_element__payload_t *left,
 202                            const svn_element__payload_t *right,
 203                            apr_pool_t *scratch_pool);
 204
 205 /** Create a new node-payload object for a subbranch-root (link to a
 206  * nested branch).
 207  *
 208  * Allocate the result in @a result_pool.
 209  */
 210 svn_element__payload_t *
 211 svn_element__payload_create_subbranch(apr_pool_t *result_pool);
 212
 213 /** Create a new node-payload object by reference to an existing payload.
 214  *
 215  * Set the node kind to 'unknown'.
 216  *
 217  * Allocate the result in @a result_pool.
 218  */
 219 svn_element__payload_t *
 220 svn_element__payload_create_ref(svn_revnum_t rev,
 221                                 const char *branch_id,
 222                                 int eid,
 223                                 apr_pool_t *result_pool);
 224
 225 /** Create a new node-payload object for a directory node.
 226  *
 227  * Allocate the result in @a result_pool.
 228  */
 229 svn_element__payload_t *
 230 svn_element__payload_create_dir(apr_hash_t *props,
 231                                 apr_pool_t *result_pool);
 232
 233 /** Create a new node-payload object for a file node.
 234  *
 235  * Allocate the result in @a result_pool.
 236  */
 237 svn_element__payload_t *
 238 svn_element__payload_create_file(apr_hash_t *props,
 239                                  svn_stringbuf_t *text,
 240                                  apr_pool_t *result_pool);
 241
 242 /** Create a new node-payload object for a symlink node.
 243  *
 244  * Allocate the result in @a result_pool.
 245  */
 246 svn_element__payload_t *
 247 svn_element__payload_create_symlink(apr_hash_t *props,
 248                                     const char *target,
 249                                     apr_pool_t *result_pool);
 250
 251 /** @} */
 252
 253
 254 /*
 255  * ========================================================================
 256  * Element-Revision Content
 257  * ========================================================================
 258  *
 259  * @defgroup svn_el_rev_content Element-Revision Content
 260  * @{
 261  */
 262
 263 /* The content (parent, name and payload) of an element-revision.
 264  * In other words, an el-rev node in a (mixed-rev) directory-tree.
 265  */
 266 typedef struct svn_element__content_t
 267 {
 268   /* eid of the parent element, or -1 if this is the root element */
 269   int parent_eid;
 270   /* element name, or "" for root element; never null */
 271   const char *name;
 272   /* payload (kind, props, text, ...) */
 273   svn_element__payload_t *payload;
 274
 275 } svn_element__content_t;
 276
 277 /* Return a new content object constructed with deep copies of PARENT_EID,
 278  * NAME and PAYLOAD, allocated in RESULT_POOL.
 279  */
 280 svn_element__content_t *
 281 svn_element__content_create(int parent_eid,
 282                             const char *name,
 283                             const svn_element__payload_t *payload,
 284                             apr_pool_t *result_pool);
 285
 286 /* Return a deep copy of OLD, allocated in RESULT_POOL.
 287  */
 288 svn_element__content_t *
 289 svn_element__content_dup(const svn_element__content_t *old,
 290                          apr_pool_t *result_pool);
 291
 292 /* Return TRUE iff CONTENT_LEFT is the same as CONTENT_RIGHT. */
 293 svn_boolean_t
 294 svn_element__content_equal(const svn_element__content_t *content_left,
 295                            const svn_element__content_t *content_right,
 296                            apr_pool_t *scratch_pool);
 297
 298 /** @} */
 299
 300
 301 /*
 302  * ========================================================================
 303  * Element Tree
 304  * ========================================================================
 305  *
 306  * The elements in an Element Tree do not necessarily form a single,
 307  * complete tree at all times.
 308  *
 309  * @defgroup svn_element_tree Element Tree
 310  * @{
 311  */
 312
 313 /* A (sub)tree of elements.
 314  *
 315  * An element tree is described by the content of element ROOT_EID in E_MAP,
 316  * and its children (as determined by their parent links) and their names
 317  * and their content recursively. For the element ROOT_EID itself, only
 318  * its content is relevant; its parent and name are to be ignored.
 319  *
 320  * E_MAP may also contain entries that are not part of the subtree. Thus,
 321  * to select a sub-subtree, it is only necessary to change ROOT_EID.
 322  *
 323  * The EIDs used in here may be considered either as global EIDs (known to
 324  * the repo), or as local stand-alone EIDs (in their own local name-space),
 325  * according to the context.
 326  */
 327 typedef struct svn_element__tree_t
 328 {
 329   /* EID -> svn_element__content_t mapping. */
 330   apr_hash_t *e_map;
 331
 332   /* Subtree root EID. (ROOT_EID must be an existing key in E_MAP.) */
 333   int root_eid;
 334
 335 } svn_element__tree_t;
 336
 337 /* Create an element tree object.
 338  *
 339  * The result contains a *shallow* copy of E_MAP, or a new empty mapping
 340  * if E_MAP is null.
 341  */
 342 svn_element__tree_t *
 343 svn_element__tree_create(apr_hash_t *e_map,
 344                          int root_eid,
 345                          apr_pool_t *result_pool);
 346
 347 svn_element__content_t *
 348 svn_element__tree_get(const svn_element__tree_t *tree,
 349                       int eid);
 350
 351 void
 352 svn_element__tree_set(svn_element__tree_t *tree,
 353                       int eid,
 354                       const svn_element__content_t *element);
 355
 356 /* Purge entries from E_MAP that don't connect, via parent directory hierarchy,
 357  * to ROOT_EID. In other words, remove elements that have been implicitly
 358  * deleted.
 359  *
 360  * ROOT_EID must be present in E_MAP.
 361  *
 362  * ### Does not detect cycles: current implementation will not purge a cycle
 363  *     that is disconnected from ROOT_EID. This could be a problem.
 364  */
 365 void
 366 svn_element__tree_purge_orphans(apr_hash_t *e_map,
 367                                 int root_eid,
 368                                 apr_pool_t *scratch_pool);
 369
 370 /* Return the subtree-relative path of element EID in TREE.
 371  *
 372  * If the element EID does not currently exist in TREE, return NULL.
 373  *
 374  * ### TODO: Clarify sequencing requirements.
 375  */
 376 const char *
 377 svn_element__tree_get_path_by_eid(const svn_element__tree_t *tree,
 378                                   int eid,
 379                                   apr_pool_t *result_pool);
 380
 381 /* Return the subtree rooted at EID within ELEMENT_TREE.
 382  *
 383  * The result is limited by the lifetime of ELEMENT_TREE. It includes a
 384  * shallow copy of the mapping in ELEMENT_TREE: the hash table is
 385  * duplicated but the keys and values (element content data) are not.
 386  */
 387 svn_element__tree_t *
 388 svn_element__tree_get_subtree_at_eid(svn_element__tree_t *element_tree,
 389                                      int eid,
 390                                      apr_pool_t *result_pool);
 391
 392 /** @} */
 393
 394
 395 #ifdef __cplusplus
 396 }
 397 #endif /* __cplusplus */
 398
 399 #endif /* SVN_BRANCH_ELEMENT_H */