Skip to content
Navigation Menu
Toggle navigation
Sign in
In this repository
All GitHub Enterprise
↵
Jump to
↵
No suggested jump to results
In this repository
All GitHub Enterprise
↵
Jump to
↵
In this organization
All GitHub Enterprise
↵
Jump to
↵
In this repository
All GitHub Enterprise
↵
Jump to
↵
Sign in
Reseting focus
You signed in with another tab or window.
Reload
to refresh your session.
You signed out in another tab or window.
Reload
to refresh your session.
You switched accounts on another tab or window.
Reload
to refresh your session.
Dismiss alert
{{ message }}
git-mirror
/
git
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
0
Pull requests
0
Actions
Projects
0
Security
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security
Insights
Files
abcb865
Documentation
block-sha1
builtin
compat
contrib
ewah
git-gui
gitk-git
gitweb
mergetools
perl
po
ppc
t
templates
vcs-svn
xdiff
.gitattributes
.gitignore
.mailmap
COPYING
GIT-VERSION-GEN
INSTALL
LGPL-2.1
Makefile
README
RelNotes
abspath.c
aclocal.m4
advice.c
advice.h
alias.c
alloc.c
archive-tar.c
archive-zip.c
archive.c
archive.h
argv-array.c
argv-array.h
attr.c
attr.h
base85.c
bisect.c
bisect.h
blob.c
blob.h
branch.c
branch.h
builtin.h
bulk-checkin.c
bulk-checkin.h
bundle.c
bundle.h
cache-tree.c
cache-tree.h
cache.h
check-builtins.sh
check-racy.c
check_bindir
color.c
color.h
column.c
column.h
combine-diff.c
command-list.txt
commit-slab.h
commit.c
commit.h
config.c
config.mak.in
config.mak.uname
configure.ac
connect.c
connect.h
connected.c
connected.h
convert.c
convert.h
copy.c
credential-cache--daemon.c
credential-cache.c
credential-store.c
credential.c
credential.h
csum-file.c
csum-file.h
ctype.c
daemon.c
date.c
decorate.c
decorate.h
delta.h
diff-delta.c
diff-lib.c
diff-no-index.c
diff.c
diff.h
diffcore-break.c
diffcore-delta.c
diffcore-order.c
diffcore-pickaxe.c
diffcore-rename.c
diffcore.h
dir.c
dir.h
editor.c
entry.c
environment.c
exec_cmd.c
exec_cmd.h
fast-import.c
fetch-pack.c
fetch-pack.h
fmt-merge-msg.h
fsck.c
fsck.h
generate-cmdlist.sh
gettext.c
gettext.h
git-add--interactive.perl
git-am.sh
git-archimport.perl
git-bisect.sh
git-compat-util.h
git-cvsexportcommit.perl
git-cvsimport.perl
git-cvsserver.perl
git-difftool--helper.sh
git-difftool.perl
git-filter-branch.sh
git-instaweb.sh
git-merge-octopus.sh
git-merge-one-file.sh
git-merge-resolve.sh
git-mergetool--lib.sh
git-mergetool.sh
git-p4.py
git-parse-remote.sh
git-pull.sh
git-quiltimport.sh
git-rebase--am.sh
git-rebase--interactive.sh
git-rebase--merge.sh
git-rebase.sh
git-relink.perl
git-remote-testgit.sh
git-request-pull.sh
git-send-email.perl
git-sh-i18n.sh
git-sh-setup.sh
git-stash.sh
git-submodule.sh
git-svn.perl
git-web--browse.sh
git.c
git.rc
git.spec.in
gpg-interface.c
gpg-interface.h
graph.c
graph.h
grep.c
grep.h
hashmap.c
hashmap.h
help.c
help.h
hex.c
http-backend.c
http-fetch.c
http-push.c
http-walker.c
http.c
http.h
ident.c
imap-send.c
khash.h
kwset.c
kwset.h
levenshtein.c
levenshtein.h
line-log.c
line-log.h
line-range.c
line-range.h
list-objects.c
list-objects.h
ll-merge.c
ll-merge.h
lockfile.c
log-tree.c
log-tree.h
mailmap.c
mailmap.h
match-trees.c
merge-blobs.c
merge-blobs.h
merge-recursive.c
merge-recursive.h
merge.c
mergesort.c
mergesort.h
name-hash.c
notes-cache.c
notes-cache.h
notes-merge.c
notes-merge.h
notes-utils.c
notes-utils.h
notes.c
notes.h
object.c
object.h
pack-bitmap-write.c
pack-bitmap.c
pack-bitmap.h
pack-check.c
pack-objects.c
pack-objects.h
pack-revindex.c
pack-revindex.h
pack-write.c
pack.h
pager.c
parse-options-cb.c
parse-options.c
parse-options.h
patch-delta.c
patch-ids.c
patch-ids.h
path.c
pathspec.c
pathspec.h
pkt-line.c
pkt-line.h
preload-index.c
pretty.c
prio-queue.c
prio-queue.h
progress.c
progress.h
prompt.c
prompt.h
quote.c
quote.h
reachable.c
reachable.h
read-cache.c
reflog-walk.c
reflog-walk.h
refs.c
refs.h
remote-curl.c
remote-testsvn.c
remote.c
remote.h
replace_object.c
rerere.c
rerere.h
resolve-undo.c
resolve-undo.h
revision.c
revision.h
run-command.c
run-command.h
send-pack.c
send-pack.h
sequencer.c
sequencer.h
server-info.c
setup.c
sh-i18n--envsubst.c
sha1-array.c
sha1-array.h
sha1-lookup.c
sha1-lookup.h
sha1_file.c
sha1_name.c
shallow.c
shell.c
shortlog.h
show-index.c
sideband.c
sideband.h
sigchain.c
sigchain.h
split-index.c
split-index.h
strbuf.c
strbuf.h
streaming.c
streaming.h
string-list.c
string-list.h
submodule.c
submodule.h
symlinks.c
tag.c
tag.h
tar.h
test-chmtime.c
test-config.c
test-ctype.c
test-date.c
test-delta.c
test-dump-cache-tree.c
test-dump-split-index.c
test-genrandom.c
test-hashmap.c
test-index-version.c
test-line-buffer.c
test-match-trees.c
test-mergesort.c
test-mktemp.c
test-parse-options.c
test-path-utils.c
test-prio-queue.c
test-read-cache.c
test-regex.c
test-revision-walking.c
test-run-command.c
test-scrap-cache-tree.c
test-sha1.c
test-sha1.sh
test-sigchain.c
test-string-list.c
test-subprocess.c
test-svn-fe.c
test-urlmatch-normalization.c
test-wildmatch.c
thread-utils.c
thread-utils.h
trace.c
trace.h
transport-helper.c
transport.c
transport.h
tree-diff.c
tree-walk.c
tree-walk.h
tree.c
tree.h
unicode_width.h
unimplemented.sh
unix-socket.c
unix-socket.h
unpack-trees.c
unpack-trees.h
update_unicode.sh
upload-pack.c
url.c
url.h
urlmatch.c
urlmatch.h
usage.c
userdiff.c
userdiff.h
utf8.c
utf8.h
varint.c
varint.h
version.c
version.h
versioncmp.c
walker.c
walker.h
wildmatch.c
wildmatch.h
wrap-for-bin.sh
wrapper.c
write_or_die.c
ws.c
wt-status.c
wt-status.h
xdiff-interface.c
xdiff-interface.h
zlib.c
Breadcrumbs
git
/
test-hashmap.c
Blame
Blame
Latest commit
History
History
264 lines (214 loc) · 6.14 KB
Breadcrumbs
git
/
test-hashmap.c
Top
File metadata and controls
Code
Blame
264 lines (214 loc) · 6.14 KB
Raw
#include "git-compat-util.h" #include "hashmap.h" struct test_entry { struct hashmap_entry ent; /* key and value as two \0-terminated strings */ char key[FLEX_ARRAY]; }; static const char *get_value(const struct test_entry *e) { return e->key + strlen(e->key) + 1; } static int test_entry_cmp(const struct test_entry *e1, const struct test_entry *e2, const char* key) { return strcmp(e1->key, key ? key : e2->key); } static int test_entry_cmp_icase(const struct test_entry *e1, const struct test_entry *e2, const char* key) { return strcasecmp(e1->key, key ? key : e2->key); } static struct test_entry *alloc_test_entry(int hash, char *key, int klen, char *value, int vlen) { struct test_entry *entry = malloc(sizeof(struct test_entry) + klen + vlen + 2); hashmap_entry_init(entry, hash); memcpy(entry->key, key, klen + 1); memcpy(entry->key + klen + 1, value, vlen + 1); return entry; } #define HASH_METHOD_FNV 0 #define HASH_METHOD_I 1 #define HASH_METHOD_IDIV10 2 #define HASH_METHOD_0 3 #define HASH_METHOD_X2 4 #define TEST_SPARSE 8 #define TEST_ADD 16 #define TEST_SIZE 100000 static unsigned int hash(unsigned int method, unsigned int i, const char *key) { unsigned int hash; switch (method & 3) { case HASH_METHOD_FNV: hash = strhash(key); break; case HASH_METHOD_I: hash = i; break; case HASH_METHOD_IDIV10: hash = i / 10; break; case HASH_METHOD_0: hash = 0; break; } if (method & HASH_METHOD_X2) hash = 2 * hash; return hash; } /* * Test performance of hashmap.[ch] * Usage: time echo "perfhashmap method rounds" | test-hashmap */ static void perf_hashmap(unsigned int method, unsigned int rounds) { struct hashmap map; char buf[16]; struct test_entry **entries; unsigned int *hashes; unsigned int i, j; entries = malloc(TEST_SIZE * sizeof(struct test_entry *)); hashes = malloc(TEST_SIZE * sizeof(int)); for (i = 0; i < TEST_SIZE; i++) { snprintf(buf, sizeof(buf), "%i", i); entries[i] = alloc_test_entry(0, buf, strlen(buf), "", 0); hashes[i] = hash(method, i, entries[i]->key); } if (method & TEST_ADD) { /* test adding to the map */ for (j = 0; j < rounds; j++) { hashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, 0); /* add entries */ for (i = 0; i < TEST_SIZE; i++) { hashmap_entry_init(entries[i], hashes[i]); hashmap_add(&map, entries[i]); } hashmap_free(&map, 0); } } else { /* test map lookups */ hashmap_init(&map, (hashmap_cmp_fn) test_entry_cmp, 0); /* fill the map (sparsely if specified) */ j = (method & TEST_SPARSE) ? TEST_SIZE / 10 : TEST_SIZE; for (i = 0; i < j; i++) { hashmap_entry_init(entries[i], hashes[i]); hashmap_add(&map, entries[i]); } for (j = 0; j < rounds; j++) { for (i = 0; i < TEST_SIZE; i++) { hashmap_get_from_hash(&map, hashes[i], entries[i]->key); } } hashmap_free(&map, 0); } } #define DELIM " \t\r\n" /* * Read stdin line by line and print result of commands to stdout: * * hash key -> strhash(key) memhash(key) strihash(key) memihash(key) * put key value -> NULL / old value * get key -> NULL / value * remove key -> NULL / old value * iterate -> key1 value1\nkey2 value2\n... * size -> tablesize numentries * * perfhashmap method rounds -> test hashmap.[ch] performance */ int main(int argc, char *argv[]) { char line[1024]; struct hashmap map; int icase; /* init hash map */ icase = argc > 1 && !strcmp("ignorecase", argv[1]); hashmap_init(&map, (hashmap_cmp_fn) (icase ? test_entry_cmp_icase : test_entry_cmp), 0); /* process commands from stdin */ while (fgets(line, sizeof(line), stdin)) { char *cmd, *p1 = NULL, *p2 = NULL; int l1 = 0, l2 = 0, hash = 0; struct test_entry *entry; /* break line into command and up to two parameters */ cmd = strtok(line, DELIM); /* ignore empty lines */ if (!cmd || *cmd == '#') continue; p1 = strtok(NULL, DELIM); if (p1) { l1 = strlen(p1); hash = icase ? strihash(p1) : strhash(p1); p2 = strtok(NULL, DELIM); if (p2) l2 = strlen(p2); } if (!strcmp("hash", cmd) && l1) { /* print results of different hash functions */ printf("%u %u %u %u\n", strhash(p1), memhash(p1, l1), strihash(p1), memihash(p1, l1)); } else if (!strcmp("add", cmd) && l1 && l2) { /* create entry with key = p1, value = p2 */ entry = alloc_test_entry(hash, p1, l1, p2, l2); /* add to hashmap */ hashmap_add(&map, entry); } else if (!strcmp("put", cmd) && l1 && l2) { /* create entry with key = p1, value = p2 */ entry = alloc_test_entry(hash, p1, l1, p2, l2); /* add / replace entry */ entry = hashmap_put(&map, entry); /* print and free replaced entry, if any */ puts(entry ? get_value(entry) : "NULL"); free(entry); } else if (!strcmp("get", cmd) && l1) { /* lookup entry in hashmap */ entry = hashmap_get_from_hash(&map, hash, p1); /* print result */ if (!entry) puts("NULL"); while (entry) { puts(get_value(entry)); entry = hashmap_get_next(&map, entry); } } else if (!strcmp("remove", cmd) && l1) { /* setup static key */ struct hashmap_entry key; hashmap_entry_init(&key, hash); /* remove entry from hashmap */ entry = hashmap_remove(&map, &key, p1); /* print result and free entry*/ puts(entry ? get_value(entry) : "NULL"); free(entry); } else if (!strcmp("iterate", cmd)) { struct hashmap_iter iter; hashmap_iter_init(&map, &iter); while ((entry = hashmap_iter_next(&iter))) printf("%s %s\n", entry->key, get_value(entry)); } else if (!strcmp("size", cmd)) { /* print table sizes */ printf("%u %u\n", map.tablesize, map.size); } else if (!strcmp("intern", cmd) && l1) { /* test that strintern works */ const char *i1 = strintern(p1); const char *i2 = strintern(p1); if (strcmp(i1, p1)) printf("strintern(%s) returns %s\n", p1, i1); else if (i1 == p1) printf("strintern(%s) returns input pointer\n", p1); else if (i1 != i2) printf("strintern(%s) != strintern(%s)", i1, i2); else printf("%s\n", i1); } else if (!strcmp("perfhashmap", cmd) && l1 && l2) { perf_hashmap(atoi(p1), atoi(p2)); } else { printf("Unknown command %s\n", cmd); } } hashmap_free(&map, 1); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
You can’t perform that action at this time.