View Javadoc
1   /*
2    * Copyright 2020 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  package io.netty.buffer;
17  
18  /**
19   * Internal primitive map implementation that is specifically optimised for the runs availability map use case in {@link
20   * PoolChunk}.
21   */
22  final class LongLongHashMap {
23      private static final int MASK_TEMPLATE = ~1;
24      private int mask;
25      private long[] array;
26      private int maxProbe;
27      private long zeroVal;
28      private final long emptyVal;
29  
30      LongLongHashMap(long emptyVal) {
31          this.emptyVal = emptyVal;
32          zeroVal = emptyVal;
33          int initialSize = 32;
34          array = new long[initialSize];
35          mask = initialSize - 1;
36          computeMaskAndProbe();
37      }
38  
39      public long put(long key, long value) {
40          if (key == 0) {
41              long prev = zeroVal;
42              zeroVal = value;
43              return prev;
44          }
45  
46          for (;;) {
47              int index = index(key);
48              for (int i = 0; i < maxProbe; i++) {
49                  long existing = array[index];
50                  if (existing == key || existing == 0) {
51                      long prev = existing == 0? emptyVal : array[index + 1];
52                      array[index] = key;
53                      array[index + 1] = value;
54                      for (; i < maxProbe; i++) { // Nerf any existing misplaced entries.
55                          index = index + 2 & mask;
56                          if (array[index] == key) {
57                              array[index] = 0;
58                              prev = array[index + 1];
59                              break;
60                          }
61                      }
62                      return prev;
63                  }
64                  index = index + 2 & mask;
65              }
66              expand(); // Grow array and re-hash.
67          }
68      }
69  
70      public void remove(long key) {
71          if (key == 0) {
72              zeroVal = emptyVal;
73              return;
74          }
75          int index = index(key);
76          for (int i = 0; i < maxProbe; i++) {
77              long existing = array[index];
78              if (existing == key) {
79                  array[index] = 0;
80                  break;
81              }
82              index = index + 2 & mask;
83          }
84      }
85  
86      public long get(long key) {
87          if (key == 0) {
88              return zeroVal;
89          }
90          int index = index(key);
91          for (int i = 0; i < maxProbe; i++) {
92              long existing = array[index];
93              if (existing == key) {
94                  return array[index + 1];
95              }
96              index = index + 2 & mask;
97          }
98          return emptyVal;
99      }
100 
101     private int index(long key) {
102         // Hash with murmur64, and mask.
103         key ^= key >>> 33;
104         key *= 0xff51afd7ed558ccdL;
105         key ^= key >>> 33;
106         key *= 0xc4ceb9fe1a85ec53L;
107         key ^= key >>> 33;
108         return (int) key & mask;
109     }
110 
111     private void expand() {
112         long[] prev = array;
113         array = new long[prev.length * 2];
114         computeMaskAndProbe();
115         for (int i = 0; i < prev.length; i += 2) {
116             long key = prev[i];
117             if (key != 0) {
118                 long val = prev[i + 1];
119                 put(key, val);
120             }
121         }
122     }
123 
124     private void computeMaskAndProbe() {
125         int length = array.length;
126         mask = length - 1 & MASK_TEMPLATE;
127         maxProbe = (int) Math.log(length);
128     }
129 }