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;