1 /*
2 * Copyright (C) 2009, Google Inc.
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43
44 package org.eclipse.jgit.transport;
45
46 /**
47 * Simple Map<long,Object> helper for {@link PackParser}.
48 *
49 * @param <V>
50 * type of the value instance.
51 */
52 final class LongMap<V> {
53 private static final float LOAD_FACTOR = 0.75f;
54
55 private Node<V>[] table;
56
57 /** Number of entries currently in the map. */
58 private int size;
59
60 /** Next {@link #size} to trigger a {@link #grow()}. */
61 private int growAt;
62
63 LongMap() {
64 table = createArray(64);
65 growAt = (int) (table.length * LOAD_FACTOR);
66 }
67
68 boolean containsKey(final long key) {
69 return get(key) != null;
70 }
71
72 V get(final long key) {
73 for (Node<V> n = table[index(key)]; n != null; n = n.next) {
74 if (n.key == key)
75 return n.value;
76 }
77 return null;
78 }
79
80 V remove(final long key) {
81 Node<V> n = table[index(key)];
82 Node<V> prior = null;
83 while (n != null) {
84 if (n.key == key) {
85 if (prior == null)
86 table[index(key)] = n.next;
87 else
88 prior.next = n.next;
89 size--;
90 return n.value;
91 }
92 prior = n;
93 n = n.next;
94 }
95 return null;
96 }
97
98 V put(final long key, final V value) {
99 for (Node<V> n = table[index(key)]; n != null; n = n.next) {
100 if (n.key == key) {
101 final V o = n.value;
102 n.value = value;
103 return o;
104 }
105 }
106
107 if (++size == growAt)
108 grow();
109 insert(new Node<V>(key, value));
110 return null;
111 }
112
113 private void insert(final Node<V> n) {
114 final int idx = index(n.key);
115 n.next = table[idx];
116 table[idx] = n;
117 }
118
119 private void grow() {
120 final Node<V>[] oldTable = table;
121 final int oldSize = table.length;
122
123 table = createArray(oldSize << 1);
124 growAt = (int) (table.length * LOAD_FACTOR);
125 for (int i = 0; i < oldSize; i++) {
126 Node<V> e = oldTable[i];
127 while (e != null) {
128 final Node<V> n = e.next;
129 insert(e);
130 e = n;
131 }
132 }
133 }
134
135 private final int index(final long key) {
136 int h = ((int) key) >>> 1;
137 h ^= (h >>> 20) ^ (h >>> 12);
138 return h & (table.length - 1);
139 }
140
141 @SuppressWarnings("unchecked")
142 private static final <V> Node<V>[] createArray(final int sz) {
143 return new Node[sz];
144 }
145
146 private static class Node<V> {
147 final long key;
148
149 V value;
150
151 Node<V> next;
152
153 Node(final long k, final V v) {
154 key = k;
155 value = v;
156 }
157 }
158 }