subversion/libsvn_fs_x/reps.c

34 /* Length of the text chunks we hash and match.  The algorithm will find
53 /* value of unused hash buckets */
116 /* Yet another hash data structure.  This one tries to be more cache
136   /* number of buckets in this hash, i.e. elements in each array above.
146   /* pool to use when growing the hash */
150 /* Hash key type. 32 bits for pseudo-Adler32 hash sums.
164   /* text block hash */
165   hash_t hash;
300 hash_to_index(hash_t *hash, hash_key_t adler32)
302   return (adler32 * 0xd1f3da69) >> hash->shift;
309 allocate_hash_members(hash_t *hash,
315   hash->pool = result_pool;
316   hash->size = size;
318   hash->prefixes = apr_pcalloc(result_pool, size);
319   hash->last_matches = apr_pcalloc(result_pool,
320                                    sizeof(*hash->last_matches) * size);
321   hash->offsets = apr_palloc(result_pool, sizeof(*hash->offsets) * size);
324     hash->offsets[i] = NO_OFFSET;
331 init_hash(hash_t *hash,
335   hash->used = 0;
336   hash->shift = sizeof(hash_key_t) * 8 - twoPower;
338   allocate_hash_members(hash, 1 << twoPower, result_pool);
345 grow_hash(hash_t *hash,
352   /* determine the new hash size */
353   apr_size_t new_size = hash->size * 2;
354   apr_size_t new_shift = hash->shift - 1;
361   /* allocate new hash */
362   allocate_hash_members(&copy, new_size, hash->pool);
367   for (i = 0; i < hash->size; ++i)
369       apr_uint32_t offset = hash->offsets[i];
378           copy.prefixes[idx] = hash->prefixes[i];
380           copy.last_matches[idx] = hash->last_matches[i];
384   *hash = copy;
396   init_hash(&result->hash, 4, result_pool);
458   /* expand the hash upfront to minimize the chances of collisions */
459   buckets_required = builder->hash.used + len / MATCH_BLOCKSIZE;
460   if (buckets_required * 3 >= builder->hash.size * 2)
461     grow_hash(&builder->hash, builder->text, 2 * buckets_required);
463   /* add hash entries for the new sequence */
469       size_t idx = hash_to_index(&builder->hash, key);
471       /* Don't replace hash entries that stem from the current text.
473       if (builder->hash.offsets[idx] == NO_OFFSET)
474         ++builder->hash.used;
475       else if (builder->hash.offsets[idx] >= instruction.offset)
478       builder->hash.offsets[idx] = (apr_uint32_t)offset;
479       builder->hash.prefixes[idx] = builder->text->data[offset];
514           idx = hash_to_index(&builder->hash, key);
515           if (builder->hash.prefixes[idx] == current[0])
517               offset = builder->hash.offsets[idx];