1/* 2 * token.c : routines for doing diffs 3 * 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 12 * 13 * http://www.apache.org/licenses/LICENSE-2.0 14 * 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 20 * under the License. 21 * ==================================================================== 22 */ 23 24 25#include <apr.h> 26#include <apr_pools.h> 27#include <apr_general.h> 28 29#include "svn_error.h" 30#include "svn_diff.h" 31#include "svn_types.h" 32 33#include "diff.h" 34 35 36/* 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. 39 */ 40#define SVN_DIFF__HASH_SIZE 127 41 42struct svn_diff__node_t 43{ 44 svn_diff__node_t *parent; 45 svn_diff__node_t *left; 46 svn_diff__node_t *right; 47 48 apr_uint32_t hash; 49 svn_diff__token_index_t index; 50 void *token; 51}; 52 53struct svn_diff__tree_t 54{ 55 svn_diff__node_t *root[SVN_DIFF__HASH_SIZE]; 56 apr_pool_t *pool; 57 svn_diff__token_index_t node_count; 58}; 59 60 61/* 62 * Returns number of tokens in a tree 63 */ 64svn_diff__token_index_t 65svn_diff__get_node_count(svn_diff__tree_t *tree) 66{ 67 return tree->node_count; 68} 69 70/* 71 * Support functions to build a tree of token positions 72 */ 73 74void 75svn_diff__tree_create(svn_diff__tree_t **tree, apr_pool_t *pool) 76{ 77 *tree = apr_pcalloc(pool, sizeof(**tree)); 78 (*tree)->pool = pool; 79 (*tree)->node_count = 0; 80} 81 82 83static svn_error_t * 84tree_insert_token(svn_diff__node_t **node, svn_diff__tree_t *tree, 85 void *diff_baton, 86 const svn_diff_fns2_t *vtable, 87 apr_uint32_t hash, void *token) 88{ 89 svn_diff__node_t *new_node; 90 svn_diff__node_t **node_ref; 91 svn_diff__node_t *parent; 92 int rv; 93 94 SVN_ERR_ASSERT(token); 95 96 parent = NULL; 97 node_ref = &tree->root[hash % SVN_DIFF__HASH_SIZE]; 98 99 while (*node_ref != NULL) 100 { 101 parent = *node_ref; 102 103 rv = hash - parent->hash; 104 if (!rv) 105 SVN_ERR(vtable->token_compare(diff_baton, parent->token, token, &rv)); 106 107 if (rv == 0) 108 { 109 /* Discard the previous token. This helps in cases where 110 * only recently read tokens are still in memory. 111 */ 112 if (vtable->token_discard != NULL) 113 vtable->token_discard(diff_baton, parent->token); 114 115 parent->token = token; 116 *node = parent; 117 118 return SVN_NO_ERROR; 119 } 120 else if (rv > 0) 121 { 122 node_ref = &parent->left; 123 } 124 else 125 { 126 node_ref = &parent->right; 127 } 128 } 129 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++; 138 139 *node = *node_ref = new_node; 140 141 return SVN_NO_ERROR; 142} 143 144 145/* 146 * Get all tokens from a datasource. Return the 147 * last item in the (circular) list. 148 */ 149svn_error_t * 150svn_diff__get_tokens(svn_diff__position_t **position_list, 151 svn_diff__tree_t *tree, 152 void *diff_baton, 153 const svn_diff_fns2_t *vtable, 154 svn_diff_datasource_e datasource, 155 apr_off_t prefix_lines, 156 apr_pool_t *pool) 157{ 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; 162 void *token; 163 apr_off_t offset; 164 apr_uint32_t hash; 165 166 *position_list = NULL; 167 168 position_ref = &start_position; 169 offset = prefix_lines; 170 hash = 0; /* The callback fn doesn't need to touch it per se */ 171 while (1) 172 { 173 SVN_ERR(vtable->datasource_get_next_token(&hash, &token, 174 diff_baton, datasource)); 175 if (token == NULL) 176 break; 177 178 offset++; 179 SVN_ERR(tree_insert_token(&node, tree, diff_baton, vtable, hash, token)); 180 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; 186 187 *position_ref = position; 188 position_ref = &position->next; 189 } 190 191 *position_ref = start_position; 192 193 SVN_ERR(vtable->datasource_close(diff_baton, datasource)); 194 195 *position_list = position; 196 197 return SVN_NO_ERROR; 198} 199