Mercurial > jhg

comparison src/org/tmatesoft/hg/util/DirectHashSet.java @ 304:85b8efde5586

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use memory-friendly set implementation to canonicalize filenames and nodeids
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 21 Sep 2011 18:26:16 +0200
parents
children 51d682cf9cdc
comparison
equal deleted inserted replaced
303:2ffcbf360fd5 304:85b8efde5586
1 /*
2 * Copyright (c) 2011 TMate Software Ltd
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 2 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * For information on how to redistribute this software under
14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@hg4j.com
16 */
17 package org.tmatesoft.hg.util;
18
19 import org.tmatesoft.hg.internal.Experimental;
20
21 /**
22 * Memory-friendly alternative to HashSet. With slightly worse performance than that of HashSet, uses n * sizeof(HashMap.Entry) less memory
23 * (i.e. for set of 50k elements saves more than 1 Mb of memory). Besides, elements of this set can be obtained (not only queried for presence) -
24 * the option essential for canonical mappings (aka Pool)
25 *
26 * @author Artem Tikhomirov
27 * @author TMate Software Ltd.
28 */
29 @Experimental
30 public class DirectHashSet<T> {
31
32 private Object[] table;
33 private int size;
34 private int threshold;
35
36 public DirectHashSet() {
37 this (16);
38 }
39
40 public DirectHashSet(int capacity) {
41 int result = 2;
42 while (result < capacity) {
43 result <<= 1;
44 }
45 table = new Object[result];
46 threshold = result - (result >>> 2);
47 }
48
49 /**
50 * Add element to the set.
51 * @param o element, shall not be <code>null</code>
52 * @return previous element from the set equal to the argument
53 */
54 @SuppressWarnings("unchecked")
55 public T put(T o) {
56 final int h = hash(o);
57 final int mask = table.length - 1;
58 int i = h & mask;
59 Object t;
60 while ((t = table[i]) != null) {
61 if (t.equals(o)) {
62 table[i] = o;
63 return (T) t;
64 }
65 i = (i+1) & mask;
66 }
67 table[i] = o;
68 if (++size >= threshold) {
69 resize();
70 }
71 return null;
72 }
73
74 /**
75 * Query set for the element.
76 * @param o element, shall not be <code>null</code>
77 * @return element from the set, if present
78 */
79 @SuppressWarnings("unchecked")
80 public T get(T o) {
81 final int h = hash(o);
82 final int mask = table.length - 1;
83 int i = h & mask;
84 Object t;
85 while ((t = table[i]) != null) {
86 if (t == o || t.equals(o)) {
87 return (T) t;
88 }
89 i = (i+1) & mask;
90 }
91 return null;
92 }
93
94 public int size() {
95 return size;
96 }
97
98 public void clear() {
99 Object[] t = table;
100 for (int i = 0, top = t.length; i < top; i++) {
101 t[i] = null;
102 }
103 size = 0;
104 }
105
106 private void resize() {
107 final int newSize = table.length << 1;
108 final int newMask = newSize - 1;
109 Object[] newTable = new Object[newSize];
110 for (int i = 0, size = table.length; i < size; i++) {
111 Object t = table[i];
112 if (t != null) {
113 table[i] = null;
114 int x = hash(t) & newMask;
115 while (newTable[x] != null) {
116 x = (x+1) & newMask;
117 }
118 newTable[x] = t;
119 }
120 }
121 table = newTable;
122 threshold = newSize - (newSize >>> 2);
123 }
124
125 private static int hash(Object o) {
126 int h = o.hashCode();
127 // return h;
128 // HashMap.newHash()
129 h ^= (h >>> 20) ^ (h >>> 12);
130 return h ^ (h >>> 7) ^ (h >>> 4);
131 }
132
133 }