/*
 * JBoss, Home of Professional Open Source.
 * Copyright 2014 Red Hat, Inc., and individual contributors
 * as indicated by the @author tags.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package io.undertow.util;

import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.RandomAccess;

An array-backed list/deque for header string values.
Author:David M. Lloyd
/** * An array-backed list/deque for header string values. * * @author <a href="mailto:david.lloyd@redhat.com">David M. Lloyd</a> */
public final class HeaderValues extends AbstractCollection<String> implements Deque<String>, List<String>, RandomAccess { private static final String[] NO_STRINGS = new String[0]; final HttpString key; byte size; Object value; HeaderValues(final HttpString key) { this.key = key; } public HttpString getHeaderName() { return key; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { final byte size = this.size; if (size == 0) return; clearInternal(); } private void clearInternal() { final Object value = this.value; if (value instanceof String[]) { final String[] strings = (String[]) value; final int len = strings.length; Arrays.fill(strings, 0, len, null); } else { this.value = null; } this.size = 0; } private int index(int idx) { assert idx >= 0; assert idx < size; final int len = ((String[]) value).length; if (idx > len) { idx -= len; } return idx; } public ListIterator<String> listIterator() { return iterator(0, true); } public ListIterator<String> listIterator(final int index) { return iterator(index, true); } public Iterator<String> iterator() { return iterator(0, true); } public Iterator<String> descendingIterator() { return iterator(0, false); } private ListIterator<String> iterator(final int start, final boolean forwards) { return new ListIterator<String>() { int idx = start; int returned = -1; public boolean hasNext() { return idx < size; } public boolean hasPrevious() { return idx > 0; } public String next() { try { final String next; if (forwards) { int idx = this.idx; next = get(idx); returned = idx; this.idx = idx + 1; return next; } else { int idx = this.idx - 1; next = get(idx); this.idx = returned = idx; } return next; } catch (IndexOutOfBoundsException e) { throw new NoSuchElementException(); } } public int nextIndex() { return idx; } public String previous() { try { final String prev; if (forwards) { int idx = this.idx - 1; prev = get(idx); this.idx = returned = idx; } else { int idx = this.idx; prev = get(idx); returned = idx; this.idx = idx + 1; return prev; } return prev; } catch (IndexOutOfBoundsException e) { throw new NoSuchElementException(); } } public int previousIndex() { return idx - 1; } public void remove() { if (returned == -1) { throw new IllegalStateException(); } HeaderValues.this.remove(returned); returned = -1; } public void set(final String headerValue) { if (returned == -1) { throw new IllegalStateException(); } HeaderValues.this.set(returned, headerValue); } public void add(final String headerValue) { if (returned == -1) { throw new IllegalStateException(); } final int idx = this.idx; HeaderValues.this.add(idx, headerValue); this.idx = idx + 1; returned = -1; } }; } public boolean offerFirst(final String headerValue) { int size = this.size; if (headerValue == null || size == Byte.MAX_VALUE) return false; final Object value = this.value; if (value instanceof String[]) { final String[] strings = (String[]) value; final int len = strings.length; if (size == len) { final String[] newStrings = new String[len + 2]; System.arraycopy(strings, 0, newStrings, 1, len); newStrings[0] = headerValue; this.value = newStrings; } else { System.arraycopy(strings, 0, strings, 1, strings.length - 1); strings[0] = headerValue; } this.size = (byte) (size + 1); } else { if (size == 0) { this.value = headerValue; this.size = (byte) 1; } else { this.value = new String[] { headerValue, (String) value, null, null }; this.size = (byte) 2; } } return true; } public boolean offerLast(final String headerValue) { int size = this.size; if (headerValue == null || size == Byte.MAX_VALUE) return false; final Object value = this.value; if (value instanceof String[]) { offerLastMultiValue(headerValue, size, (String[]) value); } else { if (size == 0) { this.value = headerValue; this.size = (byte) 1; } else { this.value = new String[] { (String) value, headerValue, null, null }; this.size = (byte) 2; } } return true; } private void offerLastMultiValue(String headerValue, int size, String[] value) { final String[] strings = value; final int len = strings.length; if (size == len) { final String[] newStrings = new String[len + 2]; System.arraycopy(strings, 0, newStrings, 0, len); newStrings[len] = headerValue; this.value = newStrings; } else { strings[size] = headerValue; } this.size = (byte) (size + 1); } private boolean offer(int idx, final String headerValue) { int size = this.size; if (idx < 0 || idx > size || size == Byte.MAX_VALUE || headerValue == null) return false; if (idx == 0) return offerFirst(headerValue); if (idx == size) return offerLast(headerValue); assert size >= 2; // must be >= 2 to pass the last two checks final Object value = this.value; assert value instanceof String[]; final String[] strings = (String[]) value; final int len = strings.length; // This stuff is all algebraically derived. if (size == len) { // Grow the list, copy each segment into new spots so that head = 0 final int newLen = len + 2; final String[] newStrings = new String[newLen]; System.arraycopy(value, 0, newStrings, 0, idx); System.arraycopy(value, idx, newStrings, idx + 1, len - idx); // finally fill in the new value newStrings[idx] = headerValue; this.value = newStrings; } else{ System.arraycopy(value, idx, value, idx + 1, len - idx); // finally fill in the new value strings[idx] = headerValue; } this.size = (byte) (size + 1); return true; } public String pollFirst() { final byte size = this.size; if (size == 0) return null; final Object value = this.value; if (value instanceof String) { this.size = 0; this.value = null; return (String) value; } else { final String[] strings = (String[]) value; String ret = strings[0]; System.arraycopy(strings, 1, strings, 0, strings.length - 1); this.size = (byte) (size - 1); return ret; } } public String pollLast() { final byte size = this.size; if (size == 0) return null; final Object value = this.value; if (value instanceof String) { this.size = 0; this.value = null; return (String) value; } else { final String[] strings = (String[]) value; int idx = (this.size = (byte) (size - 1)); final int len = strings.length; if (idx > len) idx -= len; try { return strings[idx]; } finally { strings[idx] = null; } } } public String remove(int idx) { final int size = this.size; if (idx < 0 || idx >= size) throw new IndexOutOfBoundsException(); if (idx == 0) return removeFirst(); if (idx == size - 1) return removeLast(); assert size > 2; // must be > 2 to pass the last two checks // value must be an array since size > 2 final String[] value = (String[]) this.value; final int len = value.length; String ret = value[idx]; System.arraycopy(value, idx + 1, value, idx, len - idx - 1); value[len - 1] = null; this.size = (byte) (size - 1); return ret; } public String get(int idx) { if (idx > size) { throw new IndexOutOfBoundsException(); } Object value = this.value; assert value != null; if (value instanceof String) { assert size == 1; return (String) value; } final String[] a = (String[]) value; return a[index(idx)]; } public int indexOf(final Object o) { if (o == null || size == 0) return -1; if (value instanceof String[]) { final String[] list = (String[]) value; final int len = list.length; for (int i = 0; i < size; i ++) { if ((i > len ? list[i - len] : list[i]).equals(o)) { return i; } } } else if (o.equals(value)) { return 0; } return -1; } public int lastIndexOf(final Object o) { if (o == null || size == 0) return -1; if (value instanceof String[]) { final String[] list = (String[]) value; final int len = list.length; int idx; for (int i = size - 1; i >= 0; i --) { idx = i; if ((idx > len ? list[idx - len] : list[idx]).equals(o)) { return i; } } } else if (o.equals(value)) { return 0; } return -1; } public String set(final int index, final String element) { if (element == null) throw new IllegalArgumentException(); final byte size = this.size; if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); final Object value = this.value; if (size == 1 && value instanceof String) try { return (String) value; } finally { this.value = element; } else { final String[] list = (String[]) value; final int i = index(index); try { return list[i]; } finally { list[i] = element; } } } public boolean addAll(int index, final Collection<? extends String> c) { final int size = this.size; if (index < 0 || index > size) throw new IndexOutOfBoundsException(); final Iterator<? extends String> iterator = c.iterator(); boolean result = false; while (iterator.hasNext()) { result |= offer(index, iterator.next()); } return result; } public List<String> subList(final int fromIndex, final int toIndex) { // todo - this is about 75% correct, by spec... if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) throw new IndexOutOfBoundsException(); final int len = toIndex - fromIndex; final String[] strings = new String[len]; for (int i = 0; i < len; i ++) { strings[i] = get(i + fromIndex); } return Arrays.asList(strings); } public String[] toArray() { int size = this.size; if (size == 0) { return NO_STRINGS; } final Object v = this.value; if (v instanceof String) return new String[] { (String) v }; final String[] list = (String[]) v; final int len = list.length; final int copyEnd = size; if (copyEnd < len) { return Arrays.copyOfRange(list, 0, copyEnd); } else { String[] ret = Arrays.copyOfRange(list, 0, copyEnd); System.arraycopy(list, 0, ret, len, copyEnd - len); return ret; } } public <T> T[] toArray(final T[] a) { int size = this.size; if (size == 0) return a; final int inLen = a.length; final Object[] target = inLen < size ? Arrays.copyOfRange(a, inLen, inLen + size) : a; final Object v = this.value; if (v instanceof String) { target[0] = v; } else { System.arraycopy(v, 0, target, 0, size); } return (T[]) target; } //====================================== // // Derived methods // //====================================== public void addFirst(final String s) { if (s == null) return; if (! offerFirst(s)) throw new IllegalStateException(); } public void addLast(final String s) { if (s == null) return; if (! offerLast(s)) throw new IllegalStateException(); } public void add(final int index, final String s) { if (s == null) return; if (! offer(index, s)) throw new IllegalStateException(); } public boolean contains(final Object o) { return indexOf(o) != -1; } public String peekFirst() { return size == 0 ? null : get(0); } public String peekLast() { return size == 0 ? null : get(size - 1); } public boolean removeFirstOccurrence(final Object o) { int i = indexOf(o); return i != -1 && remove(i) != null; } public boolean removeLastOccurrence(final Object o) { int i = lastIndexOf(o); return i != -1 && remove(i) != null; } public boolean add(final String s) { addLast(s); return true; } public void push(final String s) { addFirst(s); } public String pop() { return removeFirst(); } public boolean offer(final String s) { return offerLast(s); } public String poll() { return pollFirst(); } public String peek() { return peekFirst(); } public String remove() { return removeFirst(); } public String removeFirst() { final String s = pollFirst(); if (s == null) { throw new NoSuchElementException(); } return s; } public String removeLast() { final String s = pollLast(); if (s == null) { throw new NoSuchElementException(); } return s; } public String getFirst() { final String s = peekFirst(); if (s == null) { throw new NoSuchElementException(); } return s; } public String getLast() { final String s = peekLast(); if (s == null) { throw new NoSuchElementException(); } return s; } public String element() { return getFirst(); } public boolean remove(Object obj) { return removeFirstOccurrence(obj); } public boolean addAll(final Collection<? extends String> c) { for (String s : c) { add(s); } return !c.isEmpty(); } }