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