001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package org.apache.tomcat.util.collections;
019:
020: import org.apache.tomcat.util.buf.MessageBytes;
021:
022: // Originally MimeHeaders
023:
024: /**
025: * An efficient representation for certain type of map. The keys
026: * can have a single or multi values, but most of the time there are
027: * single values.
028: *
029: * The data is of "MessageBytes" type, meaning bytes[] that can be
030: * converted to Strings ( if needed, and encoding is lazy-binded ).
031: *
032: * This is a base class for MimeHeaders, Parameters and Cookies.
033: *
034: * Data structures: each field is a single-valued key/value.
035: * The fields are allocated when needed, and are recycled.
036: * The current implementation does linear search, in future we'll
037: * also use the hashkey.
038: *
039: * @author dac@eng.sun.com
040: * @author James Todd [gonzo@eng.sun.com]
041: * @author Costin Manolache
042: */
043: public class MultiMap {
044:
045: protected Field[] fields;
046: // fields in use
047: protected int count;
048:
049: /**
050: *
051: */
052: public MultiMap(int initial_size) {
053: fields = new Field[initial_size];
054: }
055:
056: /**
057: * Clears all header fields.
058: */
059: public void recycle() {
060: for (int i = 0; i < count; i++) {
061: fields[i].recycle();
062: }
063: count = 0;
064: }
065:
066: // -------------------- Idx access to headers ----------
067: // This allows external iterators.
068:
069: /**
070: * Returns the current number of header fields.
071: */
072: public int size() {
073: return count;
074: }
075:
076: /**
077: * Returns the Nth header name
078: * This may be used to iterate through all header fields.
079: *
080: * An exception is thrown if the index is not valid ( <0 or >size )
081: */
082: public MessageBytes getName(int n) {
083: // n >= 0 && n < count ? headers[n].getName() : null
084: return fields[n].name;
085: }
086:
087: /**
088: * Returns the Nth header value
089: * This may be used to iterate through all header fields.
090: */
091: public MessageBytes getValue(int n) {
092: return fields[n].value;
093: }
094:
095: /** Find the index of a field with the given name.
096: */
097: public int find(String name, int starting) {
098: // We can use a hash - but it's not clear how much
099: // benefit you can get - there is an overhead
100: // and the number of headers is small (4-5 ?)
101: // Another problem is that we'll pay the overhead
102: // of constructing the hashtable
103:
104: // A custom search tree may be better
105: for (int i = starting; i < count; i++) {
106: if (fields[i].name.equals(name)) {
107: return i;
108: }
109: }
110: return -1;
111: }
112:
113: /** Find the index of a field with the given name.
114: */
115: public int findIgnoreCase(String name, int starting) {
116: // We can use a hash - but it's not clear how much
117: // benefit you can get - there is an overhead
118: // and the number of headers is small (4-5 ?)
119: // Another problem is that we'll pay the overhead
120: // of constructing the hashtable
121:
122: // A custom search tree may be better
123: for (int i = starting; i < count; i++) {
124: if (fields[i].name.equalsIgnoreCase(name)) {
125: return i;
126: }
127: }
128: return -1;
129: }
130:
131: /**
132: * Removes the field at the specified position.
133: *
134: * MultiMap will preserve the order of field add unless remove()
135: * is called. This is not thread-safe, and will invalidate all
136: * iterators.
137: *
138: * This is not a frequent operation for Headers and Parameters -
139: * there are better ways ( like adding a "isValid" field )
140: */
141: public void remove(int i) {
142: // reset and swap with last header
143: Field mh = fields[i];
144: // reset the field
145: mh.recycle();
146:
147: fields[i] = fields[count - 1];
148: fields[count - 1] = mh;
149: count--;
150: }
151:
152: /** Create a new, unitialized entry.
153: */
154: public int addField() {
155: int len = fields.length;
156: int pos = count;
157: if (count >= len) {
158: // expand header list array
159: Field tmp[] = new Field[pos * 2];
160: System.arraycopy(fields, 0, tmp, 0, len);
161: fields = tmp;
162: }
163: if (fields[pos] == null) {
164: fields[pos] = new Field();
165: }
166: count++;
167: return pos;
168: }
169:
170: public MessageBytes get(String name) {
171: for (int i = 0; i < count; i++) {
172: if (fields[i].name.equals(name)) {
173: return fields[i].value;
174: }
175: }
176: return null;
177: }
178:
179: public int findFirst(String name) {
180: for (int i = 0; i < count; i++) {
181: if (fields[i].name.equals(name)) {
182: return i;
183: }
184: }
185: return -1;
186: }
187:
188: public int findNext(int startPos) {
189: int next = fields[startPos].nextPos;
190: if (next != MultiMap.NEED_NEXT) {
191: return next;
192: }
193:
194: // next==NEED_NEXT, we never searched for this header
195: MessageBytes name = fields[startPos].name;
196: for (int i = startPos; i < count; i++) {
197: if (fields[i].name.equals(name)) {
198: // cache the search result
199: fields[startPos].nextPos = i;
200: return i;
201: }
202: }
203: fields[startPos].nextPos = MultiMap.LAST;
204: return -1;
205: }
206:
207: // workaround for JDK1.1.8/solaris
208: static final int NEED_NEXT = -2;
209: static final int LAST = -1;
210:
211: // -------------------- Internal representation --------------------
212: final class Field {
213: MessageBytes name;
214: MessageBytes value;
215:
216: // Extra info for speed
217:
218: // multiple fields with same name - a linked list will
219: // speed up multiple name enumerations and search.
220: int nextPos;
221:
222: // hashkey
223: int hash;
224: Field nextSameHash;
225:
226: Field() {
227: nextPos = MultiMap.NEED_NEXT;
228: }
229:
230: void recycle() {
231: name.recycle();
232: value.recycle();
233: nextPos = MultiMap.NEED_NEXT;
234: }
235: }
236: }
|