subversion/libsvn_subr/hash.c

   1 /*
   2  * hash.c :  dumping and reading hash tables to/from files.
   3  *
   4  * ====================================================================
   5  * Copyright (c) 2000-2004 CollabNet.  All rights reserved.
   6  *
   7  * This software is licensed as described in the file COPYING, which
   8  * you should have received as part of this distribution.  The terms
   9  * are also available at http://subversion.tigris.org/license-1.html.
  10  * If newer versions of this license are posted there, you may use a
  11  * newer version instead, at your option.
  12  *
  13  * This software consists of voluntary contributions made by many
  14  * individuals.  For exact contribution history, see the revision
  15  * history and logs, available at http://subversion.tigris.org/.
  16  * ====================================================================
  17  */
  18
  19
  20 \f
  21 #include <stdlib.h>
  22 #include <limits.h>
  23 #include <assert.h>
  24 #include <apr_version.h>
  25 #include <apr_pools.h>
  26 #include <apr_hash.h>
  27 #include <apr_file_io.h>
  28 #include "svn_types.h"
  29 #include "svn_string.h"
  30 #include "svn_error.h"
  31 #include "svn_hash.h"
  32 #include "svn_sorts.h"
  33 #include "svn_io.h"
  34 #include "svn_pools.h"
  35 #include "private/svn_dep_compat.h"
  36
  37 \f
  38
  39 /*
  40  * The format of a dumped hash table is:
  41  *
  42  *   K <nlength>
  43  *   name (a string of <nlength> bytes, followed by a newline)
  44  *   V <vlength>
  45  *   val (a string of <vlength> bytes, followed by a newline)
  46  *   [... etc, etc ...]
  47  *   END
  48  *
  49  *
  50  * (Yes, there is a newline after END.)
  51  *
  52  * For example:
  53  *
  54  *   K 5
  55  *   color
  56  *   V 3
  57  *   red
  58  *   K 11
  59  *   wine review
  60  *   V 376
  61  *   A forthright entrance, yet coquettish on the tongue, its deceptively
  62  *   fruity exterior hides the warm mahagony undercurrent that is the
  63  *   hallmark of Chateau Fraisant-Pitre.  Connoisseurs of the region will
  64  *   be pleased to note the familiar, subtle hints of mulberries and
  65  *   carburator fluid.  Its confident finish is marred only by a barely
  66  *   detectable suggestion of rancid squid ink.
  67  *   K 5
  68  *   price
  69  *   V 8
  70  *   US $6.50
  71  *   END
  72  *
  73  */
  74
  75
  76
  77 \f
  78 /*** Dumping and loading hash files. */
  79
  80 /* Implements svn_hash_read2 and svn_hash_read_incremental. */
  81 static svn_error_t *
  82 hash_read(apr_hash_t *hash, svn_stream_t *stream, const char *terminator,
  83           svn_boolean_t incremental, apr_pool_t *pool)
  84 {
  85   svn_stringbuf_t *buf;
  86   svn_boolean_t eof;
  87   apr_size_t len, keylen, vallen;
  88   char c, *end, *keybuf, *valbuf;
  89
  90   while (1)
  91     {
  92       /* Read a key length line.  Might be END, though. */
  93       SVN_ERR(svn_stream_readline(stream, &buf, "\n", &eof, pool));
  94
  95       /* Check for the end of the hash. */
  96       if ((!terminator && eof && buf->len == 0)
  97           || (terminator && (strcmp(buf->data, terminator) == 0)))
  98         return SVN_NO_ERROR;
  99
 100       /* Check for unexpected end of stream */
 101       if (eof)
 102         return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 103
 104       if ((buf->len >= 3) && (buf->data[0] == 'K') && (buf->data[1] == ' '))
 105         {
 106           /* Get the length of the key */
 107           keylen = (size_t) strtoul(buf->data + 2, &end, 10);
 108           if (keylen == (size_t) ULONG_MAX || *end != '\0')
 109             return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 110
 111           /* Now read that much into a buffer. */
 112           keybuf = apr_palloc(pool, keylen + 1);
 113           SVN_ERR(svn_stream_read(stream, keybuf, &keylen));
 114           keybuf[keylen] = '\0';
 115
 116           /* Suck up extra newline after key data */
 117           len = 1;
 118           SVN_ERR(svn_stream_read(stream, &c, &len));
 119           if (c != '\n')
 120             return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 121
 122           /* Read a val length line */
 123           SVN_ERR(svn_stream_readline(stream, &buf, "\n", &eof, pool));
 124
 125           if ((buf->data[0] == 'V') && (buf->data[1] == ' '))
 126             {
 127               vallen = (size_t) strtoul(buf->data + 2, &end, 10);
 128               if (vallen == (size_t) ULONG_MAX || *end != '\0')
 129                 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 130
 131               valbuf = apr_palloc(pool, vallen + 1);
 132               SVN_ERR(svn_stream_read(stream, valbuf, &vallen));
 133               valbuf[vallen] = '\0';
 134
 135               /* Suck up extra newline after val data */
 136               len = 1;
 137               SVN_ERR(svn_stream_read(stream, &c, &len));
 138               if (c != '\n')
 139                 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 140
 141               /* Add a new hash entry. */
 142               apr_hash_set(hash, keybuf, keylen,
 143                            svn_string_ncreate(valbuf, vallen, pool));
 144             }
 145           else
 146             return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 147         }
 148       else if (incremental && (buf->len >= 3)
 149                && (buf->data[0] == 'D') && (buf->data[1] == ' '))
 150         {
 151           /* Get the length of the key */
 152           keylen = (size_t) strtoul(buf->data + 2, &end, 10);
 153           if (keylen == (size_t) ULONG_MAX || *end != '\0')
 154             return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 155
 156           /* Now read that much into a buffer. */
 157           keybuf = apr_palloc(pool, keylen + 1);
 158           SVN_ERR(svn_stream_read(stream, keybuf, &keylen));
 159           keybuf[keylen] = '\0';
 160
 161           /* Suck up extra newline after key data */
 162           len = 1;
 163           SVN_ERR(svn_stream_read(stream, &c, &len));
 164           if (c != '\n')
 165             return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 166
 167           /* Remove this hash entry. */
 168           apr_hash_set(hash, keybuf, keylen, NULL);
 169         }
 170       else
 171         return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 172     }
 173 }
 174
 175
 176 /* Implements svn_hash_write2 and svn_hash_write_incremental. */
 177 static svn_error_t *
 178 hash_write(apr_hash_t *hash, apr_hash_t *oldhash, svn_stream_t *stream,
 179            const char *terminator, apr_pool_t *pool)
 180 {
 181   apr_pool_t *subpool;
 182   apr_size_t len;
 183   apr_array_header_t *list;
 184   int i;
 185
 186   subpool = svn_pool_create(pool);
 187
 188   list = svn_sort__hash(hash, svn_sort_compare_items_lexically, pool);
 189   for (i = 0; i < list->nelts; i++)
 190     {
 191       svn_sort__item_t *item = &APR_ARRAY_IDX(list, i, svn_sort__item_t);
 192       svn_string_t *valstr = item->value;
 193
 194       svn_pool_clear(subpool);
 195
 196       /* Don't output entries equal to the ones in oldhash, if present. */
 197       if (oldhash)
 198         {
 199           svn_string_t *oldstr = apr_hash_get(oldhash, item->key, item->klen);
 200
 201           if (oldstr && svn_string_compare(valstr, oldstr))
 202             continue;
 203         }
 204
 205       /* Write it out. */
 206       SVN_ERR(svn_stream_printf(stream, subpool,
 207                                 "K %" APR_SSIZE_T_FMT "\n%s\n"
 208                                 "V %" APR_SIZE_T_FMT "\n",
 209                                 item->klen, (const char *) item->key,
 210                                 valstr->len));
 211       len = valstr->len;
 212       SVN_ERR(svn_stream_write(stream, valstr->data, &len));
 213       SVN_ERR(svn_stream_printf(stream, subpool, "\n"));
 214     }
 215
 216   if (oldhash)
 217     {
 218       /* Output a deletion entry for each property in oldhash but not hash. */
 219       list = svn_sort__hash(oldhash, svn_sort_compare_items_lexically,
 220                             pool);
 221       for (i = 0; i < list->nelts; i++)
 222         {
 223           svn_sort__item_t *item = &APR_ARRAY_IDX(list, i, svn_sort__item_t);
 224
 225           svn_pool_clear(subpool);
 226
 227           /* If it's not present in the new hash, write out a D entry. */
 228           if (! apr_hash_get(hash, item->key, item->klen))
 229             SVN_ERR(svn_stream_printf(stream, subpool,
 230                                       "D %" APR_SSIZE_T_FMT "\n%s\n",
 231                                       item->klen, (const char *) item->key));
 232         }
 233     }
 234
 235   if (terminator)
 236     SVN_ERR(svn_stream_printf(stream, subpool, "%s\n", terminator));
 237
 238   svn_pool_destroy(subpool);
 239   return SVN_NO_ERROR;
 240 }
 241
 242
 243 svn_error_t *svn_hash_read2(apr_hash_t *hash, svn_stream_t *stream,
 244                             const char *terminator, apr_pool_t *pool)
 245 {
 246   return hash_read(hash, stream, terminator, FALSE, pool);
 247 }
 248
 249
 250 svn_error_t *svn_hash_read_incremental(apr_hash_t *hash,
 251                                        svn_stream_t *stream,
 252                                        const char *terminator,
 253                                        apr_pool_t *pool)
 254 {
 255   return hash_read(hash, stream, terminator, TRUE, pool);
 256 }
 257
 258
 259 svn_error_t *
 260 svn_hash_write2(apr_hash_t *hash, svn_stream_t *stream,
 261                 const char *terminator, apr_pool_t *pool)
 262 {
 263   return hash_write(hash, NULL, stream, terminator, pool);
 264 }
 265
 266
 267 svn_error_t *
 268 svn_hash_write_incremental(apr_hash_t *hash, apr_hash_t *oldhash,
 269                            svn_stream_t *stream, const char *terminator,
 270                            apr_pool_t *pool)
 271 {
 272   assert(oldhash != NULL);
 273   return hash_write(hash, oldhash, stream, terminator, pool);
 274 }
 275
 276
 277 svn_error_t *
 278 svn_hash_write(apr_hash_t *hash, apr_file_t *destfile, apr_pool_t *pool)
 279 {
 280   return hash_write(hash, NULL, svn_stream_from_aprfile(destfile, pool),
 281                     SVN_HASH_TERMINATOR, pool);
 282 }
 283
 284
 285 /* There are enough quirks in the deprecated svn_hash_read that we
 286    should just preserve its implementation. */
 287 svn_error_t *
 288 svn_hash_read(apr_hash_t *hash,
 289               apr_file_t *srcfile,
 290               apr_pool_t *pool)
 291 {
 292   svn_error_t *err;
 293   char buf[SVN_KEYLINE_MAXLEN];
 294   apr_size_t num_read;
 295   char c;
 296   int first_time = 1;
 297
 298
 299   while (1)
 300     {
 301       /* Read a key length line.  Might be END, though. */
 302       apr_size_t len = sizeof(buf);
 303
 304       err = svn_io_read_length_line(srcfile, buf, &len, pool);
 305       if (err && APR_STATUS_IS_EOF(err->apr_err) && first_time)
 306         {
 307           /* We got an EOF on our very first attempt to read, which
 308              means it's a zero-byte file.  No problem, just go home. */
 309           svn_error_clear(err);
 310           return SVN_NO_ERROR;
 311         }
 312       else if (err)
 313         /* Any other circumstance is a genuine error. */
 314         return err;
 315
 316       first_time = 0;
 317
 318       if (((len == 3) && (buf[0] == 'E') && (buf[1] == 'N') && (buf[2] == 'D'))
 319           || ((len == 9)
 320               && (buf[0] == 'P')
 321               && (buf[1] == 'R')       /* We formerly used just "END" to */
 322               && (buf[2] == 'O')       /* end a property hash, but later */
 323               && (buf[3] == 'P')       /* we added "PROPS-END", so that  */
 324               && (buf[4] == 'S')       /* the fs dump format would be    */
 325               && (buf[5] == '-')       /* more human-readable.  That's   */
 326               && (buf[6] == 'E')       /* why we accept either way here. */
 327               && (buf[7] == 'N')
 328               && (buf[8] == 'D')))
 329         {
 330           /* We've reached the end of the dumped hash table, so leave. */
 331           return SVN_NO_ERROR;
 332         }
 333       else if ((buf[0] == 'K') && (buf[1] == ' '))
 334         {
 335           /* Get the length of the key */
 336           size_t keylen = (size_t) atoi(buf + 2);
 337
 338           /* Now read that much into a buffer, + 1 byte for null terminator */
 339           void *keybuf = apr_palloc(pool, keylen + 1);
 340           SVN_ERR(svn_io_file_read_full(srcfile,
 341                                         keybuf, keylen, &num_read, pool));
 342           ((char *) keybuf)[keylen] = '\0';
 343
 344           /* Suck up extra newline after key data */
 345           SVN_ERR(svn_io_file_getc(&c, srcfile, pool));
 346           if (c != '\n')
 347             return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 348
 349           /* Read a val length line */
 350           len = sizeof(buf);
 351           SVN_ERR(svn_io_read_length_line(srcfile, buf, &len, pool));
 352
 353           if ((buf[0] == 'V') && (buf[1] == ' '))
 354             {
 355               svn_string_t *value = apr_palloc(pool, sizeof(*value));
 356
 357               /* Get the length of the value */
 358               apr_size_t vallen = atoi(buf + 2);
 359
 360               /* Again, 1 extra byte for the null termination. */
 361               void *valbuf = apr_palloc(pool, vallen + 1);
 362               SVN_ERR(svn_io_file_read_full(srcfile,
 363                                             valbuf, vallen,
 364                                             &num_read, pool));
 365               ((char *) valbuf)[vallen] = '\0';
 366
 367               /* Suck up extra newline after val data */
 368               SVN_ERR(svn_io_file_getc(&c, srcfile, pool));
 369               if (c != '\n')
 370                 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 371
 372               value->data = valbuf;
 373               value->len = vallen;
 374
 375               /* The Grand Moment:  add a new hash entry! */
 376               apr_hash_set(hash, keybuf, keylen, value);
 377             }
 378           else
 379             {
 380               return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 381             }
 382         }
 383       else
 384         {
 385           return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
 386         }
 387     } /* while (1) */
 388 }
 389
 390
 391 \f
 392 /*** Diffing hashes ***/
 393
 394 svn_error_t *
 395 svn_hash_diff(apr_hash_t *hash_a,
 396               apr_hash_t *hash_b,
 397               svn_hash_diff_func_t diff_func,
 398               void *diff_func_baton,
 399               apr_pool_t *pool)
 400 {
 401   apr_hash_index_t *hi;
 402
 403   if (hash_a)
 404     for (hi = apr_hash_first(pool, hash_a); hi; hi = apr_hash_next(hi))
 405       {
 406         const void *key;
 407         apr_ssize_t klen;
 408
 409         apr_hash_this(hi, &key, &klen, NULL);
 410
 411         if (hash_b && (apr_hash_get(hash_b, key, klen)))
 412           SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_both,
 413                                diff_func_baton));
 414         else
 415           SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_a,
 416                                diff_func_baton));
 417       }
 418
 419   if (hash_b)
 420     for (hi = apr_hash_first(pool, hash_b); hi; hi = apr_hash_next(hi))
 421       {
 422         const void *key;
 423         apr_ssize_t klen;
 424
 425         apr_hash_this(hi, &key, &klen, NULL);
 426
 427         if (! (hash_a && apr_hash_get(hash_a, key, klen)))
 428           SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_b,
 429                                diff_func_baton));
 430       }
 431
 432   return SVN_NO_ERROR;
 433 }
 434
 435 \f
 436 /*** Misc. hash APIs ***/
 437
 438 svn_error_t *
 439 svn_hash_keys(apr_array_header_t **array,
 440               apr_hash_t *hash,
 441               apr_pool_t *pool)
 442 {
 443   apr_hash_index_t *hi;
 444
 445   *array = apr_array_make(pool, apr_hash_count(hash), sizeof(const char *));
 446
 447   for (hi = apr_hash_first(pool, hash); hi; hi = apr_hash_next(hi))
 448     {
 449       const void *key;
 450       const char *path;
 451
 452       apr_hash_this(hi, &key, NULL, NULL);
 453       path = key;
 454
 455       APR_ARRAY_PUSH(*array, const char *) = path;
 456     }
 457
 458   return SVN_NO_ERROR;
 459 }
 460
 461
 462 svn_error_t *
 463 svn_hash_from_cstring_keys(apr_hash_t **hash_p,
 464                            const apr_array_header_t *keys,
 465                            apr_pool_t *pool)
 466 {
 467   int i;
 468   apr_hash_t *hash = apr_hash_make(pool);
 469   for (i = 0; i < keys->nelts; i++)
 470     {
 471       const char *key =
 472         apr_pstrdup(pool, APR_ARRAY_IDX(keys, i, const char *));
 473       apr_hash_set(hash, key, APR_HASH_KEY_STRING, key);
 474     }
 475   *hash_p = hash;
 476   return SVN_NO_ERROR;
 477 }
 478
 479
 480 svn_error_t *
 481 svn_hash__clear(apr_hash_t *hash)
 482 {
 483 #if APR_VERSION_AT_LEAST(1, 3, 0)
 484   apr_hash_clear(hash);
 485 #else
 486   apr_hash_index_t *hi;
 487   const void *key;
 488   apr_ssize_t klen;
 489
 490   for (hi = apr_hash_first(NULL, hash); hi; hi = apr_hash_next(hi))
 491     {
 492       apr_hash_this(hi, &key, &klen, NULL);
 493       apr_hash_set(hash, key, klen, NULL);
 494     }
 495 #endif
 496   return SVN_NO_ERROR;
 497 }