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 */
16package com.squareup.okhttp.internal;
17
18import java.util.ArrayList;
19import java.util.Arrays;
20import java.util.List;
21
22import static java.lang.String.format;
23
24/** A simple bitset which supports left shifting. */
25public interface BitArray {
26
27  void clear();
28
29  void set(int index);
30
31  void toggle(int index);
32
33  boolean get(int index);
34
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
41    @Override public void clear() {
42      data = 0x0000000000000000L;
43    }
44
45    @Override public void set(int index) {
46      data |= (1L << checkInput(index));
47    }
48
49    @Override public void toggle(int index) {
50      data ^= (1L << checkInput(index));
51    }
52
53    @Override public boolean get(int index) {
54      return ((data >> checkInput(index)) & 1L) == 1;
55    }
56
57    @Override public void shiftLeft(int count) {
58      data = data << checkInput(count);
59    }
60
61    @Override public String toString() {
62      return Long.toBinaryString(data);
63    }
64
65    public BitArray toVariableCapacity() {
66      return new VariableCapacity(this);
67    }
68
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
86    public VariableCapacity() {
87      data = new long[1];
88    }
89
90    private VariableCapacity(FixedCapacity small) {
91      data = new long[] {small.data, 0};
92    }
93
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
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
111    private int shiftOf(int index) {
112      return (index + start) % 64;
113    }
114
115    @Override public void clear() {
116      Arrays.fill(data, 0);
117    }
118
119    @Override public void set(int index) {
120      checkInput(index);
121      int offset = offsetOf(index);
122      data[offset] |= 1L << shiftOf(index);
123    }
124
125    @Override public void toggle(int index) {
126      checkInput(index);
127      int offset = offsetOf(index);
128      data[offset] ^= 1L << shiftOf(index);
129    }
130
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
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
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
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
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