org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java

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