1 /* id.c : operations on node-revision IDs
3 * ====================================================================
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
12 * http://www.apache.org/licenses/LICENSE-2.0
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
20 * ====================================================================
29 #include "../libsvn_fs/fs-loader.h"
30 #include "private/svn_temp_serializer.h"
31 #include "private/svn_string_private.h"
34 typedef struct fs_fs__id_t
36 /* API visible part */
37 svn_fs_id_t generic_id;
42 svn_fs_fs__id_part_t node_id;
43 svn_fs_fs__id_part_t copy_id;
44 svn_fs_fs__id_part_t txn_id;
45 svn_fs_fs__id_part_t rev_item;
51 /** Like strtol but with a fixed base of 10, locale independent and limited
52 * to non-negative values. Overflows are indicated by a FALSE return value
53 * in which case *RESULT_P will not be modified.
55 * This allows the compiler to generate massively faster code.
56 * (E.g. Avoiding locale specific processing). ID parsing is one of the
57 * most CPU consuming parts of FSFS data access. Better be quick.
60 locale_independent_strtol(long *result_p,
64 /* We allow positive values only. We use unsigned arithmetics to get
65 * well-defined overflow behavior. It also happens to allow for a wider
66 * range of compiler-side optimizations. */
67 unsigned long result = 0;
70 unsigned long c = (unsigned char)*buffer - (unsigned char)'0';
73 /* This implies the NUL check. */
77 /* Overflow check. Passing this, NEXT can be no more than ULONG_MAX+9
78 * before being truncated to ULONG but it still covers 0 .. ULONG_MAX.
80 if (result > ULONG_MAX / 10)
83 next = result * 10 + c;
85 /* Overflow check. In case of an overflow, NEXT is 0..9.
86 * In the non-overflow case, RESULT is either >= 10 or RESULT and NEXT
96 if (result > LONG_MAX)
99 *result_p = (long)result;
104 /* Parse the NUL-terminated ID part at DATA and write the result into *PART.
105 * Return TRUE if no errors were detected. */
107 part_parse(svn_fs_fs__id_part_t *part,
112 /* special case: ID inside some transaction */
115 part->revision = SVN_INVALID_REVNUM;
116 part->number = svn__base36toui64(&data, data + 1);
117 return *data == '\0';
120 /* special case: 0 / default ID */
121 if (data[0] == '0' && data[1] == '\0')
128 /* read old style / new style ID */
129 part->number = svn__base36toui64(&data, data);
133 return *data == '\0';
136 return locale_independent_strtol(&part->revision, data+1, &end);
139 /* Parse the transaction id in DATA and store the result in *TXN_ID.
140 * Return FALSE if there was some problem.
143 txn_id_parse(svn_fs_fs__id_part_t *txn_id,
147 if (!locale_independent_strtol(&txn_id->revision, data, &end))
155 txn_id->number = svn__base36toui64(&data, data);
156 return *data == '\0';
159 /* Write the textual representation of *PART into P and return a pointer
160 * to the first position behind that string.
163 unparse_id_part(char *p,
164 const svn_fs_fs__id_part_t *part)
166 if (SVN_IS_VALID_REVNUM(part->revision))
168 /* ordinary old style / new style ID */
169 p += svn__ui64tobase36(p, part->number);
170 if (part->revision > 0)
173 p += svn__i64toa(p, part->revision);
178 /* in txn: mark with "_" prefix */
180 p += svn__ui64tobase36(p, part->number);
190 /* Operations on ID parts */
193 svn_fs_fs__id_part_is_root(const svn_fs_fs__id_part_t* part)
195 return part->revision == 0 && part->number == 0;
199 svn_fs_fs__id_part_eq(const svn_fs_fs__id_part_t *lhs,
200 const svn_fs_fs__id_part_t *rhs)
202 return lhs->revision == rhs->revision && lhs->number == rhs->number;
206 svn_fs_fs__id_txn_used(const svn_fs_fs__id_part_t *txn_id)
208 return SVN_IS_VALID_REVNUM(txn_id->revision) || (txn_id->number != 0);
212 svn_fs_fs__id_txn_reset(svn_fs_fs__id_part_t *txn_id)
214 txn_id->revision = SVN_INVALID_REVNUM;
219 svn_fs_fs__id_txn_parse(svn_fs_fs__id_part_t *txn_id,
222 if (! txn_id_parse(txn_id, data))
223 return svn_error_createf(SVN_ERR_FS_MALFORMED_TXN_ID, NULL,
224 "malformed txn id '%s'", data);
230 svn_fs_fs__id_txn_unparse(const svn_fs_fs__id_part_t *txn_id,
233 char string[2 * SVN_INT64_BUFFER_SIZE + 1];
236 p += svn__i64toa(p, txn_id->revision);
238 p += svn__ui64tobase36(p, txn_id->number);
240 return apr_pstrmemdup(pool, string, p - string);
245 /* Accessing ID Pieces. */
247 const svn_fs_fs__id_part_t *
248 svn_fs_fs__id_node_id(const svn_fs_id_t *fs_id)
250 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
252 return &id->private_id.node_id;
256 const svn_fs_fs__id_part_t *
257 svn_fs_fs__id_copy_id(const svn_fs_id_t *fs_id)
259 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
261 return &id->private_id.copy_id;
265 const svn_fs_fs__id_part_t *
266 svn_fs_fs__id_txn_id(const svn_fs_id_t *fs_id)
268 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
270 return &id->private_id.txn_id;
274 const svn_fs_fs__id_part_t *
275 svn_fs_fs__id_rev_item(const svn_fs_id_t *fs_id)
277 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
279 return &id->private_id.rev_item;
283 svn_fs_fs__id_rev(const svn_fs_id_t *fs_id)
285 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
287 return id->private_id.rev_item.revision;
291 svn_fs_fs__id_item(const svn_fs_id_t *fs_id)
293 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
295 return id->private_id.rev_item.number;
299 svn_fs_fs__id_is_txn(const svn_fs_id_t *fs_id)
301 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
303 return svn_fs_fs__id_txn_used(&id->private_id.txn_id);
307 svn_fs_fs__id_unparse(const svn_fs_id_t *fs_id,
310 char string[6 * SVN_INT64_BUFFER_SIZE + 10];
311 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
313 char *p = unparse_id_part(string, &id->private_id.node_id);
314 p = unparse_id_part(p, &id->private_id.copy_id);
316 if (svn_fs_fs__id_txn_used(&id->private_id.txn_id))
319 p += svn__i64toa(p, id->private_id.txn_id.revision);
321 p += svn__ui64tobase36(p, id->private_id.txn_id.number);
326 p += svn__i64toa(p, id->private_id.rev_item.revision);
328 p += svn__i64toa(p, id->private_id.rev_item.number);
331 return svn_string_ncreate(string, p - string, pool);
335 /*** Comparing node IDs ***/
338 svn_fs_fs__id_eq(const svn_fs_id_t *a,
339 const svn_fs_id_t *b)
341 const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
342 const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
347 return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
348 &id_b->private_id.node_id)
349 && svn_fs_fs__id_part_eq(&id_a->private_id.copy_id,
350 &id_b->private_id.copy_id)
351 && svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
352 &id_b->private_id.txn_id)
353 && svn_fs_fs__id_part_eq(&id_a->private_id.rev_item,
354 &id_b->private_id.rev_item);
359 svn_fs_fs__id_check_related(const svn_fs_id_t *a,
360 const svn_fs_id_t *b)
362 const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
363 const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
368 /* If both node_ids have been created within _different_ transactions
369 (and are still uncommitted), then it is impossible for them to be
372 Due to our txn-local temporary IDs, however, they might have been
373 given the same temporary node ID. We need to detect that case.
375 if ( id_a->private_id.node_id.revision == SVN_INVALID_REVNUM
376 && id_b->private_id.node_id.revision == SVN_INVALID_REVNUM)
378 if (!svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
379 &id_b->private_id.txn_id))
382 /* At this point, matching node_ids implies relatedness. */
385 return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
386 &id_b->private_id.node_id);
390 svn_fs_node_relation_t
391 svn_fs_fs__id_compare(const svn_fs_id_t *a,
392 const svn_fs_id_t *b)
394 if (svn_fs_fs__id_eq(a, b))
395 return svn_fs_node_unchanged;
396 return (svn_fs_fs__id_check_related(a, b) ? svn_fs_node_common_ancestor
397 : svn_fs_node_unrelated);
401 svn_fs_fs__id_part_compare(const svn_fs_fs__id_part_t *a,
402 const svn_fs_fs__id_part_t *b)
404 if (a->revision < b->revision)
406 if (a->revision > b->revision)
409 return a->number < b->number ? -1 : a->number == b->number ? 0 : 1;
416 static id_vtable_t id_vtable = {
417 svn_fs_fs__id_unparse,
418 svn_fs_fs__id_compare
422 svn_fs_fs__id_txn_create_root(const svn_fs_fs__id_part_t *txn_id,
425 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
427 /* node ID and copy ID are "0" */
429 id->private_id.txn_id = *txn_id;
430 id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
432 id->generic_id.vtable = &id_vtable;
433 id->generic_id.fsap_data = id;
435 return (svn_fs_id_t *)id;
438 svn_fs_id_t *svn_fs_fs__id_create_root(const svn_revnum_t revision,
441 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
443 id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
444 id->private_id.rev_item.revision = revision;
445 id->private_id.rev_item.number = SVN_FS_FS__ITEM_INDEX_ROOT_NODE;
447 id->generic_id.vtable = &id_vtable;
448 id->generic_id.fsap_data = id;
450 return (svn_fs_id_t *)id;
454 svn_fs_fs__id_txn_create(const svn_fs_fs__id_part_t *node_id,
455 const svn_fs_fs__id_part_t *copy_id,
456 const svn_fs_fs__id_part_t *txn_id,
459 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
461 id->private_id.node_id = *node_id;
462 id->private_id.copy_id = *copy_id;
463 id->private_id.txn_id = *txn_id;
464 id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
466 id->generic_id.vtable = &id_vtable;
467 id->generic_id.fsap_data = id;
469 return (svn_fs_id_t *)id;
474 svn_fs_fs__id_rev_create(const svn_fs_fs__id_part_t *node_id,
475 const svn_fs_fs__id_part_t *copy_id,
476 const svn_fs_fs__id_part_t *rev_item,
479 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
481 id->private_id.node_id = *node_id;
482 id->private_id.copy_id = *copy_id;
483 id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
484 id->private_id.rev_item = *rev_item;
486 id->generic_id.vtable = &id_vtable;
487 id->generic_id.fsap_data = id;
489 return (svn_fs_id_t *)id;
494 svn_fs_fs__id_copy(const svn_fs_id_t *source, apr_pool_t *pool)
496 const fs_fs__id_t *id = (const fs_fs__id_t *)source;
497 fs_fs__id_t *new_id = apr_pmemdup(pool, id, sizeof(*new_id));
499 new_id->generic_id.fsap_data = new_id;
501 return (svn_fs_id_t *)new_id;
504 /* Return an ID resulting from parsing the string DATA, or NULL if DATA is
505 an invalid ID string. *DATA will be modified / invalidated by this call. */
513 /* Alloc a new svn_fs_id_t structure. */
514 id = apr_pcalloc(pool, sizeof(*id));
515 id->generic_id.vtable = &id_vtable;
516 id->generic_id.fsap_data = id;
518 /* Now, we basically just need to "split" this data on `.'
519 characters. We will use svn_cstring_tokenize, which will put
520 terminators where each of the '.'s used to be. Then our new
521 id field will reference string locations inside our duplicate
525 str = svn_cstring_tokenize(".", &data);
528 if (! part_parse(&id->private_id.node_id, str))
532 str = svn_cstring_tokenize(".", &data);
535 if (! part_parse(&id->private_id.copy_id, str))
539 str = svn_cstring_tokenize(".", &data);
549 /* This is a revision type ID */
550 id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
551 id->private_id.txn_id.number = 0;
554 str = svn_cstring_tokenize("/", &data);
557 if (!locale_independent_strtol(&id->private_id.rev_item.revision,
561 err = svn_cstring_atoi64(&val, data);
564 svn_error_clear(err);
567 id->private_id.rev_item.number = (apr_uint64_t)val;
569 else if (str[0] == 't')
571 /* This is a transaction type ID */
572 id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
573 id->private_id.rev_item.number = 0;
575 if (! txn_id_parse(&id->private_id.txn_id, str + 1))
581 return (svn_fs_id_t *)id;
585 svn_fs_fs__id_parse(const svn_fs_id_t **id_p,
589 svn_fs_id_t *id = id_parse(data, pool);
591 return svn_error_createf(SVN_ERR_FS_MALFORMED_NODEREV_ID, NULL,
592 "Malformed node revision ID string");
599 /* (de-)serialization support */
601 /* Serialize an ID within the serialization CONTEXT.
604 svn_fs_fs__id_serialize(svn_temp_serializer__context_t *context,
605 const svn_fs_id_t * const *in)
607 const fs_fs__id_t *id = (const fs_fs__id_t *)*in;
609 /* nothing to do for NULL ids */
613 /* serialize the id data struct itself */
614 svn_temp_serializer__add_leaf(context,
615 (const void * const *)in,
616 sizeof(fs_fs__id_t));
619 /* Deserialize an ID inside the BUFFER.
622 svn_fs_fs__id_deserialize(void *buffer, svn_fs_id_t **in_out)
626 /* The id maybe all what is in the whole buffer.
627 * Don't try to fixup the pointer in that case*/
628 if (*in_out != buffer)
629 svn_temp_deserializer__resolve(buffer, (void**)in_out);
631 id = (fs_fs__id_t *)*in_out;
633 /* no id, no sub-structure fixup necessary */
637 /* the stored vtable is bogus at best -> set the right one */
638 id->generic_id.vtable = &id_vtable;
639 id->generic_id.fsap_data = id;