contrib/subversion/subversion/libsvn_fs_fs/key-gen.c

   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 \f
  39 /*** Keys for reps and strings. ***/
  40
  41 void
  42 svn_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
  79 void
  80 svn_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
 146 int
 147 svn_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 }