key-gen.c revision 251886 
1/* key-gen.c --- manufacturing sequential keys for some db tables
2 *
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
11 *
12 *      http://www.apache.org/licenses/LICENSE-2.0
13 *
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
19 *    under the License.
20 * ====================================================================
21 */
22
23#include <assert.h>
24#include <string.h>
25#include <stdlib.h>
26#include <apr.h>
27#include <apr_network_io.h>
28#include "private/svn_fs_private.h"
29#include "key-gen.h"
30
31/* The Berkeley DB backend uses a key as a transaction name and the
32   maximum key size must be less than the maximum transaction name
33   length. */
34#if MAX_KEY_SIZE > SVN_FS__TXN_MAX_LEN
35#error The MAX_KEY_SIZE used for BDB txn names is greater than SVN_FS__TXN_MAX_LEN.
36#endif
37
38
39/*** Keys for reps and strings. ***/
40
41void
42svn_fs_fs__add_keys(const char *key1, const char *key2, char *result)
43{
44  apr_ssize_t i1 = strlen(key1) - 1;
45  apr_ssize_t i2 = strlen(key2) - 1;
46  int i3 = 0;
47  int val;
48  int carry = 0;
49  char buf[MAX_KEY_SIZE + 2];
50
51  while ((i1 >= 0) || (i2 >= 0) || (carry > 0))
52    {
53      val = carry;
54      if (i1>=0)
55        val += (key1[i1] <= '9') ? (key1[i1] - '0') : (key1[i1] - 'a' + 10);
56
57      if (i2>=0)
58        val += (key2[i2] <= '9') ? (key2[i2] - '0') : (key2[i2] - 'a' + 10);
59
60      carry = val / 36;
61      val = val % 36;
62
63      buf[i3++] = (char)((val <= 9) ? (val + '0') : (val - 10 + 'a'));
64
65      if (i1>=0)
66        i1--;
67      if (i2>=0)
68        i2--;
69    }
70
71  /* Now reverse the resulting string and NULL terminate it. */
72  for (i1 = 0; i1 < i3; i1++)
73    result[i1] = buf[i3 - i1 - 1];
74
75  result[i1] = '\0';
76}
77
78
79void
80svn_fs_fs__next_key(const char *this, apr_size_t *len, char *next)
81{
82  apr_ssize_t i;
83  apr_size_t olen = *len;     /* remember the first length */
84  char c;                     /* current char */
85  svn_boolean_t carry = TRUE; /* boolean: do we have a carry or not?
86                                 We start with a carry, because we're
87                                 incrementing the number, after all. */
88
89  /* Leading zeros are not allowed, except for the string "0". */
90  if ((*len > 1) && (this[0] == '0'))
91    {
92      *len = 0;
93      return;
94    }
95
96  for (i = (olen - 1); i >= 0; i--)
97    {
98      c = this[i];
99
100      /* Validate as we go. */
101      if (! (((c >= '0') && (c <= '9')) || ((c >= 'a') && (c <= 'z'))))
102        {
103          *len = 0;
104          return;
105        }
106
107      if (carry)
108        {
109          if (c == 'z')
110            next[i] = '0';
111          else
112            {
113              carry = FALSE;
114
115              if (c == '9')
116                next[i] = 'a';
117              else
118                next[i] = ++c;
119            }
120        }
121      else
122        next[i] = c;
123    }
124
125  /* The new length is OLEN, plus 1 if there's a carry out of the
126     leftmost digit. */
127  *len = olen + (carry ? 1 : 0);
128
129  /* Ensure that we haven't overrun the (ludicrous) bound on key length.
130     Note that MAX_KEY_SIZE is a bound on the size *including*
131     the trailing null byte. */
132  assert(*len < MAX_KEY_SIZE);
133
134  /* Now we know it's safe to add the null terminator. */
135  next[*len] = '\0';
136
137  /* Handle any leftover carry. */
138  if (carry)
139    {
140      memmove(next+1, next, olen);
141      next[0] = '1';
142    }
143}
144
145
146int
147svn_fs_fs__key_compare(const char *a, const char *b)
148{
149  apr_size_t a_len = strlen(a);
150  apr_size_t b_len = strlen(b);
151  int cmp;
152
153  if (a_len > b_len)
154    return 1;
155  if (b_len > a_len)
156    return -1;
157  cmp = strcmp(a, b);
158  return (cmp ? (cmp / abs(cmp)) : 0);
159}
160