Mercurial > public > mercurial-scm > hg
annotate mercurial/thirdparty/xdiff/xutils.c @ 36825:f1ef0e53e628
xdiff: use int64 for hash table size
Follow-up of the previous "long" -> "int64" change. Now xdiff only uses int
for return values and small integers (ex. booleans, shifting score, bits in
hash table size, etc) so it should be able to handle large input.
Differential Revision: https://phab.mercurial-scm.org/D2765
| author | Jun Wu <quark@fb.com> |
|---|---|
| date | Fri, 09 Mar 2018 14:47:29 -0800 |
| parents | 49fe6249937a |
| children |
| rev | line source |
|---|---|
| 36671 | 1 /* |
| 2 * LibXDiff by Davide Libenzi ( File Differential Library ) | |
| 3 * Copyright (C) 2003 Davide Libenzi | |
| 4 * | |
| 5 * This library is free software; you can redistribute it and/or | |
| 6 * modify it under the terms of the GNU Lesser General Public | |
| 7 * License as published by the Free Software Foundation; either | |
| 8 * version 2.1 of the License, or (at your option) any later version. | |
| 9 * | |
| 10 * This library is distributed in the hope that it will be useful, | |
| 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 * Lesser General Public License for more details. | |
| 14 * | |
| 15 * You should have received a copy of the GNU Lesser General Public | |
| 16 * License along with this library; if not, see | |
| 17 * <http://www.gnu.org/licenses/>. | |
| 18 * | |
| 19 * Davide Libenzi <davidel@xmailserver.org> | |
| 20 * | |
| 21 */ | |
| 22 | |
| 23 #include <limits.h> | |
| 24 #include <assert.h> | |
| 25 #include "xinclude.h" | |
| 26 | |
| 27 | |
| 28 | |
| 29 | |
|
36822
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
30 int64_t xdl_bogosqrt(int64_t n) { |
|
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
31 int64_t i; |
| 36671 | 32 |
| 33 /* | |
| 34 * Classical integer square root approximation using shifts. | |
| 35 */ | |
| 36 for (i = 1; n > 0; n >>= 2) | |
| 37 i <<= 1; | |
| 38 | |
| 39 return i; | |
| 40 } | |
| 41 | |
| 42 | |
|
36822
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
43 void *xdl_mmfile_first(mmfile_t *mmf, int64_t *size) |
| 36671 | 44 { |
| 45 *size = mmf->size; | |
| 46 return mmf->ptr; | |
| 47 } | |
| 48 | |
| 49 | |
|
36822
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
50 int64_t xdl_mmfile_size(mmfile_t *mmf) |
| 36671 | 51 { |
| 52 return mmf->size; | |
| 53 } | |
| 54 | |
| 55 | |
|
36822
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
56 int xdl_cha_init(chastore_t *cha, int64_t isize, int64_t icount) { |
| 36671 | 57 |
| 58 cha->head = cha->tail = NULL; | |
| 59 cha->isize = isize; | |
| 60 cha->nsize = icount * isize; | |
| 61 cha->ancur = cha->sncur = NULL; | |
| 62 cha->scurr = 0; | |
| 63 | |
| 64 return 0; | |
| 65 } | |
| 66 | |
| 67 | |
| 68 void xdl_cha_free(chastore_t *cha) { | |
| 69 chanode_t *cur, *tmp; | |
| 70 | |
| 71 for (cur = cha->head; (tmp = cur) != NULL;) { | |
| 72 cur = cur->next; | |
| 73 xdl_free(tmp); | |
| 74 } | |
| 75 } | |
| 76 | |
| 77 | |
| 78 void *xdl_cha_alloc(chastore_t *cha) { | |
| 79 chanode_t *ancur; | |
| 80 void *data; | |
| 81 | |
| 82 if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) { | |
| 83 if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) { | |
| 84 | |
| 85 return NULL; | |
| 86 } | |
| 87 ancur->icurr = 0; | |
| 88 ancur->next = NULL; | |
| 89 if (cha->tail) | |
| 90 cha->tail->next = ancur; | |
| 91 if (!cha->head) | |
| 92 cha->head = ancur; | |
| 93 cha->tail = ancur; | |
| 94 cha->ancur = ancur; | |
| 95 } | |
| 96 | |
| 97 data = (char *) ancur + sizeof(chanode_t) + ancur->icurr; | |
| 98 ancur->icurr += cha->isize; | |
| 99 | |
| 100 return data; | |
| 101 } | |
| 102 | |
|
36822
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
103 int64_t xdl_guess_lines(mmfile_t *mf, int64_t sample) { |
|
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
104 int64_t nl = 0, size, tsize = 0; |
| 36671 | 105 char const *data, *cur, *top; |
| 106 | |
| 107 if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { | |
| 108 for (top = data + size; nl < sample && cur < top; ) { | |
| 109 nl++; | |
| 110 if (!(cur = memchr(cur, '\n', top - cur))) | |
| 111 cur = top; | |
| 112 else | |
| 113 cur++; | |
| 114 } | |
| 115 tsize += (long) (cur - data); | |
| 116 } | |
| 117 | |
| 118 if (nl && tsize) | |
| 119 nl = xdl_mmfile_size(mf) / (tsize / nl); | |
| 120 | |
| 121 return nl + 1; | |
| 122 } | |
| 123 | |
|
36823
49fe6249937a
xdiff: remove unused flags parameter
Jun Wu <quark@fb.com>
parents:
36822
diff
changeset
|
124 int xdl_recmatch(const char *l1, int64_t s1, const char *l2, int64_t s2) |
| 36671 | 125 { |
| 126 if (s1 == s2 && !memcmp(l1, l2, s1)) | |
| 127 return 1; | |
|
36761
09f320067591
xdiff: remove whitespace related feature
Jun Wu <quark@fb.com>
parents:
36671
diff
changeset
|
128 return 0; |
| 36671 | 129 } |
| 130 | |
|
36823
49fe6249937a
xdiff: remove unused flags parameter
Jun Wu <quark@fb.com>
parents:
36822
diff
changeset
|
131 uint64_t xdl_hash_record(char const **data, char const *top) { |
|
36822
882657a9f768
xdiff: replace {unsigned ,}long with {u,}int64_t
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
132 uint64_t ha = 5381; |
| 36671 | 133 char const *ptr = *data; |
| 134 | |
| 135 for (; ptr < top && *ptr != '\n'; ptr++) { | |
| 136 ha += (ha << 5); | |
| 137 ha ^= (unsigned long) *ptr; | |
| 138 } | |
| 139 *data = ptr < top ? ptr + 1: ptr; | |
| 140 | |
| 141 return ha; | |
| 142 } | |
| 143 | |
|
36825
f1ef0e53e628
xdiff: use int64 for hash table size
Jun Wu <quark@fb.com>
parents:
36823
diff
changeset
|
144 unsigned int xdl_hashbits(int64_t size) { |
|
f1ef0e53e628
xdiff: use int64 for hash table size
Jun Wu <quark@fb.com>
parents:
36823
diff
changeset
|
145 int64_t val = 1; |
|
f1ef0e53e628
xdiff: use int64 for hash table size
Jun Wu <quark@fb.com>
parents:
36823
diff
changeset
|
146 unsigned int bits = 0; |
| 36671 | 147 |
|
36825
f1ef0e53e628
xdiff: use int64 for hash table size
Jun Wu <quark@fb.com>
parents:
36823
diff
changeset
|
148 for (; val < size && bits < (int64_t) CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++); |
| 36671 | 149 return bits ? bits: 1; |
| 150 } |