src/com/facebook/buck/apple/clang/HeaderMap.java - buck - Git at Google

 /*
  * Copyright 2014-present Facebook, Inc.
  *
  * 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 com.facebook.buck.apple.clang;

 import static java.lang.Math.max;

 import com.google.common.base.Ascii;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.Maps;

 import java.io.File;
 import java.io.FileInputStream;
 import java.io.IOException;
 import java.nio.ByteBuffer;
 import java.nio.ByteOrder;
 import java.nio.channels.FileChannel;
 import java.nio.charset.Charset;
 import java.nio.charset.StandardCharsets;
 import java.nio.file.Path;
 import java.util.Map;

 import javax.annotation.Nullable;

 /**
  * Header maps are essentially hash maps from strings to paths (coded as two strings: a prefix and
  * a suffix).
  * <p>
  * This class provides support for reading and generating clang header maps.
  * No spec is available but we conform to the
  * <a href="http://clang.llvm.org/doxygen/HeaderMap_8h_source.html">reader class defined in the
  * Clang documentation</a>.
  * <p>
  * Note: currently we don't support offsets greater than MAX_SIGNED_INT.
  */
 public class HeaderMap {
   private static final double MAX_LOAD_FACTOR = 0.75;

   /**
    * Bucket in the hashtable that is a {@link HeaderMap}.
    * Note: This notion of bucket is slightly more abstract than the one on disk (string offsets
    * being already swapped/shifted).
    */
   private static class Bucket {
     /** Offset of the key string into stringBytes. */
     final int key;

     /** Offset of the value prefix into stringBytes. */
     final int prefix;

     /** Offset of the value suffix into stringBytes. */
     final int suffix;

     Bucket(int key, int prefix, int suffix) {
       this.key = key;
       this.prefix = prefix;
       this.suffix = suffix;
     }
   }

   private static final Charset DEFAULT_CHARSET = StandardCharsets.UTF_8;

   /** Number of entries in the string table. */
   private int numEntries;

   /** Number of buckets (always a power of 2). */
   private int numBuckets;

   /** Length of longest result path (excluding {@code null}). */
   private int maxValueLength;

   // data containers
   private Bucket[] buckets;
   private byte[] stringBytes; // actually chars to make debugging easier
   private int stringBytesActualLength;

   /** Map to help share strings. */
   private Map<String, Integer> addedStrings;

   private HeaderMap(int numBuckets, int stringBytesLength) {
     Preconditions.checkArgument(numBuckets > 0, "The number of buckets must be greater than 0");
     Preconditions.checkArgument(
         stringBytesLength > 0,
         "The size of the string array must be greater than 0");
     Preconditions.checkArgument(
         (numBuckets & (numBuckets - 1)) == 0,
         "The number of buckets must be a power of 2");

     this.numEntries = 0;
     this.numBuckets = numBuckets;
     this.maxValueLength = 0;

     this.buckets = new Bucket[numBuckets];
     this.stringBytes = new byte[stringBytesLength];
     this.stringBytesActualLength = 0;
     this.addedStrings = Maps.newHashMap();
   }

   public int getNumEntries() {
     return numEntries;
   }

   public int getNumBuckets() {
     return numBuckets;
   }

   public int getMaxValueLength() {
     return maxValueLength;
   }

   public interface HeaderMapVisitor {
     void apply(String str, String prefix, String suffix);
   }

   public void visit(HeaderMapVisitor visitor) {
     for (int i = 0; i < numBuckets; i++) {
       Bucket bucket = buckets[i];
       if (bucket != null) {
         visitor.apply(
             Preconditions.checkNotNull(getString(bucket.key)),
             Preconditions.checkNotNull(getString(bucket.prefix)),
             Preconditions.checkNotNull(getString(bucket.suffix)));
       }
     }
   }

   @Override
   public String toString() {
     StringBuilder builder = new StringBuilder();
     print(builder);
     return builder.toString();
   }

   public void print(final Appendable stream) {
     visit(new HeaderMapVisitor() {
       @Override
       public void apply(String str, String prefix, String suffix) {
         try {
           stream.append("\"");
           stream.append(str);
           stream.append("\" -> \"");
           stream.append(prefix);
           stream.append(suffix);
           stream.append("\"\n");
         } catch (IOException e) {
           throw new RuntimeException(e);
         }
       }
     });
   }

   @Nullable
   public String lookup(String str) {
     int hash0 = hashKey(str) & (numBuckets - 1);

     int hash = hash0;
     while (true) {
       Bucket bucket = buckets[hash];
       if (bucket == null) {
         return null;
       }
       if (str.equalsIgnoreCase(getString(bucket.key))) {
         return getString(bucket.prefix) + getString(bucket.suffix);
       }

       hash = (hash + 1) & (numBuckets - 1);
       if (hash == hash0) {
         return null;
       }
     }
   }

   // --------- I/O methods ----------

   private static final int HEADER_MAGIC = ('h' << 24) | ('m' << 16) | ('a' << 8) | 'p';
   private static final short HEADER_VERSION = 1;
   private static final short HEADER_RESERVED = 0;
   private static final int EMPTY_BUCKET_KEY = 0;

   private static final int HEADER_SIZE = 24;
   private static final int BUCKET_SIZE = 12;

   @Nullable
   public static HeaderMap deserialize(byte[] bytes) {
     HeaderMap hmap = new HeaderMap(1, 1);
     if (hmap.processBytes(bytes)) {
       return hmap;
     } else {
       return null;
     }
   }

   @Nullable
   public static HeaderMap deserialize(ByteBuffer buffer) {
     HeaderMap hmap = new HeaderMap(1, 1);
     if (hmap.processBuffer(buffer)) {
       return hmap;
     } else {
       return null;
     }
   }

   public static HeaderMap loadFromFile(File hmapFile) throws IOException {
     HeaderMap map;
     try (FileInputStream inputStream = new FileInputStream(hmapFile)) {
       FileChannel fileChannel = inputStream.getChannel();
       ByteBuffer buffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, hmapFile.length());

       map = HeaderMap.deserialize(buffer);
       if (map == null) {
         throw new IOException("Error while parsing header map " + hmapFile.toString());
       }
     }
     return map;
   }

   private boolean processBytes(byte[] bytes) {
     ByteBuffer buffer = ByteBuffer.wrap(bytes);
     return processBuffer(buffer);
   }

   private boolean processBuffer(ByteBuffer buffer) {
     buffer.order(ByteOrder.BIG_ENDIAN);
     if (buffer.getInt(0) != HEADER_MAGIC) {
       buffer.order(ByteOrder.LITTLE_ENDIAN);
     }

     int magic = buffer.getInt();
     short version = buffer.getShort();
     if (magic != HEADER_MAGIC || version != HEADER_VERSION) {
       return false;
     }

     /* reserved */ buffer.getShort();
     int stringOffset = buffer.getInt();
     numEntries = buffer.getInt();
     numBuckets = buffer.getInt();
     maxValueLength = buffer.getInt();

     // strings can be anywhere after the end of the buckets
     stringBytesActualLength = buffer.capacity() - HEADER_SIZE - numBuckets * BUCKET_SIZE;

     buckets = new Bucket[numBuckets];
     int actualOffset = HEADER_SIZE + numBuckets * BUCKET_SIZE - stringOffset;
     // actualOffset should always be positive since the index EMPTY_BUCKET_KEY=0 is reserved

     for (int i = 0; i < numBuckets; i++) {
       int keyRawOffset = buffer.getInt();
       int prefixRawOffset = buffer.getInt();
       int suffixRawOffset = buffer.getInt();

       if (keyRawOffset == EMPTY_BUCKET_KEY) {
         buckets[i] = null;
       } else {
         // we can subtract 1 value because index 0 is EMPTY_BUCKET_KEY
         buckets[i] = new Bucket(
             keyRawOffset - actualOffset,
             prefixRawOffset - actualOffset,
             suffixRawOffset - actualOffset);
       }
     }
     // anything else is string
     stringBytes = new byte[stringBytesActualLength];
     buffer.get(stringBytes);

     return true;
   }

   public int getRequiredBufferCapacity() {
     return HEADER_SIZE + numBuckets * BUCKET_SIZE + stringBytesActualLength;
   }

   public byte[] getBytes() {
     return getBytes(ByteOrder.BIG_ENDIAN);
   }

   public byte[] getBytes(ByteOrder bo) {
     byte[] bytes = new byte[getRequiredBufferCapacity()];
     ByteBuffer buffer = ByteBuffer.wrap(bytes).order(bo);
     serialize(buffer);
     return bytes;
   }

   public void serialize(ByteBuffer buffer) {
     int actualOffset = 1; // must be greater than EMPTY_BUCKET_KEY

     buffer.putInt(HEADER_MAGIC);
     buffer.putShort(HEADER_VERSION);
     buffer.putShort(HEADER_RESERVED);
     buffer.putInt(HEADER_SIZE + numBuckets * BUCKET_SIZE - actualOffset);
     buffer.putInt(numEntries);
     buffer.putInt(numBuckets);
     buffer.putInt(maxValueLength);

     for (int i = 0; i < numBuckets; i++) {
       Bucket bucket = buckets[i];
       if (bucket == null) {
         buffer.putInt(EMPTY_BUCKET_KEY);
         buffer.putInt(0);
         buffer.putInt(0);
       } else {
         buffer.putInt(bucket.key + actualOffset);
         buffer.putInt(bucket.prefix + actualOffset);
         buffer.putInt(bucket.suffix + actualOffset);
       }
     }
     buffer.put(stringBytes, 0, stringBytesActualLength);
   }

   // -------------- Builder class ----------------

   public static Builder builder() {
     return new Builder();
   }

   public static class Builder {

     static final int DEFAULT_NUM_BUCKETS = 256;
     static final int DEFAULT_STRING_BYTES_LENGTH = 256;

     HeaderMap headerMap;

     public Builder() {
       this.headerMap = new HeaderMap(DEFAULT_NUM_BUCKETS, DEFAULT_STRING_BYTES_LENGTH);
     }

     public synchronized boolean add(String key, String prefix, String suffix) {
       AddResult result = headerMap.add(key, prefix, suffix);

       while (result == AddResult.FAILURE_FULL) {
         // the table is full, let's start all over again with a doubled number of bucket
         // and (optimization) the same size of string bytes
         final HeaderMap newHeaderMap = new HeaderMap(
             headerMap.numBuckets * 2,
             headerMap.stringBytes.length);
         headerMap.visit(
             new HeaderMapVisitor() {
               @Override
               public void apply(String str, String prefix, String suffix) {
                 AddResult copying = newHeaderMap.add(str, prefix, suffix);
                 assert (copying == AddResult.OK);
               }
             });
         headerMap = newHeaderMap;
         result = headerMap.add(key, prefix, suffix);
       }

       return (result == AddResult.OK);
     }

     public static String[] splitPath(Path path) {
       String[] result = new String[2];
       if (path.getNameCount() < 2) {
         result[0] = "";
         result[1] = path.toString();
       } else {
         result[0] = path.getParent().toString() + "/";
         result[1] = path.getFileName().toString();
       }
       return result;
     }

     public boolean add(String key, Path path) {
       String[] s = splitPath(path);
       return add(key, s[0], s[1]);
     }

     public synchronized HeaderMap build() {
       return headerMap;
     }
   }

   // ------------- Internals -----------

   private static int hashKey(String str) {
     // ASCII lowercase is part of the format.
     // UTF8 is the standard filesystem charset.
     return hashKey(Ascii.toLowerCase(str).getBytes(DEFAULT_CHARSET));
   }

   private static int hashKey(byte[] str) {
     int key = 0;
     for (byte c : str) {
       key += c * 13;
     }
     return key;
   }

   private enum AddResult {
     OK,
     FAILURE_FULL,
     FAILURE_ALREADY_PRESENT,
   }

   @SuppressWarnings("PMD.UnusedPrivateMethod") // PMD has a bad heuristic here.
   private AddResult add(String str, String prefix, String suffix) {
     if ((numEntries + 1) / (double) numBuckets > MAX_LOAD_FACTOR) {
       return AddResult.FAILURE_FULL;
     }

     int hash0 = hashKey(str) & (numBuckets - 1);

     int hash = hash0;
     while (true) {
       Bucket bucket = buckets[hash];
       if (bucket == null) {
         bucket = new Bucket(
             addString(str),
             addString(prefix),
             addString(suffix));
         buckets[hash] = bucket;
         numEntries++;
         maxValueLength = max(maxValueLength, prefix.length() + suffix.length());
         return AddResult.OK;
       }

       if (str.equalsIgnoreCase(getString(bucket.key))) {
         return AddResult.FAILURE_ALREADY_PRESENT;
       }

       hash = (hash + 1) & (numBuckets - 1);
       if (hash == hash0) {
         return AddResult.FAILURE_FULL;
       }
     }
   }

   @Nullable
   private String getString(int offset) {
     Preconditions.checkArgument(offset >= 0 && offset <= stringBytesActualLength);

     StringBuffer buffer = new StringBuffer();
     byte b = 0;
     while ((offset < stringBytesActualLength) && ((b = stringBytes[offset]) != 0)) {
       buffer.append((char) b);
       offset++;
     }

     if (offset == stringBytesActualLength) {
       // We reached the end of the array without finding a 0.
       return null;
     }
     return buffer.toString();
   }

   private void putStringByte(byte b) {
     if (stringBytesActualLength == stringBytes.length) {
       byte[] newBytes = new byte[stringBytes.length * 2];
       System.arraycopy(stringBytes, 0, newBytes, 0, stringBytesActualLength);
       stringBytes = newBytes;
     }
     stringBytes[stringBytesActualLength] = b;
     stringBytesActualLength++;
   }

   private int addString(String str) {
     Integer existingOffset = addedStrings.get(str);
     if (existingOffset != null) {
       return existingOffset.intValue();
     }

     int offset = stringBytesActualLength;
     for (byte b : str.getBytes(DEFAULT_CHARSET)) {
       putStringByte(b);
     }
     putStringByte((byte) 0);

     addedStrings.put(str, offset);
     return offset;
   }
 }
	/*
	* Copyright 2014-present Facebook, Inc.
	*
	* 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 com.facebook.buck.apple.clang;

	import static java.lang.Math.max;

	import com.google.common.base.Ascii;
	import com.google.common.base.Preconditions;
	import com.google.common.collect.Maps;

	import java.io.File;
	import java.io.FileInputStream;
	import java.io.IOException;
	import java.nio.ByteBuffer;
	import java.nio.ByteOrder;
	import java.nio.channels.FileChannel;
	import java.nio.charset.Charset;
	import java.nio.charset.StandardCharsets;
	import java.nio.file.Path;
	import java.util.Map;

	import javax.annotation.Nullable;

	/**
	* Header maps are essentially hash maps from strings to paths (coded as two strings: a prefix and
	* a suffix).
	* <p>
	* This class provides support for reading and generating clang header maps.
	* No spec is available but we conform to the
	* <a href="http://clang.llvm.org/doxygen/HeaderMap_8h_source.html">reader class defined in the
	* Clang documentation</a>.
	* <p>
	* Note: currently we don't support offsets greater than MAX_SIGNED_INT.
	*/
	public class HeaderMap {
	private static final double MAX_LOAD_FACTOR = 0.75;

	/**
	* Bucket in the hashtable that is a {@link HeaderMap}.
	* Note: This notion of bucket is slightly more abstract than the one on disk (string offsets
	* being already swapped/shifted).
	*/
	private static class Bucket {
	/** Offset of the key string into stringBytes. */
	final int key;

	/** Offset of the value prefix into stringBytes. */
	final int prefix;

	/** Offset of the value suffix into stringBytes. */
	final int suffix;

	Bucket(int key, int prefix, int suffix) {
	this.key = key;
	this.prefix = prefix;
	this.suffix = suffix;
	}
	}

	private static final Charset DEFAULT_CHARSET = StandardCharsets.UTF_8;

	/** Number of entries in the string table. */
	private int numEntries;

	/** Number of buckets (always a power of 2). */
	private int numBuckets;

	/** Length of longest result path (excluding {@code null}). */
	private int maxValueLength;

	// data containers
	private Bucket[] buckets;
	private byte[] stringBytes; // actually chars to make debugging easier
	private int stringBytesActualLength;

	/** Map to help share strings. */
	private Map<String, Integer> addedStrings;

	private HeaderMap(int numBuckets, int stringBytesLength) {
	Preconditions.checkArgument(numBuckets > 0, "The number of buckets must be greater than 0");
	Preconditions.checkArgument(
	stringBytesLength > 0,
	"The size of the string array must be greater than 0");
	Preconditions.checkArgument(
	(numBuckets & (numBuckets - 1)) == 0,
	"The number of buckets must be a power of 2");

	this.numEntries = 0;
	this.numBuckets = numBuckets;
	this.maxValueLength = 0;

	this.buckets = new Bucket[numBuckets];
	this.stringBytes = new byte[stringBytesLength];
	this.stringBytesActualLength = 0;
	this.addedStrings = Maps.newHashMap();
	}

	public int getNumEntries() {
	return numEntries;
	}

	public int getNumBuckets() {
	return numBuckets;
	}

	public int getMaxValueLength() {
	return maxValueLength;
	}

	public interface HeaderMapVisitor {
	void apply(String str, String prefix, String suffix);
	}

	public void visit(HeaderMapVisitor visitor) {
	for (int i = 0; i < numBuckets; i++) {
	Bucket bucket = buckets[i];
	if (bucket != null) {
	visitor.apply(
	Preconditions.checkNotNull(getString(bucket.key)),
	Preconditions.checkNotNull(getString(bucket.prefix)),
	Preconditions.checkNotNull(getString(bucket.suffix)));
	}
	}
	}

	@Override
	public String toString() {
	StringBuilder builder = new StringBuilder();
	print(builder);
	return builder.toString();
	}

	public void print(final Appendable stream) {
	visit(new HeaderMapVisitor() {
	@Override
	public void apply(String str, String prefix, String suffix) {
	try {
	stream.append("\"");
	stream.append(str);
	stream.append("\" -> \"");
	stream.append(prefix);
	stream.append(suffix);
	stream.append("\"\n");
	} catch (IOException e) {
	throw new RuntimeException(e);
	}
	}
	});
	}

	@Nullable
	public String lookup(String str) {
	int hash0 = hashKey(str) & (numBuckets - 1);

	int hash = hash0;
	while (true) {
	Bucket bucket = buckets[hash];
	if (bucket == null) {
	return null;
	}
	if (str.equalsIgnoreCase(getString(bucket.key))) {
	return getString(bucket.prefix) + getString(bucket.suffix);
	}

	hash = (hash + 1) & (numBuckets - 1);
	if (hash == hash0) {
	return null;
	}
	}
	}

	// --------- I/O methods ----------

	private static final int HEADER_MAGIC = ('h' << 24) \| ('m' << 16) \| ('a' << 8) \| 'p';
	private static final short HEADER_VERSION = 1;
	private static final short HEADER_RESERVED = 0;
	private static final int EMPTY_BUCKET_KEY = 0;

	private static final int HEADER_SIZE = 24;
	private static final int BUCKET_SIZE = 12;

	@Nullable
	public static HeaderMap deserialize(byte[] bytes) {
	HeaderMap hmap = new HeaderMap(1, 1);
	if (hmap.processBytes(bytes)) {
	return hmap;
	} else {
	return null;
	}
	}

	@Nullable
	public static HeaderMap deserialize(ByteBuffer buffer) {
	HeaderMap hmap = new HeaderMap(1, 1);
	if (hmap.processBuffer(buffer)) {
	return hmap;
	} else {
	return null;
	}
	}

	public static HeaderMap loadFromFile(File hmapFile) throws IOException {
	HeaderMap map;
	try (FileInputStream inputStream = new FileInputStream(hmapFile)) {
	FileChannel fileChannel = inputStream.getChannel();
	ByteBuffer buffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, hmapFile.length());

	map = HeaderMap.deserialize(buffer);
	if (map == null) {
	throw new IOException("Error while parsing header map " + hmapFile.toString());
	}
	}
	return map;
	}

	private boolean processBytes(byte[] bytes) {
	ByteBuffer buffer = ByteBuffer.wrap(bytes);
	return processBuffer(buffer);
	}

	private boolean processBuffer(ByteBuffer buffer) {
	buffer.order(ByteOrder.BIG_ENDIAN);
	if (buffer.getInt(0) != HEADER_MAGIC) {
	buffer.order(ByteOrder.LITTLE_ENDIAN);
	}

	int magic = buffer.getInt();
	short version = buffer.getShort();
	if (magic != HEADER_MAGIC \|\| version != HEADER_VERSION) {
	return false;
	}

	/* reserved */ buffer.getShort();
	int stringOffset = buffer.getInt();
	numEntries = buffer.getInt();
	numBuckets = buffer.getInt();
	maxValueLength = buffer.getInt();

	// strings can be anywhere after the end of the buckets
	stringBytesActualLength = buffer.capacity() - HEADER_SIZE - numBuckets * BUCKET_SIZE;

	buckets = new Bucket[numBuckets];
	int actualOffset = HEADER_SIZE + numBuckets * BUCKET_SIZE - stringOffset;
	// actualOffset should always be positive since the index EMPTY_BUCKET_KEY=0 is reserved

	for (int i = 0; i < numBuckets; i++) {
	int keyRawOffset = buffer.getInt();
	int prefixRawOffset = buffer.getInt();
	int suffixRawOffset = buffer.getInt();

	if (keyRawOffset == EMPTY_BUCKET_KEY) {
	buckets[i] = null;
	} else {
	// we can subtract 1 value because index 0 is EMPTY_BUCKET_KEY
	buckets[i] = new Bucket(
	keyRawOffset - actualOffset,
	prefixRawOffset - actualOffset,
	suffixRawOffset - actualOffset);
	}
	}
	// anything else is string
	stringBytes = new byte[stringBytesActualLength];
	buffer.get(stringBytes);

	return true;
	}

	public int getRequiredBufferCapacity() {
	return HEADER_SIZE + numBuckets * BUCKET_SIZE + stringBytesActualLength;
	}

	public byte[] getBytes() {
	return getBytes(ByteOrder.BIG_ENDIAN);
	}

	public byte[] getBytes(ByteOrder bo) {
	byte[] bytes = new byte[getRequiredBufferCapacity()];
	ByteBuffer buffer = ByteBuffer.wrap(bytes).order(bo);
	serialize(buffer);
	return bytes;
	}

	public void serialize(ByteBuffer buffer) {
	int actualOffset = 1; // must be greater than EMPTY_BUCKET_KEY

	buffer.putInt(HEADER_MAGIC);
	buffer.putShort(HEADER_VERSION);
	buffer.putShort(HEADER_RESERVED);
	buffer.putInt(HEADER_SIZE + numBuckets * BUCKET_SIZE - actualOffset);
	buffer.putInt(numEntries);
	buffer.putInt(numBuckets);
	buffer.putInt(maxValueLength);

	for (int i = 0; i < numBuckets; i++) {
	Bucket bucket = buckets[i];
	if (bucket == null) {
	buffer.putInt(EMPTY_BUCKET_KEY);
	buffer.putInt(0);
	buffer.putInt(0);
	} else {
	buffer.putInt(bucket.key + actualOffset);
	buffer.putInt(bucket.prefix + actualOffset);
	buffer.putInt(bucket.suffix + actualOffset);
	}
	}
	buffer.put(stringBytes, 0, stringBytesActualLength);
	}

	// -------------- Builder class ----------------

	public static Builder builder() {
	return new Builder();
	}

	public static class Builder {

	static final int DEFAULT_NUM_BUCKETS = 256;
	static final int DEFAULT_STRING_BYTES_LENGTH = 256;

	HeaderMap headerMap;

	public Builder() {
	this.headerMap = new HeaderMap(DEFAULT_NUM_BUCKETS, DEFAULT_STRING_BYTES_LENGTH);
	}

	public synchronized boolean add(String key, String prefix, String suffix) {
	AddResult result = headerMap.add(key, prefix, suffix);

	while (result == AddResult.FAILURE_FULL) {
	// the table is full, let's start all over again with a doubled number of bucket
	// and (optimization) the same size of string bytes
	final HeaderMap newHeaderMap = new HeaderMap(
	headerMap.numBuckets * 2,
	headerMap.stringBytes.length);
	headerMap.visit(
	new HeaderMapVisitor() {
	@Override
	public void apply(String str, String prefix, String suffix) {
	AddResult copying = newHeaderMap.add(str, prefix, suffix);
	assert (copying == AddResult.OK);
	}
	});
	headerMap = newHeaderMap;
	result = headerMap.add(key, prefix, suffix);
	}

	return (result == AddResult.OK);
	}

	public static String[] splitPath(Path path) {
	String[] result = new String[2];
	if (path.getNameCount() < 2) {
	result[0] = "";
	result[1] = path.toString();
	} else {
	result[0] = path.getParent().toString() + "/";
	result[1] = path.getFileName().toString();
	}
	return result;
	}

	public boolean add(String key, Path path) {
	String[] s = splitPath(path);
	return add(key, s[0], s[1]);
	}

	public synchronized HeaderMap build() {
	return headerMap;
	}
	}

	// ------------- Internals -----------

	private static int hashKey(String str) {
	// ASCII lowercase is part of the format.
	// UTF8 is the standard filesystem charset.
	return hashKey(Ascii.toLowerCase(str).getBytes(DEFAULT_CHARSET));
	}

	private static int hashKey(byte[] str) {
	int key = 0;
	for (byte c : str) {
	key += c * 13;
	}
	return key;
	}

	private enum AddResult {
	OK,
	FAILURE_FULL,
	FAILURE_ALREADY_PRESENT,
	}

	@SuppressWarnings("PMD.UnusedPrivateMethod") // PMD has a bad heuristic here.
	private AddResult add(String str, String prefix, String suffix) {
	if ((numEntries + 1) / (double) numBuckets > MAX_LOAD_FACTOR) {
	return AddResult.FAILURE_FULL;
	}

	int hash0 = hashKey(str) & (numBuckets - 1);

	int hash = hash0;
	while (true) {
	Bucket bucket = buckets[hash];
	if (bucket == null) {
	bucket = new Bucket(
	addString(str),
	addString(prefix),
	addString(suffix));
	buckets[hash] = bucket;
	numEntries++;
	maxValueLength = max(maxValueLength, prefix.length() + suffix.length());
	return AddResult.OK;
	}

	if (str.equalsIgnoreCase(getString(bucket.key))) {
	return AddResult.FAILURE_ALREADY_PRESENT;
	}

	hash = (hash + 1) & (numBuckets - 1);
	if (hash == hash0) {
	return AddResult.FAILURE_FULL;
	}
	}
	}

	@Nullable
	private String getString(int offset) {
	Preconditions.checkArgument(offset >= 0 && offset <= stringBytesActualLength);

	StringBuffer buffer = new StringBuffer();
	byte b = 0;
	while ((offset < stringBytesActualLength) && ((b = stringBytes[offset]) != 0)) {
	buffer.append((char) b);
	offset++;
	}

	if (offset == stringBytesActualLength) {
	// We reached the end of the array without finding a 0.
	return null;
	}
	return buffer.toString();
	}

	private void putStringByte(byte b) {
	if (stringBytesActualLength == stringBytes.length) {
	byte[] newBytes = new byte[stringBytes.length * 2];
	System.arraycopy(stringBytes, 0, newBytes, 0, stringBytesActualLength);
	stringBytes = newBytes;
	}
	stringBytes[stringBytesActualLength] = b;
	stringBytesActualLength++;
	}

	private int addString(String str) {
	Integer existingOffset = addedStrings.get(str);
	if (existingOffset != null) {
	return existingOffset.intValue();
	}

	int offset = stringBytesActualLength;
	for (byte b : str.getBytes(DEFAULT_CHARSET)) {
	putStringByte(b);
	}
	putStringByte((byte) 0);

	addedStrings.put(str, offset);
	return offset;
	}
	}