Fix compiler warning due to missing function prototype.
[svn.git] / subversion / libsvn_subr / hash.c
blobb132b2697f653ef3b4d908d73eb1dd93ad7164e6
1 /*
2 * hash.c : dumping and reading hash tables to/from files.
4 * ====================================================================
5 * Copyright (c) 2000-2004 CollabNet. All rights reserved.
7 * This software is licensed as described in the file COPYING, which
8 * you should have received as part of this distribution. The terms
9 * are also available at http://subversion.tigris.org/license-1.html.
10 * If newer versions of this license are posted there, you may use a
11 * newer version instead, at your option.
13 * This software consists of voluntary contributions made by many
14 * individuals. For exact contribution history, see the revision
15 * history and logs, available at http://subversion.tigris.org/.
16 * ====================================================================
21 #include <stdlib.h>
22 #include <limits.h>
23 #include <assert.h>
24 #include <apr_version.h>
25 #include <apr_pools.h>
26 #include <apr_hash.h>
27 #include <apr_file_io.h>
28 #include "svn_types.h"
29 #include "svn_string.h"
30 #include "svn_error.h"
31 #include "svn_hash.h"
32 #include "svn_sorts.h"
33 #include "svn_io.h"
34 #include "svn_pools.h"
35 #include "private/svn_dep_compat.h"
40 * The format of a dumped hash table is:
42 * K <nlength>
43 * name (a string of <nlength> bytes, followed by a newline)
44 * V <vlength>
45 * val (a string of <vlength> bytes, followed by a newline)
46 * [... etc, etc ...]
47 * END
50 * (Yes, there is a newline after END.)
52 * For example:
54 * K 5
55 * color
56 * V 3
57 * red
58 * K 11
59 * wine review
60 * V 376
61 * A forthright entrance, yet coquettish on the tongue, its deceptively
62 * fruity exterior hides the warm mahagony undercurrent that is the
63 * hallmark of Chateau Fraisant-Pitre. Connoisseurs of the region will
64 * be pleased to note the familiar, subtle hints of mulberries and
65 * carburator fluid. Its confident finish is marred only by a barely
66 * detectable suggestion of rancid squid ink.
67 * K 5
68 * price
69 * V 8
70 * US $6.50
71 * END
78 /*** Dumping and loading hash files. */
80 /* Implements svn_hash_read2 and svn_hash_read_incremental. */
81 static svn_error_t *
82 hash_read(apr_hash_t *hash, svn_stream_t *stream, const char *terminator,
83 svn_boolean_t incremental, apr_pool_t *pool)
85 svn_stringbuf_t *buf;
86 svn_boolean_t eof;
87 apr_size_t len, keylen, vallen;
88 char c, *end, *keybuf, *valbuf;
90 while (1)
92 /* Read a key length line. Might be END, though. */
93 SVN_ERR(svn_stream_readline(stream, &buf, "\n", &eof, pool));
95 /* Check for the end of the hash. */
96 if ((!terminator && eof && buf->len == 0)
97 || (terminator && (strcmp(buf->data, terminator) == 0)))
98 return SVN_NO_ERROR;
100 /* Check for unexpected end of stream */
101 if (eof)
102 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
104 if ((buf->len >= 3) && (buf->data[0] == 'K') && (buf->data[1] == ' '))
106 /* Get the length of the key */
107 keylen = (size_t) strtoul(buf->data + 2, &end, 10);
108 if (keylen == (size_t) ULONG_MAX || *end != '\0')
109 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
111 /* Now read that much into a buffer. */
112 keybuf = apr_palloc(pool, keylen + 1);
113 SVN_ERR(svn_stream_read(stream, keybuf, &keylen));
114 keybuf[keylen] = '\0';
116 /* Suck up extra newline after key data */
117 len = 1;
118 SVN_ERR(svn_stream_read(stream, &c, &len));
119 if (c != '\n')
120 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
122 /* Read a val length line */
123 SVN_ERR(svn_stream_readline(stream, &buf, "\n", &eof, pool));
125 if ((buf->data[0] == 'V') && (buf->data[1] == ' '))
127 vallen = (size_t) strtoul(buf->data + 2, &end, 10);
128 if (vallen == (size_t) ULONG_MAX || *end != '\0')
129 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
131 valbuf = apr_palloc(pool, vallen + 1);
132 SVN_ERR(svn_stream_read(stream, valbuf, &vallen));
133 valbuf[vallen] = '\0';
135 /* Suck up extra newline after val data */
136 len = 1;
137 SVN_ERR(svn_stream_read(stream, &c, &len));
138 if (c != '\n')
139 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
141 /* Add a new hash entry. */
142 apr_hash_set(hash, keybuf, keylen,
143 svn_string_ncreate(valbuf, vallen, pool));
145 else
146 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
148 else if (incremental && (buf->len >= 3)
149 && (buf->data[0] == 'D') && (buf->data[1] == ' '))
151 /* Get the length of the key */
152 keylen = (size_t) strtoul(buf->data + 2, &end, 10);
153 if (keylen == (size_t) ULONG_MAX || *end != '\0')
154 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
156 /* Now read that much into a buffer. */
157 keybuf = apr_palloc(pool, keylen + 1);
158 SVN_ERR(svn_stream_read(stream, keybuf, &keylen));
159 keybuf[keylen] = '\0';
161 /* Suck up extra newline after key data */
162 len = 1;
163 SVN_ERR(svn_stream_read(stream, &c, &len));
164 if (c != '\n')
165 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
167 /* Remove this hash entry. */
168 apr_hash_set(hash, keybuf, keylen, NULL);
170 else
171 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
176 /* Implements svn_hash_write2 and svn_hash_write_incremental. */
177 static svn_error_t *
178 hash_write(apr_hash_t *hash, apr_hash_t *oldhash, svn_stream_t *stream,
179 const char *terminator, apr_pool_t *pool)
181 apr_pool_t *subpool;
182 apr_size_t len;
183 apr_array_header_t *list;
184 int i;
186 subpool = svn_pool_create(pool);
188 list = svn_sort__hash(hash, svn_sort_compare_items_lexically, pool);
189 for (i = 0; i < list->nelts; i++)
191 svn_sort__item_t *item = &APR_ARRAY_IDX(list, i, svn_sort__item_t);
192 svn_string_t *valstr = item->value;
194 svn_pool_clear(subpool);
196 /* Don't output entries equal to the ones in oldhash, if present. */
197 if (oldhash)
199 svn_string_t *oldstr = apr_hash_get(oldhash, item->key, item->klen);
201 if (oldstr && svn_string_compare(valstr, oldstr))
202 continue;
205 /* Write it out. */
206 SVN_ERR(svn_stream_printf(stream, subpool,
207 "K %" APR_SSIZE_T_FMT "\n%s\n"
208 "V %" APR_SIZE_T_FMT "\n",
209 item->klen, (const char *) item->key,
210 valstr->len));
211 len = valstr->len;
212 SVN_ERR(svn_stream_write(stream, valstr->data, &len));
213 SVN_ERR(svn_stream_printf(stream, subpool, "\n"));
216 if (oldhash)
218 /* Output a deletion entry for each property in oldhash but not hash. */
219 list = svn_sort__hash(oldhash, svn_sort_compare_items_lexically,
220 pool);
221 for (i = 0; i < list->nelts; i++)
223 svn_sort__item_t *item = &APR_ARRAY_IDX(list, i, svn_sort__item_t);
225 svn_pool_clear(subpool);
227 /* If it's not present in the new hash, write out a D entry. */
228 if (! apr_hash_get(hash, item->key, item->klen))
229 SVN_ERR(svn_stream_printf(stream, subpool,
230 "D %" APR_SSIZE_T_FMT "\n%s\n",
231 item->klen, (const char *) item->key));
235 if (terminator)
236 SVN_ERR(svn_stream_printf(stream, subpool, "%s\n", terminator));
238 svn_pool_destroy(subpool);
239 return SVN_NO_ERROR;
243 svn_error_t *svn_hash_read2(apr_hash_t *hash, svn_stream_t *stream,
244 const char *terminator, apr_pool_t *pool)
246 return hash_read(hash, stream, terminator, FALSE, pool);
250 svn_error_t *svn_hash_read_incremental(apr_hash_t *hash,
251 svn_stream_t *stream,
252 const char *terminator,
253 apr_pool_t *pool)
255 return hash_read(hash, stream, terminator, TRUE, pool);
259 svn_error_t *
260 svn_hash_write2(apr_hash_t *hash, svn_stream_t *stream,
261 const char *terminator, apr_pool_t *pool)
263 return hash_write(hash, NULL, stream, terminator, pool);
267 svn_error_t *
268 svn_hash_write_incremental(apr_hash_t *hash, apr_hash_t *oldhash,
269 svn_stream_t *stream, const char *terminator,
270 apr_pool_t *pool)
272 assert(oldhash != NULL);
273 return hash_write(hash, oldhash, stream, terminator, pool);
277 svn_error_t *
278 svn_hash_write(apr_hash_t *hash, apr_file_t *destfile, apr_pool_t *pool)
280 return hash_write(hash, NULL, svn_stream_from_aprfile(destfile, pool),
281 SVN_HASH_TERMINATOR, pool);
285 /* There are enough quirks in the deprecated svn_hash_read that we
286 should just preserve its implementation. */
287 svn_error_t *
288 svn_hash_read(apr_hash_t *hash,
289 apr_file_t *srcfile,
290 apr_pool_t *pool)
292 svn_error_t *err;
293 char buf[SVN_KEYLINE_MAXLEN];
294 apr_size_t num_read;
295 char c;
296 int first_time = 1;
299 while (1)
301 /* Read a key length line. Might be END, though. */
302 apr_size_t len = sizeof(buf);
304 err = svn_io_read_length_line(srcfile, buf, &len, pool);
305 if (err && APR_STATUS_IS_EOF(err->apr_err) && first_time)
307 /* We got an EOF on our very first attempt to read, which
308 means it's a zero-byte file. No problem, just go home. */
309 svn_error_clear(err);
310 return SVN_NO_ERROR;
312 else if (err)
313 /* Any other circumstance is a genuine error. */
314 return err;
316 first_time = 0;
318 if (((len == 3) && (buf[0] == 'E') && (buf[1] == 'N') && (buf[2] == 'D'))
319 || ((len == 9)
320 && (buf[0] == 'P')
321 && (buf[1] == 'R') /* We formerly used just "END" to */
322 && (buf[2] == 'O') /* end a property hash, but later */
323 && (buf[3] == 'P') /* we added "PROPS-END", so that */
324 && (buf[4] == 'S') /* the fs dump format would be */
325 && (buf[5] == '-') /* more human-readable. That's */
326 && (buf[6] == 'E') /* why we accept either way here. */
327 && (buf[7] == 'N')
328 && (buf[8] == 'D')))
330 /* We've reached the end of the dumped hash table, so leave. */
331 return SVN_NO_ERROR;
333 else if ((buf[0] == 'K') && (buf[1] == ' '))
335 /* Get the length of the key */
336 size_t keylen = (size_t) atoi(buf + 2);
338 /* Now read that much into a buffer, + 1 byte for null terminator */
339 void *keybuf = apr_palloc(pool, keylen + 1);
340 SVN_ERR(svn_io_file_read_full(srcfile,
341 keybuf, keylen, &num_read, pool));
342 ((char *) keybuf)[keylen] = '\0';
344 /* Suck up extra newline after key data */
345 SVN_ERR(svn_io_file_getc(&c, srcfile, pool));
346 if (c != '\n')
347 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
349 /* Read a val length line */
350 len = sizeof(buf);
351 SVN_ERR(svn_io_read_length_line(srcfile, buf, &len, pool));
353 if ((buf[0] == 'V') && (buf[1] == ' '))
355 svn_string_t *value = apr_palloc(pool, sizeof(*value));
357 /* Get the length of the value */
358 apr_size_t vallen = atoi(buf + 2);
360 /* Again, 1 extra byte for the null termination. */
361 void *valbuf = apr_palloc(pool, vallen + 1);
362 SVN_ERR(svn_io_file_read_full(srcfile,
363 valbuf, vallen,
364 &num_read, pool));
365 ((char *) valbuf)[vallen] = '\0';
367 /* Suck up extra newline after val data */
368 SVN_ERR(svn_io_file_getc(&c, srcfile, pool));
369 if (c != '\n')
370 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
372 value->data = valbuf;
373 value->len = vallen;
375 /* The Grand Moment: add a new hash entry! */
376 apr_hash_set(hash, keybuf, keylen, value);
378 else
380 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
383 else
385 return svn_error_create(SVN_ERR_MALFORMED_FILE, NULL, NULL);
387 } /* while (1) */
392 /*** Diffing hashes ***/
394 svn_error_t *
395 svn_hash_diff(apr_hash_t *hash_a,
396 apr_hash_t *hash_b,
397 svn_hash_diff_func_t diff_func,
398 void *diff_func_baton,
399 apr_pool_t *pool)
401 apr_hash_index_t *hi;
403 if (hash_a)
404 for (hi = apr_hash_first(pool, hash_a); hi; hi = apr_hash_next(hi))
406 const void *key;
407 apr_ssize_t klen;
409 apr_hash_this(hi, &key, &klen, NULL);
411 if (hash_b && (apr_hash_get(hash_b, key, klen)))
412 SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_both,
413 diff_func_baton));
414 else
415 SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_a,
416 diff_func_baton));
419 if (hash_b)
420 for (hi = apr_hash_first(pool, hash_b); hi; hi = apr_hash_next(hi))
422 const void *key;
423 apr_ssize_t klen;
425 apr_hash_this(hi, &key, &klen, NULL);
427 if (! (hash_a && apr_hash_get(hash_a, key, klen)))
428 SVN_ERR((*diff_func)(key, klen, svn_hash_diff_key_b,
429 diff_func_baton));
432 return SVN_NO_ERROR;
436 /*** Misc. hash APIs ***/
438 svn_error_t *
439 svn_hash_keys(apr_array_header_t **array,
440 apr_hash_t *hash,
441 apr_pool_t *pool)
443 apr_hash_index_t *hi;
445 *array = apr_array_make(pool, apr_hash_count(hash), sizeof(const char *));
447 for (hi = apr_hash_first(pool, hash); hi; hi = apr_hash_next(hi))
449 const void *key;
450 const char *path;
452 apr_hash_this(hi, &key, NULL, NULL);
453 path = key;
455 APR_ARRAY_PUSH(*array, const char *) = path;
458 return SVN_NO_ERROR;
462 svn_error_t *
463 svn_hash_from_cstring_keys(apr_hash_t **hash_p,
464 const apr_array_header_t *keys,
465 apr_pool_t *pool)
467 int i;
468 apr_hash_t *hash = apr_hash_make(pool);
469 for (i = 0; i < keys->nelts; i++)
471 const char *key =
472 apr_pstrdup(pool, APR_ARRAY_IDX(keys, i, const char *));
473 apr_hash_set(hash, key, APR_HASH_KEY_STRING, key);
475 *hash_p = hash;
476 return SVN_NO_ERROR;
480 svn_error_t *
481 svn_hash__clear(apr_hash_t *hash)
483 #if APR_VERSION_AT_LEAST(1, 3, 0)
484 apr_hash_clear(hash);
485 #else
486 apr_hash_index_t *hi;
487 const void *key;
488 apr_ssize_t klen;
490 for (hi = apr_hash_first(NULL, hash); hi; hi = apr_hash_next(hi))
492 apr_hash_this(hi, &key, &klen, NULL);
493 apr_hash_set(hash, key, klen, NULL);
495 #endif
496 return SVN_NO_ERROR;