KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > tomcat > util > collections > MultiMap


1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */

17
18 package org.apache.tomcat.util.collections;
19
20 import org.apache.tomcat.util.buf.MessageBytes;
21
22 // Originally MimeHeaders
23

24 /**
25  * An efficient representation for certain type of map. The keys
26  * can have a single or multi values, but most of the time there are
27  * single values.
28  *
29  * The data is of "MessageBytes" type, meaning bytes[] that can be
30  * converted to Strings ( if needed, and encoding is lazy-binded ).
31  *
32  * This is a base class for MimeHeaders, Parameters and Cookies.
33  *
34  * Data structures: each field is a single-valued key/value.
35  * The fields are allocated when needed, and are recycled.
36  * The current implementation does linear search, in future we'll
37  * also use the hashkey.
38  *
39  * @author dac@eng.sun.com
40  * @author James Todd [gonzo@eng.sun.com]
41  * @author Costin Manolache
42  */

43 public class MultiMap {
44
45     protected Field[] fields;
46     // fields in use
47
protected int count;
48
49     /**
50      *
51      */

52     public MultiMap(int initial_size) {
53     fields=new Field[initial_size];
54     }
55
56     /**
57      * Clears all header fields.
58      */

59     public void recycle() {
60     for (int i = 0; i < count; i++) {
61         fields[i].recycle();
62     }
63     count = 0;
64     }
65
66     // -------------------- Idx access to headers ----------
67
// This allows external iterators.
68

69     /**
70      * Returns the current number of header fields.
71      */

72     public int size() {
73     return count;
74     }
75
76     /**
77      * Returns the Nth header name
78      * This may be used to iterate through all header fields.
79      *
80      * An exception is thrown if the index is not valid ( <0 or >size )
81      */

82     public MessageBytes getName(int n) {
83     // n >= 0 && n < count ? headers[n].getName() : null
84
return fields[n].name;
85     }
86
87     /**
88      * Returns the Nth header value
89      * This may be used to iterate through all header fields.
90      */

91     public MessageBytes getValue(int n) {
92     return fields[n].value;
93     }
94
95     /** Find the index of a field with the given name.
96      */

97     public int find( String JavaDoc name, int starting ) {
98     // We can use a hash - but it's not clear how much
99
// 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 }
237
Popular Tags