src/TortoiseMerge/libsvn_diff/token.c

   1 /*
   2  * token.c :  routines for doing diffs
   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 #include <apr.h>
  21 #include <apr_pools.h>
  22 #include <apr_general.h>
  23
  24 #include "svn_version.h"
  25 #include "svn_io.h"
  26
  27 #include "svn_error.h"
  28 #include "svn_diff.h"
  29 #include "svn_types.h"
  30
  31 #include "diff.h"
  32
  33
  34 /*
  35  * Prime number to use as the size of the hash table.  This number was
  36  * not selected by testing of any kind and may need tweaking.
  37  */
  38 #define SVN_DIFF__HASH_SIZE 127
  39
  40 struct svn_diff__node_t
  41 {
  42   svn_diff__node_t     *parent;
  43   svn_diff__node_t     *left;
  44   svn_diff__node_t     *right;
  45
  46   apr_uint32_t          hash;
  47   void                 *token;
  48 };
  49
  50 struct svn_diff__tree_t
  51 {
  52   svn_diff__node_t     *root[SVN_DIFF__HASH_SIZE];
  53   apr_pool_t           *pool;
  54 };
  55
  56
  57 /*
  58  * Support functions to build a tree of token positions
  59  */
  60
  61 void
  62 svn_diff__tree_create(svn_diff__tree_t **tree, apr_pool_t *pool)
  63 {
  64   *tree = apr_pcalloc(pool, sizeof(**tree));
  65   (*tree)->pool = pool;
  66 }
  67
  68
  69 static svn_error_t *
  70 svn_diff__tree_insert_token(svn_diff__node_t **node, svn_diff__tree_t *tree,
  71                             void *diff_baton,
  72                             const svn_diff_fns_t *vtable,
  73                             apr_uint32_t hash, void *token)
  74 {
  75   svn_diff__node_t *new_node;
  76   svn_diff__node_t **node_ref;
  77   svn_diff__node_t *parent;
  78   int rv;
  79
  80   SVN_ERR_ASSERT(token);
  81
  82   parent = NULL;
  83   node_ref = &tree->root[hash % SVN_DIFF__HASH_SIZE];
  84
  85   while (*node_ref != NULL)
  86     {
  87       parent = *node_ref;
  88
  89       rv = hash - parent->hash;
  90       if (!rv)
  91         SVN_ERR(vtable->token_compare(diff_baton, parent->token, token, &rv));
  92
  93       if (rv == 0)
  94         {
  95           /* Discard the previous token.  This helps in cases where
  96            * only recently read tokens are still in memory.
  97            */
  98           if (vtable->token_discard != NULL)
  99             vtable->token_discard(diff_baton, parent->token);
 100
 101           parent->token = token;
 102           *node = parent;
 103
 104           return SVN_NO_ERROR;
 105         }
 106       else if (rv > 0)
 107         {
 108           node_ref = &parent->left;
 109         }
 110       else
 111         {
 112           node_ref = &parent->right;
 113         }
 114     }
 115
 116   /* Create a new node */
 117   new_node = apr_palloc(tree->pool, sizeof(*new_node));
 118   new_node->parent = parent;
 119   new_node->left = NULL;
 120   new_node->right = NULL;
 121   new_node->hash = hash;
 122   new_node->token = token;
 123
 124   *node = *node_ref = new_node;
 125
 126   return SVN_NO_ERROR;
 127 }
 128
 129
 130 /*
 131  * Get all tokens from a datasource.  Return the
 132  * last item in the (circular) list.
 133  */
 134 svn_error_t *
 135 svn_diff__get_tokens(svn_diff__position_t **position_list,
 136                      svn_diff__tree_t *tree,
 137                      void *diff_baton,
 138                      const svn_diff_fns_t *vtable,
 139                      svn_diff_datasource_e datasource,
 140                      apr_pool_t *pool)
 141 {
 142   svn_diff__position_t *start_position;
 143   svn_diff__position_t *position = NULL;
 144   svn_diff__position_t **position_ref;
 145   svn_diff__node_t *node;
 146   void *token;
 147   apr_off_t offset;
 148   apr_uint32_t hash;
 149
 150   *position_list = NULL;
 151
 152
 153   SVN_ERR(vtable->datasource_open(diff_baton, datasource));
 154
 155   position_ref = &start_position;
 156   offset = 0;
 157   hash = 0; /* The callback fn doesn't need to touch it per se */
 158   while (1)
 159     {
 160       SVN_ERR(vtable->datasource_get_next_token(&hash, &token,
 161                                                 diff_baton, datasource));
 162       if (token == NULL)
 163         break;
 164
 165       offset++;
 166       SVN_ERR(svn_diff__tree_insert_token(&node, tree,
 167                                           diff_baton, vtable,
 168                                           hash, token));
 169
 170       /* Create a new position */
 171       position = apr_palloc(pool, sizeof(*position));
 172       position->next = NULL;
 173       position->node = node;
 174       position->offset = offset;
 175
 176       *position_ref = position;
 177       position_ref = &position->next;
 178     }
 179
 180   *position_ref = start_position;
 181
 182   SVN_ERR(vtable->datasource_close(diff_baton, datasource));
 183
 184   *position_list = position;
 185
 186   return SVN_NO_ERROR;
 187 }