1 /* 2 * Copyright 2014 Square Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://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, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.squareup.okhttp.internal; 17 18 import java.util.ArrayList; 19 import java.util.Arrays; 20 import java.util.List; 21 22 import static java.lang.String.format; 23 24 /** A simple bitset which supports left shifting. */ 25 public interface BitArray { 26 clear()27 void clear(); 28 set(int index)29 void set(int index); 30 toggle(int index)31 void toggle(int index); 32 get(int index)33 boolean get(int index); 34 shiftLeft(int count)35 void shiftLeft(int count); 36 37 /** Bit set that only supports settings bits 0 - 63. */ 38 public final class FixedCapacity implements BitArray { 39 long data = 0x0000000000000000L; 40 clear()41 @Override public void clear() { 42 data = 0x0000000000000000L; 43 } 44 set(int index)45 @Override public void set(int index) { 46 data |= (1L << checkInput(index)); 47 } 48 toggle(int index)49 @Override public void toggle(int index) { 50 data ^= (1L << checkInput(index)); 51 } 52 get(int index)53 @Override public boolean get(int index) { 54 return ((data >> checkInput(index)) & 1L) == 1; 55 } 56 shiftLeft(int count)57 @Override public void shiftLeft(int count) { 58 data = data << checkInput(count); 59 } 60 toString()61 @Override public String toString() { 62 return Long.toBinaryString(data); 63 } 64 toVariableCapacity()65 public BitArray toVariableCapacity() { 66 return new VariableCapacity(this); 67 } 68 checkInput(int index)69 private static int checkInput(int index) { 70 if (index < 0 || index > 63) { 71 throw new IllegalArgumentException(format("input must be between 0 and 63: %s", index)); 72 } 73 return index; 74 } 75 } 76 77 /** Bit set that grows as needed. */ 78 public final class VariableCapacity implements BitArray { 79 80 long[] data; 81 82 // Start offset which allows for cheap shifting. Data is always kept on 64-bit bounds but we 83 // offset the outward facing index to support shifts without having to move the underlying bits. 84 private int start; // Valid values are [0..63] 85 VariableCapacity()86 public VariableCapacity() { 87 data = new long[1]; 88 } 89 VariableCapacity(FixedCapacity small)90 private VariableCapacity(FixedCapacity small) { 91 data = new long[] {small.data, 0}; 92 } 93 growToSize(int size)94 private void growToSize(int size) { 95 long[] newData = new long[size]; 96 if (data != null) { 97 System.arraycopy(data, 0, newData, 0, data.length); 98 } 99 data = newData; 100 } 101 offsetOf(int index)102 private int offsetOf(int index) { 103 index += start; 104 int offset = index / 64; 105 if (offset > data.length - 1) { 106 growToSize(offset + 1); 107 } 108 return offset; 109 } 110 shiftOf(int index)111 private int shiftOf(int index) { 112 return (index + start) % 64; 113 } 114 clear()115 @Override public void clear() { 116 Arrays.fill(data, 0); 117 } 118 set(int index)119 @Override public void set(int index) { 120 checkInput(index); 121 int offset = offsetOf(index); 122 data[offset] |= 1L << shiftOf(index); 123 } 124 toggle(int index)125 @Override public void toggle(int index) { 126 checkInput(index); 127 int offset = offsetOf(index); 128 data[offset] ^= 1L << shiftOf(index); 129 } 130 get(int index)131 @Override public boolean get(int index) { 132 checkInput(index); 133 int offset = offsetOf(index); 134 return (data[offset] & (1L << shiftOf(index))) != 0; 135 } 136 shiftLeft(int count)137 @Override public void shiftLeft(int count) { 138 start -= checkInput(count); 139 if (start < 0) { 140 int arrayShift = (start / -64) + 1; 141 long[] newData = new long[data.length + arrayShift]; 142 System.arraycopy(data, 0, newData, arrayShift, data.length); 143 data = newData; 144 start = 64 + (start % 64); 145 } 146 } 147 toString()148 @Override public String toString() { 149 StringBuilder builder = new StringBuilder("{"); 150 List<Integer> ints = toIntegerList(); 151 for (int i = 0, count = ints.size(); i < count; i++) { 152 if (i > 0) { 153 builder.append(','); 154 } 155 builder.append(ints.get(i)); 156 } 157 return builder.append('}').toString(); 158 } 159 toIntegerList()160 List<Integer> toIntegerList() { 161 List<Integer> ints = new ArrayList<Integer>(); 162 for (int i = 0, count = data.length * 64 - start; i < count; i++) { 163 if (get(i)) { 164 ints.add(i); 165 } 166 } 167 return ints; 168 } 169 checkInput(int index)170 private static int checkInput(int index) { 171 if (index < 0) { 172 throw new IllegalArgumentException(format("input must be a positive number: %s", index)); 173 } 174 return index; 175 } 176 } 177 } 178