← Back to branch summary

~svn/ubuntu/raring/subversion/ppa

« back to all changes in this revision

Viewing changes to subversion/libsvn_fs_base/util/skel.c

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-12-05 01:26:14 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051205012614-qom4xfypgtsqc2xq
Tags: 1.2.3dfsg1-3ubuntu1
Merge with the final Debian release of 1.2.3dfsg1-3, bringing in
fixes to the clean target, better documentation of the libdb4.3
upgrade and build fixes to work with swig1.3_1.3.27.

Show diffs side-by-side

added added

removed removed

Lines of Context:
subversion/libsvn_fs_base/util/skel.c
 
1
/* skel.c --- parsing and unparsing skeletons
 
2
 *
 
3
 * ====================================================================
 
4
 * Copyright (c) 2000-2004 CollabNet.  All rights reserved.
 
5
 *
 
6
 * This software is licensed as described in the file COPYING, which
 
7
 * you should have received as part of this distribution.  The terms
 
8
 * are also available at http://subversion.tigris.org/license-1.html.
 
9
 * If newer versions of this license are posted there, you may use a
 
10
 * newer version instead, at your option.
 
11
 *
 
12
 * This software consists of voluntary contributions made by many
 
13
 * individuals.  For exact contribution history, see the revision
 
14
 * history and logs, available at http://subversion.tigris.org/.
 
15
 * ====================================================================
 
16
 */
 
17
 
 
18
#include <string.h>
 
19
#include "svn_string.h"
 
20
#include "skel.h"
 
21
#include "../key-gen.h"
 
22
 
 
23
 
 
24
/* Parsing skeletons.  */
 
25
 
 
26
enum char_type {
 
27
  type_nothing = 0,
 
28
  type_space = 1,
 
29
  type_digit = 2,
 
30
  type_paren = 3,
 
31
  type_name = 4
 
32
};
 
33
 
 
34
 
 
35
/* We can't use the <ctype.h> macros here, because they are locale-
 
36
   dependent.  The syntax of a skel is specified directly in terms of
 
37
   byte values, and is independent of locale.  */
 
38
 
 
39
static const enum char_type skel_char_type[256] = {
 
40
  0, 0, 0, 0, 0, 0, 0, 0,   0, 1, 1, 0, 1, 1, 0, 0,
 
41
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
42
  1, 0, 0, 0, 0, 0, 0, 0,   3, 3, 0, 0, 0, 0, 0, 0,
 
43
  2, 2, 2, 2, 2, 2, 2, 2,   2, 2, 0, 0, 0, 0, 0, 0,
 
44
 
 
45
  /* 64 */
 
46
  0, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 4, 4, 4, 4, 4,
 
47
  4, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 3, 0, 3, 0, 0,
 
48
  0, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 4, 4, 4, 4, 4,
 
49
  4, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 0, 0, 0, 0, 0,
 
50
 
 
51
  /* 128 */
 
52
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
53
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
54
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
55
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
56
 
 
57
  /* 192 */
 
58
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
59
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
60
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
61
  0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
 
62
};
 
63
 
 
64
 
 
65
static skel_t *parse (const char *data, apr_size_t len,
 
66
                      apr_pool_t *pool);
 
67
static skel_t *list (const char *data, apr_size_t len,
 
68
                     apr_pool_t *pool);
 
69
static skel_t *implicit_atom (const char *data, apr_size_t len,
 
70
                              apr_pool_t *pool);
 
71
static skel_t *explicit_atom (const char *data, apr_size_t len,
 
72
                              apr_pool_t *pool);
 
73
 
 
74
 
 
75
skel_t *
 
76
svn_fs_base__parse_skel (const char *data,
 
77
                         apr_size_t len,
 
78
                         apr_pool_t *pool)
 
79
{
 
80
  return parse (data, len, pool);
 
81
}
 
82
 
 
83
 
 
84
/* Parse any kind of skel object --- atom, or list.  */
 
85
static skel_t *
 
86
parse (const char *data,
 
87
       apr_size_t len,
 
88
       apr_pool_t *pool)
 
89
{
 
90
  char c;
 
91
 
 
92
  /* The empty string isn't a valid skel.  */
 
93
  if (len <= 0)
 
94
    return 0;
 
95
 
 
96
  c = *data;
 
97
 
 
98
  /* Is it a list, or an atom?  */
 
99
  if (c == '(')
 
100
    return list (data, len, pool);
 
101
 
 
102
  /* Is it a string with an implicit length?  */
 
103
  if (skel_char_type[(unsigned char) c] == type_name)
 
104
    return implicit_atom (data, len, pool);
 
105
 
 
106
  /* Otherwise, we assume it's a string with an explicit length;
 
107
     svn_fs_base__getsize will catch the error.  */
 
108
  else
 
109
    return explicit_atom (data, len, pool);
 
110
}
 
111
 
 
112
 
 
113
static skel_t *
 
114
list (const char *data,
 
115
      apr_size_t len,
 
116
      apr_pool_t *pool)
 
117
{
 
118
  const char *end = data + len;
 
119
  const char *list_start;
 
120
 
 
121
  /* Verify that the list starts with an opening paren.  At the
 
122
     moment, all callers have checked this already, but it's more
 
123
     robust this way.  */
 
124
  if (data >= end || *data != '(')
 
125
    return 0;
 
126
 
 
127
  /* Mark where the list starts.  */
 
128
  list_start = data;
 
129
 
 
130
  /* Skip the opening paren.  */
 
131
  data++;
 
132
 
 
133
  /* Parse the children.  */
 
134
  {
 
135
    skel_t *children = 0;
 
136
    skel_t **tail = &children;
 
137
 
 
138
    for (;;)
 
139
      {
 
140
        skel_t *element;
 
141
 
 
142
        /* Skip any whitespace.  */
 
143
        while (data < end
 
144
               && skel_char_type[(unsigned char) *data] == type_space)
 
145
          data++;
 
146
 
 
147
        /* End of data, but no closing paren?  */
 
148
        if (data >= end)
 
149
          return 0;
 
150
 
 
151
        /* End of list?  */
 
152
        if (*data == ')')
 
153
          {
 
154
            data++;
 
155
            break;
 
156
          }
 
157
 
 
158
        /* Parse the next element in the list.  */
 
159
        element = parse (data, end - data, pool);
 
160
        if (! element)
 
161
          return 0;
 
162
 
 
163
        /* Link that element into our list.  */
 
164
        element->next = 0;
 
165
        *tail = element;
 
166
        tail = &element->next;
 
167
 
 
168
        /* Advance past that element.  */
 
169
        data = element->data + element->len;
 
170
      }
 
171
 
 
172
    /* Construct the return value.  */
 
173
    {
 
174
      skel_t *s = apr_pcalloc (pool, sizeof (*s));
 
175
 
 
176
      s->is_atom = FALSE;
 
177
      s->data = list_start;
 
178
      s->len = data - list_start;
 
179
      s->children = children;
 
180
 
 
181
      return s;
 
182
    }
 
183
  }
 
184
}
 
185
 
 
186
 
 
187
/* Parse an atom with implicit length --- one that starts with a name
 
188
   character, terminated by whitespace, '(', ')', or end-of-data.  */
 
189
static skel_t *
 
190
implicit_atom (const char *data,
 
191
               apr_size_t len,
 
192
               apr_pool_t *pool)
 
193
{
 
194
  const char *start = data;
 
195
  const char *end = data + len;
 
196
  skel_t *s;
 
197
 
 
198
  /* Verify that the atom starts with a name character.  At the
 
199
     moment, all callers have checked this already, but it's more
 
200
     robust this way.  */
 
201
  if (data >= end || skel_char_type[(unsigned char) *data] != type_name)
 
202
    return 0;
 
203
 
 
204
  /* Find the end of the string.  */
 
205
  while (++data < end
 
206
         && skel_char_type[(unsigned char) *data] != type_space
 
207
         && skel_char_type[(unsigned char) *data] != type_paren)
 
208
    ;
 
209
 
 
210
  /* Allocate the skel representing this string.  */
 
211
  s = apr_pcalloc (pool, sizeof (*s));
 
212
  s->is_atom = TRUE;
 
213
  s->data = start;
 
214
  s->len = data - start;
 
215
 
 
216
  return s;
 
217
}
 
218
 
 
219
 
 
220
/* Parse an atom with explicit length --- one that starts with a byte
 
221
   length, as a decimal ASCII number.  */
 
222
static skel_t *
 
223
explicit_atom (const char *data,
 
224
               apr_size_t len,
 
225
               apr_pool_t *pool)
 
226
{
 
227
  const char *end = data + len;
 
228
  const char *next;
 
229
  apr_size_t size;
 
230
  skel_t *s;
 
231
 
 
232
  /* Parse the length.  */
 
233
  size = svn_fs_base__getsize (data, end - data, &next, end - data);
 
234
  data = next;
 
235
 
 
236
  /* Exit if we overflowed, or there wasn't a valid number there.  */
 
237
  if (! data)
 
238
    return 0;
 
239
 
 
240
  /* Skip the whitespace character after the length.  */
 
241
  if (data >= end || skel_char_type[(unsigned char) *data] != type_space)
 
242
    return 0;
 
243
  data++;
 
244
 
 
245
  /* Check the length.  */
 
246
  if (data + size > end)
 
247
    return 0;
 
248
 
 
249
  /* Allocate the skel representing this string.  */
 
250
  s = apr_pcalloc (pool, sizeof (skel_t));
 
251
  s->is_atom = TRUE;
 
252
  s->data = data;
 
253
  s->len = size;
 
254
 
 
255
  return s;
 
256
}
 
257
 
 
258
 
 
259
 
 
260
/* Unparsing skeletons.  */
 
261
 
 
262
static apr_size_t estimate_unparsed_size (skel_t *);
 
263
static svn_stringbuf_t *unparse (skel_t *, svn_stringbuf_t *, apr_pool_t *);
 
264
 
 
265
 
 
266
svn_stringbuf_t *
 
267
svn_fs_base__unparse_skel (skel_t *skel, apr_pool_t *pool)
 
268
{
 
269
  svn_stringbuf_t *str;
 
270
 
 
271
  /* Allocate a string to hold the data.  */
 
272
  str = apr_palloc (pool, sizeof (*str));
 
273
  str->pool = pool;
 
274
  str->blocksize = estimate_unparsed_size (skel) + 200;
 
275
  str->data = apr_palloc (pool, str->blocksize);
 
276
  str->len = 0;
 
277
 
 
278
  return unparse (skel, str, pool);
 
279
}
 
280
 
 
281
 
 
282
/* Return an estimate of the number of bytes that the external
 
283
   representation of SKEL will occupy.  Since reallocing is expensive
 
284
   in pools, it's worth trying to get the buffer size right the first
 
285
   time.  */
 
286
static apr_size_t
 
287
estimate_unparsed_size (skel_t *skel)
 
288
{
 
289
  if (skel->is_atom)
 
290
    {
 
291
      if (skel->len < 100)
 
292
        /* If we have to use the explicit-length form, that'll be
 
293
           two bytes for the length, one byte for the space, and
 
294
           the contents.  */
 
295
        return skel->len + 3;
 
296
      else
 
297
        return skel->len + 30;
 
298
    }
 
299
  else
 
300
    {
 
301
      int total_len;
 
302
      skel_t *child;
 
303
 
 
304
      /* Allow space for opening and closing parens, and a space
 
305
         between each pair of elements.  */
 
306
      total_len = 2;
 
307
      for (child = skel->children; child; child = child->next)
 
308
        total_len += estimate_unparsed_size (child) + 1;
 
309
 
 
310
      return total_len;
 
311
    }
 
312
}
 
313
 
 
314
 
 
315
/* Return non-zero iff we should use the implicit-length form for SKEL.
 
316
   Assume that SKEL is an atom.  */
 
317
static svn_boolean_t
 
318
use_implicit (skel_t *skel)
 
319
{
 
320
  /* If it's null, or long, we should use explicit-length form.  */
 
321
  if (skel->len == 0
 
322
      || skel->len >= 100)
 
323
    return FALSE;
 
324
 
 
325
  /* If it doesn't start with a name character, we must use
 
326
     explicit-length form.  */
 
327
  if (skel_char_type[(unsigned char) skel->data[0]] != type_name)
 
328
    return FALSE;
 
329
 
 
330
  /* If it contains any whitespace or parens, then we must use
 
331
     explicit-length form.  */
 
332
  {
 
333
    apr_size_t i;
 
334
 
 
335
    for (i = 1; i < skel->len; i++)
 
336
      if (skel_char_type[(unsigned char) skel->data[i]] == type_space
 
337
          || skel_char_type[(unsigned char) skel->data[i]] == type_paren)
 
338
        return FALSE;
 
339
  }
 
340
 
 
341
  /* If we can't reject it for any of the above reasons, then we can
 
342
     use implicit-length form.  */
 
343
  return TRUE;
 
344
}
 
345
 
 
346
 
 
347
/* Append the concrete representation of SKEL to the string STR.
 
348
   Grow S with new space from POOL as necessary.  */
 
349
static svn_stringbuf_t *
 
350
unparse (skel_t *skel, svn_stringbuf_t *str, apr_pool_t *pool)
 
351
{
 
352
  if (skel->is_atom)
 
353
    {
 
354
      /* Append an atom to STR.  */
 
355
      if (use_implicit (skel))
 
356
        svn_stringbuf_appendbytes (str, skel->data, skel->len);
 
357
      else
 
358
        {
 
359
          /* Append the length to STR.  */
 
360
          char buf[200];
 
361
          int length_len;
 
362
 
 
363
          length_len = svn_fs_base__putsize (buf, sizeof (buf), skel->len);
 
364
          if (! length_len)
 
365
            abort ();
 
366
 
 
367
          /* Make sure we have room for the length, the space, and the
 
368
             atom's contents.  */
 
369
          svn_stringbuf_ensure (str, str->len + length_len + 1 + skel->len);
 
370
          svn_stringbuf_appendbytes (str, buf, length_len);
 
371
          str->data[str->len++] = ' ';
 
372
          svn_stringbuf_appendbytes (str, skel->data, skel->len);
 
373
        }
 
374
    }
 
375
  else
 
376
    {
 
377
      /* Append a list to STR.  */
 
378
      skel_t *child;
 
379
 
 
380
      /* Emit an opening parenthesis.  */
 
381
      svn_stringbuf_ensure (str, str->len + 1);
 
382
      str->data[str->len++] = '(';
 
383
 
 
384
      /* Append each element.  Emit a space between each pair of elements.  */
 
385
      for (child = skel->children; child; child = child->next)
 
386
        {
 
387
          unparse (child, str, pool);
 
388
          if (child->next)
 
389
            {
 
390
              svn_stringbuf_ensure (str, str->len + 1);
 
391
              str->data[str->len++] = ' ';
 
392
            }
 
393
        }
 
394
 
 
395
      /* Emit a closing parenthesis.  */
 
396
      svn_stringbuf_appendbytes (str, ")", 1);
 
397
    }
 
398
 
 
399
  return str;
 
400
}
 
401
 
 
402
 
 
403
 
 
404
/* Building skels.  */
 
405
 
 
406
 
 
407
skel_t *
 
408
svn_fs_base__str_atom (const char *str, apr_pool_t *pool)
 
409
{
 
410
  skel_t *skel = apr_pcalloc (pool, sizeof (*skel));
 
411
  skel->is_atom = TRUE;
 
412
  skel->data = str;
 
413
  skel->len = strlen (str);
 
414
 
 
415
  return skel;
 
416
}
 
417
 
 
418
 
 
419
skel_t *
 
420
svn_fs_base__mem_atom (const void *addr,
 
421
                       apr_size_t len,
 
422
                       apr_pool_t *pool)
 
423
{
 
424
  skel_t *skel = apr_pcalloc (pool, sizeof (*skel));
 
425
  skel->is_atom = TRUE;
 
426
  skel->data = addr;
 
427
  skel->len = len;
 
428
 
 
429
  return skel;
 
430
}
 
431
 
 
432
 
 
433
skel_t *
 
434
svn_fs_base__make_empty_list (apr_pool_t *pool)
 
435
{
 
436
  skel_t *skel = apr_pcalloc (pool, sizeof (*skel));
 
437
  return skel;
 
438
}
 
439
 
 
440
 
 
441
void
 
442
svn_fs_base__prepend (skel_t *skel, skel_t *list_skel)
 
443
{
 
444
  /* If list_skel isn't even a list, somebody's not using this
 
445
     function properly. */
 
446
  if (list_skel->is_atom)
 
447
    abort();
 
448
 
 
449
  skel->next = list_skel->children;
 
450
  list_skel->children = skel;
 
451
}
 
452
 
 
453
 
 
454
void
 
455
svn_fs_base__append (skel_t *skel, skel_t *list_skel)
 
456
{
 
457
  /* If list_skel isn't even a list, somebody's not using this
 
458
     function properly. */
 
459
  if (list_skel->is_atom)
 
460
    abort();
 
461
 
 
462
  /* No kids?  Let's make one. */
 
463
  if (! list_skel->children)
 
464
    {
 
465
      list_skel->children = skel;
 
466
    }
 
467
  else
 
468
    {
 
469
      skel_t *tmp = list_skel->children;
 
470
 
 
471
      /* Find the last child... */
 
472
      while (tmp->next)
 
473
        {
 
474
          tmp = tmp->next;
 
475
        }
 
476
      /* ...and then give her a sister. */
 
477
      tmp->next = skel;
 
478
    }
 
479
}
 
480
 
 
481
 
 
482
 
 
483
/* Examining skels.  */
 
484
 
 
485
 
 
486
svn_boolean_t
 
487
svn_fs_base__matches_atom (skel_t *skel, const char *str)
 
488
{
 
489
  if (skel && skel->is_atom)
 
490
    {
 
491
      apr_size_t len = strlen (str);
 
492
 
 
493
      return ((skel->len == len
 
494
               && ! memcmp (skel->data, str, len)) ? TRUE : FALSE);
 
495
    }
 
496
  return FALSE;
 
497
}
 
498
 
 
499
 
 
500
int
 
501
svn_fs_base__atom_matches_string (skel_t *skel, const svn_string_t *str)
 
502
{
 
503
  if (skel && skel->is_atom)
 
504
    {
 
505
      return ((skel->len == str->len
 
506
               && ! memcmp (skel->data, str->data, skel->len)) ? TRUE : FALSE);
 
507
    }
 
508
  return FALSE;
 
509
}
 
510
 
 
511
 
 
512
int
 
513
svn_fs_base__list_length (skel_t *skel)
 
514
{
 
515
  int len = 0;
 
516
  skel_t *child;
 
517
 
 
518
  if ((! skel) || skel->is_atom)
 
519
    return -1;
 
520
 
 
521
  for (child = skel->children; child; child = child->next)
 
522
    len++;
 
523
 
 
524
  return len;
 
525
}
 
526
 
 
527
 
 
528
 
 
529
/* Comparing skels. */
 
530
 
 
531
svn_boolean_t
 
532
svn_fs_base__skels_are_equal (skel_t *skel1, skel_t *skel2)
 
533
{
 
534
  if (skel1 == skel2)
 
535
    return TRUE;
 
536
 
 
537
  /* Else not `eq', but might still be `equal'. */
 
538
 
 
539
  if (skel1->is_atom && skel2->is_atom)
 
540
    {
 
541
      if ((skel1->len == skel2->len)
 
542
          && (! strncmp (skel1->data, skel2->data, skel1->len)))
 
543
        return TRUE;
 
544
      else
 
545
        return FALSE;
 
546
    }
 
547
  else if (((! skel1->is_atom) && (! skel2->is_atom))
 
548
           && ((svn_fs_base__list_length (skel1))
 
549
               == (svn_fs_base__list_length (skel2))))
 
550
    {
 
551
      int len = svn_fs_base__list_length (skel1);
 
552
      int i;
 
553
 
 
554
      for (i = 0; i < len; i++)
 
555
        if (! svn_fs_base__skels_are_equal ((skel1->children) + i,
 
556
                                            (skel2->children) + i))
 
557
          return FALSE;
 
558
 
 
559
      return TRUE;
 
560
    }
 
561
  else
 
562
    return FALSE;
 
563
}
 
564
 
 
565
 
 
566
 
 
567
/* Copying skels.  */
 
568
 
 
569
 
 
570
skel_t *
 
571
svn_fs_base__copy_skel (skel_t *skel, apr_pool_t *pool)
 
572
{
 
573
  skel_t *copy = apr_pcalloc (pool, sizeof (*copy));
 
574
 
 
575
  if (skel->is_atom)
 
576
    {
 
577
      apr_size_t len = skel->len;
 
578
      char *s = apr_palloc (pool, len);
 
579
 
 
580
      memcpy (s, skel->data, len);
 
581
      copy->is_atom = TRUE;
 
582
      copy->data = s;
 
583
      copy->len = len;
 
584
    }
 
585
  else
 
586
    {
 
587
      skel_t *skel_child, **copy_child_ptr;
 
588
 
 
589
      copy->is_atom = FALSE;
 
590
      copy->data = 0;
 
591
      copy->len = 0;
 
592
 
 
593
      copy_child_ptr = &copy->children;
 
594
      for (skel_child = skel->children;
 
595
           skel_child;
 
596
           skel_child = skel_child->next)
 
597
        {
 
598
          *copy_child_ptr = svn_fs_base__copy_skel (skel_child, pool);
 
599
          copy_child_ptr = &(*copy_child_ptr)->next;
 
600
        }
 
601
      *copy_child_ptr = 0;
 
602
    }
 
603
 
 
604
  return copy;
 
605
}