1 package com.fasterxml.jackson.databind.util;
2
3 import java.util.*;
4
5 /**
6  * Specialized lookup class that implements functionality similar to
7  * {@link java.util.Map}, but for special case of key always being
8  * {@link java.lang.String} and using more compact (and memory-access
9  * friendly) hashing scheme. Assumption is also that keys are typically
10  * intern()ed.
11  *<p>
12  * Generics are not used to avoid bridge methods and since these maps
13  * are not exposed as part of external API.
14  *
15  * @since 2.6
16  */
17 public final class CompactStringObjectMap
18     implements java.io.Serializable // since 2.6.2
19 {
20     private static final long serialVersionUID = 1L;
21
22     /**
23      * Shared instance that can be used when there are no contents to Map.
24      */
25     private final static CompactStringObjectMap EMPTY = new CompactStringObjectMap(1, 0,
26             new Object[4]);
27     
28     private final int _hashMask, _spillCount;
29
30     private final Object[] _hashArea;
31
32     private CompactStringObjectMap(int hashMask, int spillCount, Object[] hashArea)
33     {
34         _hashMask = hashMask;
35         _spillCount = spillCount;
36         _hashArea = hashArea;
37     }
38
39     public static <T> CompactStringObjectMap construct(Map<String,T> all)
40     {
41         if (all.isEmpty()) { // can this happen?
42             return EMPTY;
43         }
44
45         // First: calculate size of primary hash area
46         final int size = findSize(all.size());
47         final int mask = size-1;
48         // and allocate enough to contain primary/secondary, expand for spillovers as need be
49         int alloc = (size + (size>>1)) * 2;
50         Object[] hashArea = new Object[alloc];
51         int spillCount = 0;
52
53         for (Map.Entry<String,T> entry : all.entrySet()) {
54             String key = entry.getKey();
55
56             // 09-Sep-2019, tatu: [databind#2309] skip `null`s if any included
57             if (key == null) {
58                 continue;
59             }
60             
61             int slot = key.hashCode() & mask;
62             int ix = slot+slot;
63
64             // primary slot not free?
65             if (hashArea[ix] != null) {
66                 // secondary?
67                 ix = (size + (slot >> 1)) << 1;
68                 if (hashArea[ix] != null) {
69                     // ok, spill over.
70                     ix = ((size + (size >> 1) ) << 1) + spillCount;
71                     spillCount += 2;
72                     if (ix >= hashArea.length) {
73                         hashArea = Arrays.copyOf(hashArea, hashArea.length + 4);
74                     }
75                 }
76             }
77             hashArea[ix] = key;
78             hashArea[ix+1] = entry.getValue();
79         }
80         return new CompactStringObjectMap(mask, spillCount, hashArea);
81     }
82
83     private final static int findSize(int size)
84     {
85         if (size <= 5) {
86             return 8;
87         }
88         if (size <= 12) {
89             return 16;
90         }
91         int needed = size + (size >> 2); // at most 80% full
92         int result = 32;
93         while (result < needed) {
94             result += result;
95         }
96         return result;
97     }
98
99     public Object find(String key) {
100         int slot = key.hashCode() & _hashMask;
101         int ix = (slot<<1);
102         Object match = _hashArea[ix];
103         if ((match == key) || key.equals(match)) {
104             return _hashArea[ix+1];
105         }
106         return _find2(key, slot, match);
107     }
108
109     private final Object _find2(String key, int slot, Object match)
110     {
111         if (match == null) {
112             return null;
113         }
114         int hashSize = _hashMask+1;
115         int ix = hashSize + (slot>>1) << 1;
116         match = _hashArea[ix];
117         if (key.equals(match)) {
118             return _hashArea[ix+1];
119         }
120         if (match != null) { // _findFromSpill(...)
121             int i = (hashSize + (hashSize>>1)) << 1;
122             for (int end = i + _spillCount; i < end; i += 2) {
123                 match = _hashArea[i];
124                 if ((match == key) || key.equals(match)) {
125                     return _hashArea[i+1];
126                 }
127             }
128         }
129         return null;
130     }
131
132     /**
133      * @since 2.9
134      */
135     public Object findCaseInsensitive(String key) {
136         for (int i = 0, end = _hashArea.length; i < end; i += 2) {
137             Object k2 = _hashArea[i];
138             if (k2 != null) {
139                 String s = (String) k2;
140                 if (s.equalsIgnoreCase(key)) {
141                     return _hashArea[i+1];
142                 }
143             }
144         }
145         return null;
146     }
147     
148     public List<String> keys() {
149         final int end = _hashArea.length;
150         List<String> keys = new ArrayList<String>(end >> 2);
151         for (int i = 0; i < end; i += 2) {
152             Object key = _hashArea[i];
153             if (key != null) {
154                 keys.add((String) key);
155             }
156         }
157         return keys;
158     }
159 }
160