1 package com.fasterxml.jackson.databind.util; 2 3 /** 4 * Base class for specialized primitive array builders. 5 */ 6 public abstract class PrimitiveArrayBuilder<T> 7 { 8 /** 9 * Let's start with small chunks; typical usage is for small arrays anyway. 10 */ 11 final static int INITIAL_CHUNK_SIZE = 12; 12 13 /** 14 * Also: let's expand by doubling up until 64k chunks (which is 16k entries for 15 * 32-bit machines) 16 */ 17 final static int SMALL_CHUNK_SIZE = (1 << 14); 18 19 /** 20 * Let's limit maximum size of chunks we use; helps avoid excessive allocation 21 * overhead for huge data sets. 22 * For now, let's limit to quarter million entries, 1 meg chunks for 32-bit 23 * machines. 24 */ 25 final static int MAX_CHUNK_SIZE = (1 << 18); 26 27 // // // Data storage 28 29 protected T _freeBuffer; 30 31 protected Node<T> _bufferHead; 32 33 protected Node<T> _bufferTail; 34 35 /** 36 * Number of total buffered entries in this buffer, counting all instances 37 * within linked list formed by following {@link #_bufferHead}. 38 */ 39 protected int _bufferedEntryCount; 40 41 // // // Recycled instances of sub-classes 42 43 // // // Life-cycle 44 PrimitiveArrayBuilder()45 protected PrimitiveArrayBuilder() { } 46 47 /* 48 /********************************************************** 49 /* Public API 50 /********************************************************** 51 */ 52 bufferedSize()53 public int bufferedSize() { return _bufferedEntryCount; } 54 resetAndStart()55 public T resetAndStart() 56 { 57 _reset(); 58 return (_freeBuffer == null) ? 59 _constructArray(INITIAL_CHUNK_SIZE) : _freeBuffer; 60 } 61 62 /** 63 * @return Length of the next chunk to allocate 64 */ appendCompletedChunk(T fullChunk, int fullChunkLength)65 public final T appendCompletedChunk(T fullChunk, int fullChunkLength) 66 { 67 Node<T> next = new Node<T>(fullChunk, fullChunkLength); 68 if (_bufferHead == null) { // first chunk 69 _bufferHead = _bufferTail = next; 70 } else { // have something already 71 _bufferTail.linkNext(next); 72 _bufferTail = next; 73 } 74 _bufferedEntryCount += fullChunkLength; 75 int nextLen = fullChunkLength; // start with last chunk size 76 // double the size for small chunks 77 if (nextLen < SMALL_CHUNK_SIZE) { 78 nextLen += nextLen; 79 } else { // but by +25% for larger (to limit overhead) 80 nextLen += (nextLen >> 2); 81 } 82 return _constructArray(nextLen); 83 } 84 completeAndClearBuffer(T lastChunk, int lastChunkEntries)85 public T completeAndClearBuffer(T lastChunk, int lastChunkEntries) 86 { 87 int totalSize = lastChunkEntries + _bufferedEntryCount; 88 T resultArray = _constructArray(totalSize); 89 90 int ptr = 0; 91 92 for (Node<T> n = _bufferHead; n != null; n = n.next()) { 93 ptr = n.copyData(resultArray, ptr); 94 } 95 System.arraycopy(lastChunk, 0, resultArray, ptr, lastChunkEntries); 96 ptr += lastChunkEntries; 97 98 // sanity check (could have failed earlier due to out-of-bounds, too) 99 if (ptr != totalSize) { 100 throw new IllegalStateException("Should have gotten "+totalSize+" entries, got "+ptr); 101 } 102 return resultArray; 103 } 104 105 /* 106 /********************************************************** 107 /* Abstract methods for sub-classes to implement 108 /********************************************************** 109 */ 110 _constructArray(int len)111 protected abstract T _constructArray(int len); 112 113 /* 114 /********************************************************** 115 /* Internal methods 116 /********************************************************** 117 */ 118 _reset()119 protected void _reset() 120 { 121 // can we reuse the last (and thereby biggest) array for next time? 122 if (_bufferTail != null) { 123 _freeBuffer = _bufferTail.getData(); 124 } 125 // either way, must discard current contents 126 _bufferHead = _bufferTail = null; 127 _bufferedEntryCount = 0; 128 } 129 130 /* 131 /********************************************************** 132 /* Helper classes 133 /********************************************************** 134 */ 135 136 /** 137 * For actual buffering beyond the current buffer, we can actually 138 * use shared class which only deals with opaque "untyped" chunks. 139 * This works because {@link java.lang.System#arraycopy} does not 140 * take type; hence we can implement some aspects of primitive data 141 * handling in generic fashion. 142 */ 143 final static class Node<T> 144 { 145 /** 146 * Data stored in this node. 147 */ 148 final T _data; 149 150 /** 151 * Number entries in the (untyped) array. Offset is assumed to be 0. 152 */ 153 final int _dataLength; 154 155 Node<T> _next; 156 Node(T data, int dataLen)157 public Node(T data, int dataLen) 158 { 159 _data = data; 160 _dataLength = dataLen; 161 } 162 getData()163 public T getData() { return _data; } 164 copyData(T dst, int ptr)165 public int copyData(T dst, int ptr) 166 { 167 System.arraycopy(_data, 0, dst, ptr, _dataLength); 168 ptr += _dataLength; 169 return ptr; 170 } 171 next()172 public Node<T> next() { return _next; } 173 linkNext(Node<T> next)174 public void linkNext(Node<T> next) 175 { 176 if (_next != null) { // sanity check 177 throw new IllegalStateException(); 178 } 179 _next = next; 180 } 181 } 182 } 183