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 and RESULT
86 * is much larger than 10. We will then return FALSE.
88 * In the non-overflow case, NEXT is >= 10 * RESULT but never smaller.
89 * We will continue the loop in that case. */
98 if (result > LONG_MAX)
101 *result_p = (long)result;
106 /* Parse the NUL-terminated ID part at DATA and write the result into *PART.
107 * Return TRUE if no errors were detected. */
109 part_parse(svn_fs_fs__id_part_t *part,
114 /* special case: ID inside some transaction */
117 part->revision = SVN_INVALID_REVNUM;
118 part->number = svn__base36toui64(&data, data + 1);
119 return *data == '\0';
122 /* special case: 0 / default ID */
123 if (data[0] == '0' && data[1] == '\0')
130 /* read old style / new style ID */
131 part->number = svn__base36toui64(&data, data);
135 return *data == '\0';
138 return locale_independent_strtol(&part->revision, data+1, &end);
141 /* Parse the transaction id in DATA and store the result in *TXN_ID.
142 * Return FALSE if there was some problem.
145 txn_id_parse(svn_fs_fs__id_part_t *txn_id,
149 if (!locale_independent_strtol(&txn_id->revision, data, &end))
157 txn_id->number = svn__base36toui64(&data, data);
158 return *data == '\0';
161 /* Write the textual representation of *PART into P and return a pointer
162 * to the first position behind that string.
165 unparse_id_part(char *p,
166 const svn_fs_fs__id_part_t *part)
168 if (SVN_IS_VALID_REVNUM(part->revision))
170 /* ordinary old style / new style ID */
171 p += svn__ui64tobase36(p, part->number);
172 if (part->revision > 0)
175 p += svn__i64toa(p, part->revision);
180 /* in txn: mark with "_" prefix */
182 p += svn__ui64tobase36(p, part->number);
192 /* Operations on ID parts */
195 svn_fs_fs__id_part_is_root(const svn_fs_fs__id_part_t* part)
197 return part->revision == 0 && part->number == 0;
201 svn_fs_fs__id_part_eq(const svn_fs_fs__id_part_t *lhs,
202 const svn_fs_fs__id_part_t *rhs)
204 return lhs->revision == rhs->revision && lhs->number == rhs->number;
208 svn_fs_fs__id_txn_used(const svn_fs_fs__id_part_t *txn_id)
210 return SVN_IS_VALID_REVNUM(txn_id->revision) || (txn_id->number != 0);
214 svn_fs_fs__id_txn_reset(svn_fs_fs__id_part_t *txn_id)
216 txn_id->revision = SVN_INVALID_REVNUM;
221 svn_fs_fs__id_txn_parse(svn_fs_fs__id_part_t *txn_id,
224 if (! txn_id_parse(txn_id, data))
225 return svn_error_createf(SVN_ERR_FS_MALFORMED_TXN_ID, NULL,
226 "malformed txn id '%s'", data);
232 svn_fs_fs__id_txn_unparse(const svn_fs_fs__id_part_t *txn_id,
235 char string[2 * SVN_INT64_BUFFER_SIZE + 1];
238 p += svn__i64toa(p, txn_id->revision);
240 p += svn__ui64tobase36(p, txn_id->number);
242 return apr_pstrmemdup(pool, string, p - string);
247 /* Accessing ID Pieces. */
249 const svn_fs_fs__id_part_t *
250 svn_fs_fs__id_node_id(const svn_fs_id_t *fs_id)
252 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
254 return &id->private_id.node_id;
258 const svn_fs_fs__id_part_t *
259 svn_fs_fs__id_copy_id(const svn_fs_id_t *fs_id)
261 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
263 return &id->private_id.copy_id;
267 const svn_fs_fs__id_part_t *
268 svn_fs_fs__id_txn_id(const svn_fs_id_t *fs_id)
270 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
272 return &id->private_id.txn_id;
276 const svn_fs_fs__id_part_t *
277 svn_fs_fs__id_rev_item(const svn_fs_id_t *fs_id)
279 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
281 return &id->private_id.rev_item;
285 svn_fs_fs__id_rev(const svn_fs_id_t *fs_id)
287 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
289 return id->private_id.rev_item.revision;
293 svn_fs_fs__id_item(const svn_fs_id_t *fs_id)
295 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
297 return id->private_id.rev_item.number;
301 svn_fs_fs__id_is_txn(const svn_fs_id_t *fs_id)
303 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
305 return svn_fs_fs__id_txn_used(&id->private_id.txn_id);
309 svn_fs_fs__id_unparse(const svn_fs_id_t *fs_id,
312 char string[6 * SVN_INT64_BUFFER_SIZE + 10];
313 const fs_fs__id_t *id = (const fs_fs__id_t *)fs_id;
315 char *p = unparse_id_part(string, &id->private_id.node_id);
316 p = unparse_id_part(p, &id->private_id.copy_id);
318 if (svn_fs_fs__id_txn_used(&id->private_id.txn_id))
321 p += svn__i64toa(p, id->private_id.txn_id.revision);
323 p += svn__ui64tobase36(p, id->private_id.txn_id.number);
328 p += svn__i64toa(p, id->private_id.rev_item.revision);
330 p += svn__i64toa(p, id->private_id.rev_item.number);
333 return svn_string_ncreate(string, p - string, pool);
337 /*** Comparing node IDs ***/
340 svn_fs_fs__id_eq(const svn_fs_id_t *a,
341 const svn_fs_id_t *b)
343 const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
344 const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
349 return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
350 &id_b->private_id.node_id)
351 && svn_fs_fs__id_part_eq(&id_a->private_id.copy_id,
352 &id_b->private_id.copy_id)
353 && svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
354 &id_b->private_id.txn_id)
355 && svn_fs_fs__id_part_eq(&id_a->private_id.rev_item,
356 &id_b->private_id.rev_item);
361 svn_fs_fs__id_check_related(const svn_fs_id_t *a,
362 const svn_fs_id_t *b)
364 const fs_fs__id_t *id_a = (const fs_fs__id_t *)a;
365 const fs_fs__id_t *id_b = (const fs_fs__id_t *)b;
370 /* If both node_ids have been created within _different_ transactions
371 (and are still uncommitted), then it is impossible for them to be
374 Due to our txn-local temporary IDs, however, they might have been
375 given the same temporary node ID. We need to detect that case.
377 if ( id_a->private_id.node_id.revision == SVN_INVALID_REVNUM
378 && id_b->private_id.node_id.revision == SVN_INVALID_REVNUM)
380 if (!svn_fs_fs__id_part_eq(&id_a->private_id.txn_id,
381 &id_b->private_id.txn_id))
384 /* At this point, matching node_ids implies relatedness. */
387 return svn_fs_fs__id_part_eq(&id_a->private_id.node_id,
388 &id_b->private_id.node_id);
392 svn_fs_node_relation_t
393 svn_fs_fs__id_compare(const svn_fs_id_t *a,
394 const svn_fs_id_t *b)
396 if (svn_fs_fs__id_eq(a, b))
397 return svn_fs_node_unchanged;
398 return (svn_fs_fs__id_check_related(a, b) ? svn_fs_node_common_ancestor
399 : svn_fs_node_unrelated);
403 svn_fs_fs__id_part_compare(const svn_fs_fs__id_part_t *a,
404 const svn_fs_fs__id_part_t *b)
406 if (a->revision < b->revision)
408 if (a->revision > b->revision)
411 return a->number < b->number ? -1 : a->number == b->number ? 0 : 1;
418 static id_vtable_t id_vtable = {
419 svn_fs_fs__id_unparse,
420 svn_fs_fs__id_compare
424 svn_fs_fs__id_txn_create_root(const svn_fs_fs__id_part_t *txn_id,
427 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
429 /* node ID and copy ID are "0" */
431 id->private_id.txn_id = *txn_id;
432 id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
434 id->generic_id.vtable = &id_vtable;
435 id->generic_id.fsap_data = id;
437 return (svn_fs_id_t *)id;
440 svn_fs_id_t *svn_fs_fs__id_create_root(const svn_revnum_t revision,
443 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
445 id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
446 id->private_id.rev_item.revision = revision;
447 id->private_id.rev_item.number = SVN_FS_FS__ITEM_INDEX_ROOT_NODE;
449 id->generic_id.vtable = &id_vtable;
450 id->generic_id.fsap_data = id;
452 return (svn_fs_id_t *)id;
456 svn_fs_fs__id_txn_create(const svn_fs_fs__id_part_t *node_id,
457 const svn_fs_fs__id_part_t *copy_id,
458 const svn_fs_fs__id_part_t *txn_id,
461 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
463 id->private_id.node_id = *node_id;
464 id->private_id.copy_id = *copy_id;
465 id->private_id.txn_id = *txn_id;
466 id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
468 id->generic_id.vtable = &id_vtable;
469 id->generic_id.fsap_data = id;
471 return (svn_fs_id_t *)id;
476 svn_fs_fs__id_rev_create(const svn_fs_fs__id_part_t *node_id,
477 const svn_fs_fs__id_part_t *copy_id,
478 const svn_fs_fs__id_part_t *rev_item,
481 fs_fs__id_t *id = apr_pcalloc(pool, sizeof(*id));
483 id->private_id.node_id = *node_id;
484 id->private_id.copy_id = *copy_id;
485 id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
486 id->private_id.rev_item = *rev_item;
488 id->generic_id.vtable = &id_vtable;
489 id->generic_id.fsap_data = id;
491 return (svn_fs_id_t *)id;
496 svn_fs_fs__id_copy(const svn_fs_id_t *source, apr_pool_t *pool)
498 const fs_fs__id_t *id = (const fs_fs__id_t *)source;
499 fs_fs__id_t *new_id = apr_pmemdup(pool, id, sizeof(*new_id));
501 new_id->generic_id.fsap_data = new_id;
503 return (svn_fs_id_t *)new_id;
506 /* Return an ID resulting from parsing the string DATA, or NULL if DATA is
507 an invalid ID string. *DATA will be modified / invalidated by this call. */
515 /* Alloc a new svn_fs_id_t structure. */
516 id = apr_pcalloc(pool, sizeof(*id));
517 id->generic_id.vtable = &id_vtable;
518 id->generic_id.fsap_data = id;
520 /* Now, we basically just need to "split" this data on `.'
521 characters. We will use svn_cstring_tokenize, which will put
522 terminators where each of the '.'s used to be. Then our new
523 id field will reference string locations inside our duplicate
527 str = svn_cstring_tokenize(".", &data);
530 if (! part_parse(&id->private_id.node_id, str))
534 str = svn_cstring_tokenize(".", &data);
537 if (! part_parse(&id->private_id.copy_id, str))
541 str = svn_cstring_tokenize(".", &data);
551 /* This is a revision type ID */
552 id->private_id.txn_id.revision = SVN_INVALID_REVNUM;
553 id->private_id.txn_id.number = 0;
556 str = svn_cstring_tokenize("/", &data);
559 if (!locale_independent_strtol(&id->private_id.rev_item.revision,
563 err = svn_cstring_atoi64(&val, data);
566 svn_error_clear(err);
569 id->private_id.rev_item.number = (apr_uint64_t)val;
571 else if (str[0] == 't')
573 /* This is a transaction type ID */
574 id->private_id.rev_item.revision = SVN_INVALID_REVNUM;
575 id->private_id.rev_item.number = 0;
577 if (! txn_id_parse(&id->private_id.txn_id, str + 1))
583 return (svn_fs_id_t *)id;
587 svn_fs_fs__id_parse(const svn_fs_id_t **id_p,
591 svn_fs_id_t *id = id_parse(data, pool);
593 return svn_error_createf(SVN_ERR_FS_MALFORMED_NODEREV_ID, NULL,
594 "Malformed node revision ID string");
601 /* (de-)serialization support */
603 /* Serialize an ID within the serialization CONTEXT.
606 svn_fs_fs__id_serialize(svn_temp_serializer__context_t *context,
607 const svn_fs_id_t * const *in)
609 const fs_fs__id_t *id = (const fs_fs__id_t *)*in;
611 /* nothing to do for NULL ids */
615 /* Serialize the id data struct itself.
616 * Note that the structure behind IN is actually larger than a mere
618 svn_temp_serializer__add_leaf(context,
619 (const void * const *)in,
620 sizeof(fs_fs__id_t));
623 /* Deserialize an ID inside the BUFFER.
626 svn_fs_fs__id_deserialize(void *buffer, svn_fs_id_t **in_out)
630 /* The id maybe all what is in the whole buffer.
631 * Don't try to fixup the pointer in that case*/
632 if (*in_out != buffer)
633 svn_temp_deserializer__resolve(buffer, (void**)in_out);
635 id = (fs_fs__id_t *)*in_out;
637 /* no id, no sub-structure fixup necessary */
641 /* the stored vtable is bogus at best -> set the right one */
642 id->generic_id.vtable = &id_vtable;
643 id->generic_id.fsap_data = id;