← Back to branch summary

~ubuntu-branches/debian/sid/subversion/sid

« back to all changes in this revision

Viewing changes to subversion/libsvn_subr/hash.c

  • Committer: Package Import Robot
  • Author(s): James McCoy, Peter Samuelson, James McCoy
  • Date: 2014-01-12 19:48:33 UTC
  • mfrom: (0.2.10)
  • Revision ID: package-import@ubuntu.com-20140112194833-w3axfwksn296jn5x
Tags: 1.8.5-1
http://bugs.debian.org/725787
http://bugs.debian.org/507430
http://bugs.debian.org/734163
http://bugs.debian.org/601544
http://bugs.debian.org/687291
http://bugs.debian.org/273874
http://bugs.debian.org/690815
http://bugs.debian.org/654172
http://bugs.debian.org/678224
http://bugs.debian.org/566148
http://bugs.debian.org/734918
http://bugs.debian.org/722393
[ Peter Samuelson ]
* New upstream release.  (Closes: #725787) Rediff patches:
  - Remove apr-abi1 (applied upstream), rename apr-abi2 to apr-abi
  - Remove loosen-sqlite-version-check (shouldn't be needed)
  - Remove java-osgi-metadata (applied upstream)
  - svnmucc prompts for a changelog if none is provided. (Closes: #507430)
  - Remove fix-bdb-version-detection, upstream uses "apu-config --dbm-libs"
  - Remove ruby-test-wc (applied upstream)
  - Fix “svn diff -r N file” when file has svn:mime-type set.
    (Closes: #734163)
  - Support specifying an encoding for mod_dav_svn's environment in which
    hooks are run.  (Closes: #601544)
  - Fix ordering of “svnadmin dump” paths with certain APR versions.
    (Closes: #687291)
  - Provide a better error message when authentication fails with an
    svn+ssh:// URL.  (Closes: #273874)
  - Updated Polish translations.  (Closes: #690815)

[ James McCoy ]
* Remove all traces of libneon, replaced by libserf.
* patches/sqlite_3.8.x_workaround: Upstream fix for wc-queries-test test
  failurse.
* Run configure with --with-apache-libexecdir, which allows removing part of
  patches/rpath.
* Re-enable auth-test as upstream has fixed the problem of picking up
  libraries from the environment rather than the build tree.
  (Closes: #654172)
* Point LD_LIBRARY_PATH at the built auth libraries when running the svn
  command during the build.  (Closes: #678224)
* Add a NEWS entry describing how to configure mod_dav_svn to understand
  UTF-8.  (Closes: #566148)
* Remove ancient transitional package, libsvn-ruby.
* Enable compatibility with Sqlite3 versions back to Wheezy.
* Enable hardening flags.  (Closes: #734918)
* patches/build-fixes: Enable verbose build logs.
* Build against the default ruby version.  (Closes: #722393)

Show diffs side-by-side

added added

removed removed

Lines of Context:
subversion/libsvn_subr/hash.c
40
40
#include "svn_pools.h"
41
41
 
42
42
#include "private/svn_dep_compat.h"
 
43
#include "private/svn_subr_private.h"
43
44
 
44
45
#include "svn_private_config.h"
45
46
 
95
96
  svn_stringbuf_t *buf;
96
97
  svn_boolean_t eof;
97
98
  apr_size_t len, keylen, vallen;
98
 
  char c, *end, *keybuf, *valbuf;
 
99
  char c, *keybuf, *valbuf;
99
100
  apr_pool_t *iterpool = svn_pool_create(pool);
100
101
 
101
102
  while (1)
102
103
    {
 
104
      svn_error_t *err;
 
105
      apr_uint64_t ui64;
 
106
 
103
107
      svn_pool_clear(iterpool);
104
108
 
105
109
      /* Read a key length line.  Might be END, though. */
118
122
      if ((buf->len >= 3) && (buf->data[0] == 'K') && (buf->data[1] == ' '))
119
123
        {
120
124
          /* Get the length of the key */
121
 
          keylen = (size_t) strtoul(buf->data + 2, &end, 10);
122
 
          if (keylen == (size_t) ULONG_MAX || *end != '\0')
123
 
            return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL,
 
125
          err = svn_cstring_strtoui64(&ui64, buf->data + 2,
 
126
                                      0, APR_SIZE_MAX, 10);
 
127
          if (err)
 
128
            return svn_error_create(SVN_ERR_MALFORMED_FILE, err,
124
129
                                    _("Serialized hash malformed"));
 
130
          keylen = (apr_size_t)ui64;
125
131
 
126
132
          /* Now read that much into a buffer. */
127
133
          keybuf = apr_palloc(pool, keylen + 1);
140
146
 
141
147
          if ((buf->data[0] == 'V') && (buf->data[1] == ' '))
142
148
            {
143
 
              vallen = (size_t) strtoul(buf->data + 2, &end, 10);
144
 
              if (vallen == (size_t) ULONG_MAX || *end != '\0')
145
 
                return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL,
 
149
              err = svn_cstring_strtoui64(&ui64, buf->data + 2,
 
150
                                          0, APR_SIZE_MAX, 10);
 
151
              if (err)
 
152
                return svn_error_create(SVN_ERR_MALFORMED_FILE, err,
146
153
                                        _("Serialized hash malformed"));
 
154
              vallen = (apr_size_t)ui64;
147
155
 
148
156
              valbuf = apr_palloc(iterpool, vallen + 1);
149
157
              SVN_ERR(svn_stream_read(stream, valbuf, &vallen));
168
176
               && (buf->data[0] == 'D') && (buf->data[1] == ' '))
169
177
        {
170
178
          /* Get the length of the key */
171
 
          keylen = (size_t) strtoul(buf->data + 2, &end, 10);
172
 
          if (keylen == (size_t) ULONG_MAX || *end != '\0')
173
 
            return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL,
 
179
          err = svn_cstring_strtoui64(&ui64, buf->data + 2,
 
180
                                      0, APR_SIZE_MAX, 10);
 
181
          if (err)
 
182
            return svn_error_create(SVN_ERR_MALFORMED_FILE, err,
174
183
                                    _("Serialized hash malformed"));
 
184
          keylen = (apr_size_t)ui64;
175
185
 
176
186
          /* Now read that much into a buffer. */
177
187
          keybuf = apr_palloc(iterpool, keylen + 1);
229
239
            continue;
230
240
        }
231
241
 
 
242
      if (item->klen < 0)
 
243
        return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL,
 
244
                                _("Cannot serialize negative length"));
 
245
 
232
246
      /* Write it out. */
233
247
      SVN_ERR(svn_stream_printf(stream, subpool,
234
 
                                "K %" APR_SSIZE_T_FMT "\n%s\n"
 
248
                                "K %" APR_SIZE_T_FMT "\n%s\n"
235
249
                                "V %" APR_SIZE_T_FMT "\n",
236
 
                                item->klen, (const char *) item->key,
 
250
                                (apr_size_t) item->klen,
 
251
                                (const char *) item->key,
237
252
                                valstr->len));
238
253
      len = valstr->len;
239
254
      SVN_ERR(svn_stream_write(stream, valstr->data, &len));
240
 
      SVN_ERR(svn_stream_printf(stream, subpool, "\n"));
 
255
      SVN_ERR(svn_stream_puts(stream, "\n"));
241
256
    }
242
257
 
243
258
  if (oldhash)
495
510
                           apr_pool_t *pool)
496
511
{
497
512
  int i;
498
 
  apr_hash_t *hash = apr_hash_make(pool);
 
513
  apr_hash_t *hash = svn_hash__make(pool);
499
514
  for (i = 0; i < keys->nelts; i++)
500
515
    {
501
516
      const char *key =
502
517
        apr_pstrdup(pool, APR_ARRAY_IDX(keys, i, const char *));
503
 
      apr_hash_set(hash, key, APR_HASH_KEY_STRING, key);
 
518
      svn_hash_sets(hash, key, key);
504
519
    }
505
520
  *hash_p = hash;
506
521
  return SVN_NO_ERROR;
507
522
}
508
523
 
509
524
 
510
 
svn_error_t *
511
 
svn_hash__clear(apr_hash_t *hash, apr_pool_t *pool)
 
525
#if !APR_VERSION_AT_LEAST(1, 3, 0)
 
526
void
 
527
svn_hash__clear(apr_hash_t *hash)
512
528
{
513
 
#if APR_VERSION_AT_LEAST(1, 3, 0)
514
 
  apr_hash_clear(hash);
515
 
#else
516
529
  apr_hash_index_t *hi;
517
530
  const void *key;
518
531
  apr_ssize_t klen;
519
532
 
520
 
  for (hi = apr_hash_first(pool, hash); hi; hi = apr_hash_next(hi))
 
533
  for (hi = apr_hash_first(NULL, hash); hi; hi = apr_hash_next(hi))
521
534
    {
522
535
      apr_hash_this(hi, &key, &klen, NULL);
523
536
      apr_hash_set(hash, key, klen, NULL);
524
537
    }
 
538
}
525
539
#endif
526
 
  return SVN_NO_ERROR;
527
 
}
528
540
 
529
541
 
530
542
 
537
549
{
538
550
  if (hash)
539
551
    {
540
 
      const char *value = apr_hash_get(hash, key, APR_HASH_KEY_STRING);
 
552
      const char *value = svn_hash_gets(hash, key);
541
553
      return value ? value : default_value;
542
554
    }
543
555
 
560
572
  return default_value;
561
573
}
562
574
 
 
575
 
 
576
 
 
577
/*** Optimized hash function ***/
 
578
 
 
579
/* Optimized version of apr_hashfunc_default in APR 1.4.5 and earlier.
 
580
 * It assumes that the CPU has 32-bit multiplications with high throughput
 
581
 * of at least 1 operation every 3 cycles. Latency is not an issue. Another
 
582
 * optimization is a mildly unrolled main loop and breaking the dependency
 
583
 * chain within the loop.
 
584
 *
 
585
 * Note that most CPUs including Intel Atom, VIA Nano, ARM feature the
 
586
 * assumed pipelined multiplication circuitry. They can do one MUL every
 
587
 * or every other cycle.
 
588
 *
 
589
 * The performance is ultimately limited by the fact that most CPUs can
 
590
 * do only one LOAD and only one BRANCH operation per cycle. The best we
 
591
 * can do is to process one character per cycle - provided the processor
 
592
 * is wide enough to do 1 LOAD, COMPARE, BRANCH, MUL and ADD per cycle.
 
593
 */
 
594
static unsigned int
 
595
hashfunc_compatible(const char *char_key, apr_ssize_t *klen)
 
596
{
 
597
    unsigned int hash = 0;
 
598
    const unsigned char *key = (const unsigned char *)char_key;
 
599
    const unsigned char *p;
 
600
    apr_ssize_t i;
 
601
 
 
602
    if (*klen == APR_HASH_KEY_STRING)
 
603
      {
 
604
        for (p = key; ; p+=4)
 
605
          {
 
606
            unsigned int new_hash = hash * 33 * 33 * 33 * 33;
 
607
            if (!p[0]) break;
 
608
            new_hash += p[0] * 33 * 33 * 33;
 
609
            if (!p[1]) break;
 
610
            new_hash += p[1] * 33 * 33;
 
611
            if (!p[2]) break;
 
612
            new_hash += p[2] * 33;
 
613
            if (!p[3]) break;
 
614
            hash = new_hash + p[3];
 
615
          }
 
616
        for (; *p; p++)
 
617
            hash = hash * 33 + *p;
 
618
 
 
619
        *klen = p - key;
 
620
      }
 
621
    else
 
622
      {
 
623
        for (p = key, i = *klen; i >= 4; i-=4, p+=4)
 
624
          {
 
625
            hash = hash * 33 * 33 * 33 * 33
 
626
                 + p[0] * 33 * 33 * 33
 
627
                 + p[1] * 33 * 33
 
628
                 + p[2] * 33
 
629
                 + p[3];
 
630
          }
 
631
        for (; i; i--, p++)
 
632
            hash = hash * 33 + *p;
 
633
      }
 
634
 
 
635
    return hash;
 
636
}
 
637
 
 
638
apr_hash_t *
 
639
svn_hash__make(apr_pool_t *pool)
 
640
{
 
641
  return apr_hash_make_custom(pool, hashfunc_compatible);
 
642
}