2 * token.c : routines for doing diffs
4 * ====================================================================
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
13 * http://www.apache.org/licenses/LICENSE-2.0
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
21 * ====================================================================
26 #include <apr_pools.h>
27 #include <apr_general.h>
29 #include "svn_error.h"
31 #include "svn_types.h"
37 * Prime number to use as the size of the hash table. This number was
38 * not selected by testing of any kind and may need tweaking.
40 #define SVN_DIFF__HASH_SIZE 127
42 struct svn_diff__node_t
44 svn_diff__node_t
*parent
;
45 svn_diff__node_t
*left
;
46 svn_diff__node_t
*right
;
49 svn_diff__token_index_t index
;
53 struct svn_diff__tree_t
55 svn_diff__node_t
*root
[SVN_DIFF__HASH_SIZE
];
57 svn_diff__token_index_t node_count
;
62 * Returns number of tokens in a tree
64 svn_diff__token_index_t
65 svn_diff__get_node_count(svn_diff__tree_t
*tree
)
67 return tree
->node_count
;
71 * Support functions to build a tree of token positions
75 svn_diff__tree_create(svn_diff__tree_t
**tree
, apr_pool_t
*pool
)
77 *tree
= apr_pcalloc(pool
, sizeof(**tree
));
79 (*tree
)->node_count
= 0;
84 tree_insert_token(svn_diff__node_t
**node
, svn_diff__tree_t
*tree
,
86 const svn_diff_fns2_t
*vtable
,
87 apr_uint32_t hash
, void *token
)
89 svn_diff__node_t
*new_node
;
90 svn_diff__node_t
**node_ref
;
91 svn_diff__node_t
*parent
;
94 SVN_ERR_ASSERT(token
);
97 node_ref
= &tree
->root
[hash
% SVN_DIFF__HASH_SIZE
];
99 while (*node_ref
!= NULL
)
103 rv
= hash
- parent
->hash
;
105 SVN_ERR(vtable
->token_compare(diff_baton
, parent
->token
, token
, &rv
));
109 /* Discard the previous token. This helps in cases where
110 * only recently read tokens are still in memory.
112 if (vtable
->token_discard
!= NULL
)
113 vtable
->token_discard(diff_baton
, parent
->token
);
115 parent
->token
= token
;
122 node_ref
= &parent
->left
;
126 node_ref
= &parent
->right
;
130 /* Create a new node */
131 new_node
= apr_palloc(tree
->pool
, sizeof(*new_node
));
132 new_node
->parent
= parent
;
133 new_node
->left
= NULL
;
134 new_node
->right
= NULL
;
135 new_node
->hash
= hash
;
136 new_node
->token
= token
;
137 new_node
->index
= tree
->node_count
++;
139 *node
= *node_ref
= new_node
;
146 * Get all tokens from a datasource. Return the
147 * last item in the (circular) list.
150 svn_diff__get_tokens(svn_diff__position_t
**position_list
,
151 svn_diff__tree_t
*tree
,
153 const svn_diff_fns2_t
*vtable
,
154 svn_diff_datasource_e datasource
,
155 apr_off_t prefix_lines
,
158 svn_diff__position_t
*start_position
;
159 svn_diff__position_t
*position
= NULL
;
160 svn_diff__position_t
**position_ref
;
161 svn_diff__node_t
*node
;
166 *position_list
= NULL
;
168 position_ref
= &start_position
;
169 offset
= prefix_lines
;
170 hash
= 0; /* The callback fn doesn't need to touch it per se */
173 SVN_ERR(vtable
->datasource_get_next_token(&hash
, &token
,
174 diff_baton
, datasource
));
179 SVN_ERR(tree_insert_token(&node
, tree
, diff_baton
, vtable
, hash
, token
));
181 /* Create a new position */
182 position
= apr_palloc(pool
, sizeof(*position
));
183 position
->next
= NULL
;
184 position
->token_index
= node
->index
;
185 position
->offset
= offset
;
187 *position_ref
= position
;
188 position_ref
= &position
->next
;
191 *position_ref
= start_position
;
193 SVN_ERR(vtable
->datasource_close(diff_baton
, datasource
));
195 *position_list
= position
;