2 * token.c : routines for doing diffs
\r
4 * ====================================================================
\r
5 * Copyright (c) 2000-2004 CollabNet. All rights reserved.
\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
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
21 #include <apr_pools.h>
\r
22 #include <apr_general.h>
\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
31 #define SVN_DIFF__HASH_SIZE 127
\r
33 struct svn_diff__node_t
\r
35 svn_diff__node_t *parent;
\r
36 svn_diff__node_t *left;
\r
37 svn_diff__node_t *right;
\r
43 struct svn_diff__tree_t
\r
45 svn_diff__node_t *root[SVN_DIFF__HASH_SIZE];
\r
51 * Support functions to build a tree of token positions
\r
55 svn_diff__tree_create(svn_diff__tree_t **tree, apr_pool_t *pool)
\r
57 *tree = apr_pcalloc(pool, sizeof(**tree));
\r
58 (*tree)->pool = pool;
\r
62 static svn_error_t *
\r
63 svn_diff__tree_insert_token(svn_diff__node_t **node, svn_diff__tree_t *tree,
\r
65 const svn_diff_fns_t *vtable,
\r
66 apr_uint32_t hash, void *token)
\r
68 svn_diff__node_t *new_node;
\r
69 svn_diff__node_t **node_ref;
\r
70 svn_diff__node_t *parent;
\r
73 SVN_ERR_ASSERT(token);
\r
76 node_ref = &tree->root[hash % SVN_DIFF__HASH_SIZE];
\r
78 while (*node_ref != NULL)
\r
82 rv = hash - parent->hash;
\r
84 SVN_ERR(vtable->token_compare(diff_baton, parent->token, token, &rv));
\r
88 /* Discard the previous token. This helps in cases where
\r
89 * only recently read tokens are still in memory.
\r
91 if (vtable->token_discard != NULL)
\r
92 vtable->token_discard(diff_baton, parent->token);
\r
94 parent->token = token;
\r
97 return SVN_NO_ERROR;
\r
101 node_ref = &parent->left;
\r
105 node_ref = &parent->right;
\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
117 *node = *node_ref = new_node;
\r
119 return SVN_NO_ERROR;
\r
124 * Get all tokens from a datasource. Return the
\r
125 * last item in the (circular) list.
\r
128 svn_diff__get_tokens(svn_diff__position_t **position_list,
\r
129 svn_diff__tree_t *tree,
\r
131 const svn_diff_fns_t *vtable,
\r
132 svn_diff_datasource_e datasource,
\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
143 *position_list = NULL;
\r
146 SVN_ERR(vtable->datasource_open(diff_baton, datasource));
\r
148 position_ref = &start_position;
\r
150 hash = 0; /* The callback fn doesn't need to touch it per se */
\r
153 SVN_ERR(vtable->datasource_get_next_token(&hash, &token,
\r
154 diff_baton, datasource));
\r
159 SVN_ERR(svn_diff__tree_insert_token(&node, tree,
\r
160 diff_baton, vtable,
\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
169 *position_ref = position;
\r
170 position_ref = &position->next;
\r
173 *position_ref = start_position;
\r
175 SVN_ERR(vtable->datasource_close(diff_baton, datasource));
\r
177 *position_list = position;
\r
179 return SVN_NO_ERROR;
\r