Mercurial > jhg

annotate src/org/tmatesoft/hg/util/SparseSet.java @ 260:61cb6724ff36

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Experimental alternative to HashMap in Pool to reduce memory footprint
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 17 Aug 2011 02:35:15 +0200
parents
children 6bb5e7ed051a
rev   line source
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2011 TMate Software Ltd
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.util;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 import org.tmatesoft.hg.internal.Experimental;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 /**
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22 * WORK IN PROGRESS, DO NOT USE
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 * Memory-friendly alternative to HashMap-backed Pool. Set where object can be obtained (not only queried for presence)
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 * cpython repo, use of HashMap Pool results in ~6 Mb of Map.Entry and Map.Entry[],
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 * while use of SparseSet result in 2 Mb.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * @author Artem Tikhomirov
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 * @author TMate Software Ltd.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 */
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 @Experimental(reason="Requires tuning to accomodate to collection size. Present state (6-6-6) is too much for a lot of uses")
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 public class SparseSet<T> {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 public static void main(String[] args) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 SparseSet<String> ss = new SparseSet<String>();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 String one = Integer.toString(156), two = Integer.toString(1024), three = Integer.toString(1123123);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 ss.put(one);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 ss.put(two);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 ss.put(three);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 System.out.println(one == ss.get(one));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 System.out.println(two == ss.get(two));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 System.out.println(three == ss.get(three));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 System.out.println(null == ss.get("one"));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 System.out.println(one == ss.get(Integer.toString(156)));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 System.out.println(two == ss.get(Integer.toString(1024)));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 System.out.println(three == ss.get(Integer.toString(1123123)));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 ss.dump();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 private static class IndexBranch {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51 private final LeafBranch[] leafs = new LeafBranch[64];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 private static class LeafBranch {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
54 private final Object[] data = new Object[64];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
55 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
56
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 private final int[] fixups = new int[] {0x1, 0x10, 0xA, 0xD, 0x1F }; // rehash attempts
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 private final IndexBranch[] level2 = new IndexBranch[64];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
59 private int size = 0;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61 public void put(T o) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 int hash = o.hashCode();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
63 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 // 8 bits per level
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 // int i1 = (hash >>> 24) & 0xFF, i2 = (hash >>> 16) & 0xFF , i3 = (hash >>> 8) & 0xFF, i4 = hash & 0xFF;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 // 10, 8, 8 and 6 bits
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 // final int i1 = (hash >>> 22) & 0x3FF, i2 = (hash >>> 14) & 0xFF , i3 = (hash >>> 6) & 0xFF, i4 = hash & 0x3F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 // 8, 6, 6, 6, 6
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 // 10, 6, 6, 6, 4
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 // 6, 5, 5, 5 = 21 bit
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 // hash = hash ^ (hash >>> 24); // incorporate upper byte we don't use into lower to value it
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 // final int i1 = (hash >>> 18) & 0x3F, i2 = (hash >>> 12) & 0x1F , i3 = (hash >>> 7) & 0x1F, i4 = (hash >>> 2) & 0x1F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 // 6, 5, 5
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 // hash = hash ^ (hash >>> 16);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 // final int i1 = (hash >>> 10) & 0x3F, i2 = (hash >>> 5) & 0x1F , i3 = hash & 0x1F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 // 6, 6, 6
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 LeafBranch l3 = leafBranchPut(i1, i2);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 if (l3.data[i3] == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 l3.data[i3] = o;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 size++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 return;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 int neighbour = (i3+1) & 0x3F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 if (l3.data[neighbour] == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90 l3.data[neighbour] = o;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 size++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 return;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 int conflictCount = 0;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 for (int fixup : fixups) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 // if (showConflicts) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 // System.out.printf("(fixup: 0x%x) ", fixup);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 // }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 l3 = leafBranchPut(i1 ^ fixup, i2);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 conflictCount++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 if (l3.data[i3] != null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 // if (showConflicts) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 // System.out.printf("i1 failed ");
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 // }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 l3 = leafBranchPut(i1, i2 ^ fixup);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 conflictCount++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 // if (showConflicts) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 // System.out.printf("i2 %s ", (l3.data[i3] == null) ? "ok" : "failed");
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 // }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 // } else {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 // if (showConflicts) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 // System.out.printf("i1 ok");
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 // }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 // if (showConflicts) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 // System.out.println();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 // }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 if (l3.data[i3] == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 l3.data[i3] = o;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 // System.out.printf("Resolved conflict in %d steps (fixup 0x%X)\n", conflictCount, fixup);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121 size++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122 return;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
123 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 throw new IllegalStateException(String.valueOf(o));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 @SuppressWarnings("unchecked")
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 public T get(T o) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 int hash = o.hashCode();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 //hash = hash ^ (hash >>> 16);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 LeafBranch l3 = leafBranchGet(i1, i2);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
135 if (l3 == null || l3.data[i3] == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 if (o.equals(l3.data[i3])) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 return (T) l3.data[i3];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
140 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
141 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
142 int neighbour = (i3+1) & 0x3F;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
143 if (o.equals(l3.data[neighbour])) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
144 return (T) l3.data[neighbour];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
145 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
146
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
148 // resolve conflict
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149 for (int fixup : fixups) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
150 Object data = leafValueGet(i1 ^ fixup, i2, i3);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
151 if (data == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
152 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
153 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
154 if (o.equals(data)) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155 return (T)data;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
156 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
157 data = leafValueGet(i1, i2 ^ fixup, i3);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
158 if (data == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
159 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
160 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
161 if (o.equals(data)) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
162 return (T)data;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
163 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
164 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
165 dump();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
166 throw new IllegalStateException(String.format("[%d,%d,%d] hash: 0x%X, hash2: 0x%X, %s", i1, i2, i3, o.hashCode(), hash, o));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
167 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
168
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
169 public int size() {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
170 return size;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
171 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
172 private LeafBranch leafBranchPut(int i1, int i2) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
173 IndexBranch l2 = level2[i1];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
174 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
175 level2[i1] = l2 = new IndexBranch();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
176 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
177 LeafBranch l3 = l2.leafs[i2];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
178 if (l3 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
179 l2.leafs[i2] = l3 = new LeafBranch();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
180 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
181 return l3;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
182 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
183
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
184 private LeafBranch leafBranchGet(int i1, int i2) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
185 IndexBranch l2 = level2[i1];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
186 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
187 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
188 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
189 return l2.leafs[i2];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
190 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
191
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
192 private Object leafValueGet(int i1, int i2, int i3) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
193 IndexBranch l2 = level2[i1];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
194 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
195 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
196 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
197 LeafBranch l3 = l2.leafs[i2];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
198 if (l3 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
199 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
200 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
201 return l3.data[i3];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
202 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
203
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
204 public void dump() {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
205 int count = 0;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
206 for (int i = 0; i < level2.length; i++) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
207 IndexBranch l2 = level2[i];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
208 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
209 continue;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
210 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
211 for (int j = 0; j < l2.leafs.length; j++) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
212 LeafBranch l3 = l2.leafs[j];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
213 if (l3 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
214 continue;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
215 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
216 for (int k = 0; k < l3.data.length; k++) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
217 Object d = l3.data[k];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
218 if (d != null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
219 System.out.printf("[%3d,%3d,%3d] %s\n", i,j,k,d);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
220 count++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
221 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
222 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
223 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
224 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
225 System.out.printf("Total: %d elements", count);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
226 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
227 }