OSDN Git Service

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