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