src/TortoiseMerge/libsvn_diff/token.c

   1 /*\r
   2  * token.c :  routines for doing diffs\r
   3  *\r
   4  * ====================================================================\r
   5  * Copyright (c) 2000-2004 CollabNet.  All rights reserved.\r
   6  *\r
   7  * This software is licensed as described in the file COPYING, which\r
   8  * you should have received as part of this distribution.  The terms\r
   9  * are also available at http://subversion.tigris.org/license-1.html.\r
  10  * If newer versions of this license are posted there, you may use a\r
  11  * newer version instead, at your option.\r
  12  *\r
  13  * This software consists of voluntary contributions made by many\r
  14  * individuals.  For exact contribution history, see the revision\r
  15  * history and logs, available at http://subversion.tigris.org/.\r
  16  * ====================================================================\r
  17  */\r
  18 \r
  19 \r
  20 #include <apr.h>\r
  21 #include <apr_pools.h>\r
  22 #include <apr_general.h>\r
  23 \r
  24 #include "svn_error.h"\r
  25 #include "svn_diff.h"\r
  26 #include "svn_types.h"\r
  27 \r
  28 #include "diff.h"\r
  29 \r
  30 \r
  31 /*\r
  32  * Prime number to use as the size of the hash table.  This number was\r
  33  * not selected by testing of any kind and may need tweaking.\r
  34  */\r
  35 #define SVN_DIFF__HASH_SIZE 127\r
  36 \r
  37 struct svn_diff__node_t\r
  38 {\r
  39   svn_diff__node_t     *parent;\r
  40   svn_diff__node_t     *left;\r
  41   svn_diff__node_t     *right;\r
  42 \r
  43   apr_uint32_t          hash;\r
  44   void                 *token;\r
  45 };\r
  46 \r
  47 struct svn_diff__tree_t\r
  48 {\r
  49   svn_diff__node_t     *root[SVN_DIFF__HASH_SIZE];\r
  50   apr_pool_t           *pool;\r
  51 };\r
  52 \r
  53 \r
  54 /*\r
  55  * Support functions to build a tree of token positions\r
  56  */\r
  57 \r
  58 void\r
  59 svn_diff__tree_create(svn_diff__tree_t **tree, apr_pool_t *pool)\r
  60 {\r
  61   *tree = apr_pcalloc(pool, sizeof(**tree));\r
  62   (*tree)->pool = pool;\r
  63 }\r
  64 \r
  65 \r
  66 static svn_error_t *\r
  67 svn_diff__tree_insert_token(svn_diff__node_t **node, svn_diff__tree_t *tree,\r
  68                             void *diff_baton,\r
  69                             const svn_diff_fns_t *vtable,\r
  70                             apr_uint32_t hash, void *token)\r
  71 {\r
  72   svn_diff__node_t *new_node;\r
  73   svn_diff__node_t **node_ref;\r
  74   svn_diff__node_t *parent;\r
  75   int rv;\r
  76 \r
  77   SVN_ERR_ASSERT(token);\r
  78 \r
  79   parent = NULL;\r
  80   node_ref = &tree->root[hash % SVN_DIFF__HASH_SIZE];\r
  81 \r
  82   while (*node_ref != NULL)\r
  83     {\r
  84       parent = *node_ref;\r
  85 \r
  86       rv = hash - parent->hash;\r
  87       if (!rv)\r
  88         SVN_ERR(vtable->token_compare(diff_baton, parent->token, token, &rv));\r
  89 \r
  90       if (rv == 0)\r
  91         {\r
  92           /* Discard the previous token.  This helps in cases where\r
  93            * only recently read tokens are still in memory.\r
  94            */\r
  95           if (vtable->token_discard != NULL)\r
  96             vtable->token_discard(diff_baton, parent->token);\r
  97 \r
  98           parent->token = token;\r
  99           *node = parent;\r
 100 \r
 101           return SVN_NO_ERROR;\r
 102         }\r
 103       else if (rv > 0)\r
 104         {\r
 105           node_ref = &parent->left;\r
 106         }\r
 107       else\r
 108         {\r
 109           node_ref = &parent->right;\r
 110         }\r
 111     }\r
 112 \r
 113   /* Create a new node */\r
 114   new_node = apr_palloc(tree->pool, sizeof(*new_node));\r
 115   new_node->parent = parent;\r
 116   new_node->left = NULL;\r
 117   new_node->right = NULL;\r
 118   new_node->hash = hash;\r
 119   new_node->token = token;\r
 120 \r
 121   *node = *node_ref = new_node;\r
 122 \r
 123   return SVN_NO_ERROR;\r
 124 }\r
 125 \r
 126 \r
 127 /*\r
 128  * Get all tokens from a datasource.  Return the\r
 129  * last item in the (circular) list.\r
 130  */\r
 131 svn_error_t *\r
 132 svn_diff__get_tokens(svn_diff__position_t **position_list,\r
 133                      svn_diff__tree_t *tree,\r
 134                      void *diff_baton,\r
 135                      const svn_diff_fns_t *vtable,\r
 136                      svn_diff_datasource_e datasource,\r
 137                      apr_pool_t *pool)\r
 138 {\r
 139   svn_diff__position_t *start_position;\r
 140   svn_diff__position_t *position = NULL;\r
 141   svn_diff__position_t **position_ref;\r
 142   svn_diff__node_t *node;\r
 143   void *token;\r
 144   apr_off_t offset;\r
 145   apr_uint32_t hash;\r
 146 \r
 147   *position_list = NULL;\r
 148 \r
 149 \r
 150   SVN_ERR(vtable->datasource_open(diff_baton, datasource));\r
 151 \r
 152   position_ref = &start_position;\r
 153   offset = 0;\r
 154   hash = 0; /* The callback fn doesn't need to touch it per se */\r
 155   while (1)\r
 156     {\r
 157       SVN_ERR(vtable->datasource_get_next_token(&hash, &token,\r
 158                                                 diff_baton, datasource));\r
 159       if (token == NULL)\r
 160         break;\r
 161 \r
 162       offset++;\r
 163       SVN_ERR(svn_diff__tree_insert_token(&node, tree,\r
 164                                           diff_baton, vtable,\r
 165                                           hash, token));\r
 166 \r
 167       /* Create a new position */\r
 168       position = apr_palloc(pool, sizeof(*position));\r
 169       position->next = NULL;\r
 170       position->node = node;\r
 171       position->offset = offset;\r
 172 \r
 173       *position_ref = position;\r
 174       position_ref = &position->next;\r
 175     }\r
 176 \r
 177   *position_ref = start_position;\r
 178 \r
 179   SVN_ERR(vtable->datasource_close(diff_baton, datasource));\r
 180 \r
 181   *position_list = position;\r
 182 \r
 183   return SVN_NO_ERROR;\r
 184 }\r