<commit_before>/*
 * vdelta.c:  vdelta generator.
 *
 * ====================================================================
 * Copyright (c) 2000-2001 CollabNet.  All rights reserved.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution.  The terms
 * are also available at http://subversion.tigris.org/license-1.html.
 * If newer versions of this license are posted there, you may use a
 * newer version instead, at your option.
 *
 * This software consists of voluntary contributions made by many
 * individuals.  For exact contribution history, see the revision
 * history and logs, available at http://subversion.tigris.org/.
 * ====================================================================
 */


#include <assert.h>

#include <apr_general.h>        /* for APR_INLINE */

#include "svn_delta.h"
#include "delta.h"



/* ==================================================================== */
/* Hash table for vdelta hashing.

   Each hash bucket is a chain of slots. The index of the slot in
   the slots array is also the index of the key string in the
   current window's data stream. The hash table implements a multimap
   (i.e., hash and key collisions are allowed).

   To store a key->index mapping, just add slot[index] to the slot
   chain tn key's bucket (see store_mapping).

   For a given key, you can traverse the list of match candidates (some
   of which may be hash collisions) like this:

   for (slot = buckets[get_bucket(key)]; slot != NULL; slot = slot->next)
     {
       index = slot - slots;
       ...
     }

  This hash table implementation os based on the description in
  http://subversion.tigris.org/subversion-dev/current/msg00152.html. */


/* Size of a vdelta hash key. */
#define VD_KEY_SIZE 4


/* Hash slot. */
typedef struct hash_slot_t {
  struct hash_slot_t *next;
} hash_slot_t;

/* Hash table. */
typedef struct hash_table_t {
  int num_buckets;              /* Number of buckets in the table. */
  hash_slot_t **buckets;        /* Bucket array. */
  hash_slot_t *slots;           /* Slots array. */
} hash_table_t;


/* Create a hash table with NUM_SLOTS slots. NUM_SLOTS should be the sum
   of the size of the source and target parts of the delta window.
   Allocate from POOL. */
static hash_table_t *
create_hash_table (apr_size_t num_slots, apr_pool_t *pool)
{
  int i;
  apr_size_t j;
  hash_table_t* table = apr_palloc (pool, sizeof (*table));

  /* This should be a reasonable number of buckets ... */
  table->num_buckets = (num_slots / 3) | 1;
  table->buckets = apr_palloc (pool, (table->num_buckets
                                      * sizeof (*table->buckets)));
  for (i = 0; i < table->num_buckets; ++i)
    table->buckets[i] = NULL;

  table->slots = apr_palloc (pool, num_slots * sizeof (*table->slots));
  for (j = 0; j < num_slots; ++j)
    table->slots[j].next = NULL;

  return table;
}


/* Convert a key to a pointer to the key's hash bucket.
   We use a 2-universal multiplicative hash function. If you're
   windering about the selected multiplier, take a look at the
   comments in apr/tables/apr_hash.c:find_entry for a discussion
   on fast string hashes; it's very illuminating.

   [ We use 127 instead of 33 here because I happen to like
     interesting prime numbers, so there. --xbc ] */
static APR_INLINE apr_uint32_t
get_bucket (const hash_table_t *table, const char *key)
{
  int i;
  apr_uint32_t hash = 0;
  for (i = 0; i < VD_KEY_SIZE; ++i)
    hash = hash * 127 + *key++;
  return hash % table->num_buckets;
}


/* Store a key->index mapping into the hash table. */
static APR_INLINE void
store_mapping (hash_table_t *table, const char* key, apr_off_t index)
{
  apr_uint32_t bucket = get_bucket (table, key);;
  assert (table->slots[index].next == NULL);
  table->slots[index].next = table->buckets[bucket];
  table->buckets[bucket] = &table->slots[index];
}




/* ==================================================================== */
/* Vdelta generator.

   The article "Delta Algorithms: An Empirical Analysis" by Hunt,
   <NAME> Tichy contains a description of the vdelta algorithm,
   but it's incomplete. Here's a detailed description (see also
   http://subversion.tigris.org/subversion-dev/current/msg00158.html
   in the mailing list archives):
   
     1. Look up the four bytes starting at the current position
        pointer.  If there are no matches for those four bytes,
        output an insert, move the position pointer forward by one,
        and go back to step 1.

     2. Determine which of the candidates yields the longest
        extension.  This will be called the "current match".

     3. Look up the last three bytes of the current match plus one
        unmatched byte.  If there is no match for those four bytes,
        the current match is the best match; go to step 6.

     4. For each candidate, check backwards to see if it matches
        the entire match so far.  If no candidates satisfy that
        constraint, the current match is the best match; go to step 6.

     5. Among the candidates which do satisfy the constraint,<commit_msg>* subversion/libsvn_delta/vdelta.c<commit_after>/*
 * vdelta.c:  vdelta generator.
 *
 * ====================================================================
 * Copyright (c) 2000-2001 CollabNet.  All rights reserved.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution.  The terms
 * are also available at http://subversion.tigris.org/license-1.html.
 * If newer versions of this license are posted there, you may use a
 * newer version instead, at your option.
 *
 * This software consists of voluntary contributions made by many
 * individuals.  For exact contribution history, see the revision
 * history and logs, available at http://subversion.tigris.org/.
 * ====================================================================
 */


#include <assert.h>

#include <apr_general.h>        /* for APR_INLINE */

#include "svn_delta.h"
#include "delta.h"



/* ==================================================================== */
/* Hash table for vdelta hashing.

   Each hash bucket is a chain of slots. The index of the slot in
   the slots array is also the index of the key string in the
   current window's data stream. The hash table implements a multimap
   (i.e., hash and key collisions are allowed).

   To store a key->index mapping, just add slot[index] to the slot
   chain tn key's bucket (see store_mapping).

   For a given key, you can traverse the list of match candidates (some
   of which may be hash collisions) like this:

   for (slot = buckets[get_bucket(key)]; slot != NULL; slot = slot->next)
     {
       index = slot - slots;
       ...
     }

  This hash table implementation os based on the description in
  http://subversion.tigris.org/subversion-dev/current/msg00152.html. */


/* Size of a vdelta hash key. */
#define VD_KEY_SIZE 4


/* Hash slot. */
typedef struct hash_slot_t {
  struct hash_slot_t *next;
} hash_slot_t;

/* Hash table. */
typedef struct hash_table_t {
  int num_buckets;              /* Number of buckets in the table. */
  hash_slot_t **buckets;        /* Bucket array. */
  hash_slot_t *slots;           /* Slots array. */
} hash_table_t;


/* Create a hash table with NUM_SLOTS slots. NUM_SLOTS should be the sum
   of the size of the source and target parts of the delta window.
   Allocate from POOL. */
static hash_table_t *
create_hash_table (apr_size_t num_slots, apr_pool_t *pool)
{
  int i;
  apr_size_t j;
  hash_table_t* table = apr_palloc (pool, sizeof (*table));

  /* This should be a reasonable number of buckets ... */
  table->num_buckets = (num_slots / 3) | 1;
  table->buckets = apr_palloc (pool, (table->num_buckets
                                      * sizeof (*table->buckets)));
  for (i = 0; i < table->num_buckets; ++i)
    table->buckets[i] = NULL;

  table->slots = apr_palloc (pool, num_slots * sizeof (*table->slots));
  for (j = 0; j < num_slots; ++j)
    table->slots[j].next = NULL;

  return table;
}


/* Convert a key to a pointer to the key's hash bucket.
   We use a 2-universal multiplicative hash function. If you're
   windering about the selected multiplier, take a look at the
   comments in apr/tables/apr_hash.c:find_entry for a discussion
   on fast string hashes; it's very illuminating.

   [ We use 127 instead of 33 here because I happen to like
     interesting prime numbers, so there. --xbc ] */
static APR_INLINE apr_uint32_t
get_bucket (const hash_table_t *table, const char *key)
{
  int i;
  apr_uint32_t hash = 0;
  for (i = 0; i < VD_KEY_SIZE; ++i)
    hash = hash * 127 + *key++;
  return hash % table->num_buckets;
}


/* Store a key->index mapping into the hash table. */
static APR_INLINE void
store_mapping (hash_table_t *table, const char* key, apr_off_t idx)
{
  apr_uint32_t bucket = get_bucket (table, key);;
  assert (table->slots[idx].next == NULL);
  table->slots[idx].next = table->buckets[bucket];
  table->buckets[bucket] = &table->slots[idx];
}




/* ==================================================================== */
/* Vdelta generator.

   The article "Delta Algorithms: An Empirical Analysis" by Hunt,
   Vo and Tichy contains a description of the vdelta algorithm,
   but it's incomplete. Here's a detailed description (see also
   http://subversion.tigris.org/subversion-dev/current/msg00158.html
   in the mailing list archives):
   
     1. Look up the four bytes starting at the current position
        pointer.  If there are no matches for those four bytes,
        output an insert, move the position pointer forward by one,
        and go back to step 1.

     2. Determine which of the candidates yields the longest
        extension.  This will be called the "current match".

     3. Look up the last three bytes of the current match plus one
        unmatched byte.  If there is no match for those four bytes,
        the current match is the best match; go to step 6.

     4. For each candidate, check backwards to see if it matches
        the entire match so far.  If no candidates satisfy that
        constraint, the current match is the best match; go to step 6.

     5. Among the candidates which do satisfy the constraint,
{'fraction_non_alphanumeric': 0.13883241359279697, 'fraction_numerical': 0.009487849743440798, 'mean_word_length': 3.178802588996764, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7037088', 'n_tokens_mistral': 3191, 'n_tokens_neox': 2952, 'n_words': 1223}