0
# Data Structures
1

2
Specialized data structures for high-performance web applications including multi-maps, tries, pools, and concurrent collections. These structures are optimized for the access patterns common in web servers and networking applications.
3

4
## Capabilities
5

6
### Fields
7

8
Container for name/value pairs with case sensitivity options, designed for HTTP header-like data structures.
9

10
```java { .api }
11
/**
12
 * A container for name/value pairs, commonly used for HTTP headers and form parameters
13
 */
14
public class Fields implements Iterable<Fields.Field> {
15
    /** Create new Fields instance */
16
    public Fields();
17
    
18
    /** Create Fields with case sensitivity setting */
19
    public Fields(boolean caseSensitive);
20
    
21
    /** Add name/value pair */
22
    public void add(String name, String value);
23
    
24
    /** Get first value for name */
25
    public String get(String name);
26
    
27
    /** Get all values for name */
28
    public List<String> getValues(String name);
29
    
30
    /** Put single value (replaces existing) */
31
    public void put(String name, String value);
32
    
33
    /** Put multiple values (replaces existing) */
34
    public void put(String name, List<String> values);
35
    
36
    /** Remove all values for name */
37
    public boolean remove(String name);
38
    
39
    /** Check if name exists */
40
    public boolean contains(String name);
41
    
42
    /** Get number of name/value pairs */
43
    public int size();
44
    
45
    /** Check if empty */
46
    public boolean isEmpty();
47
    
48
    /** Clear all fields */
49
    public void clear();
50
    
51
    /** Get field names */
52
    public Set<String> getFieldNames();
53
    
54
    /** Individual field representation */
55
    public static class Field {
56
        public String getName();
57
        public String getValue();
58
        public List<String> getValues();
59
    }
60
}
61
```
62

63
**Usage Examples:**
64

65
```java
66
import org.eclipse.jetty.util.Fields;
67
import java.util.List;
68

69
// HTTP headers example
70
Fields headers = new Fields();
71
headers.add("Content-Type", "text/html");
72
headers.add("Accept", "text/html");
73
headers.add("Accept", "application/json"); // Multiple values
74

75
String contentType = headers.get("Content-Type");
76
List<String> acceptTypes = headers.getValues("Accept");
77

78
// Form parameters
79
Fields params = new Fields();
80
params.put("username", "john");
81
params.put("roles", List.of("admin", "user"));
82

83
// Iteration
84
for (Fields.Field field : headers) {
85
    System.out.println(field.getName() + ": " + field.getValue());
86
}
87
```
88

89
### MultiMap
90

91
Multi-valued map extending LinkedHashMap for maintaining insertion order with multiple values per key.
92

93
```java { .api }
94
/**
95
 * A Map that can hold multiple values for each key
96
 */
97
public class MultiMap<V> extends LinkedHashMap<String, List<V>> {
98
    /** Create new MultiMap */
99
    public MultiMap();
100
    
101
    /** Create MultiMap with case sensitivity */
102
    public MultiMap(boolean caseSensitive);
103
    
104
    /** Add value to key (creates list if needed) */
105
    public void add(String key, V value);
106
    
107
    /** Get first value for key */
108
    public V getValue(String key);
109
    
110
    /** Get all values for key */
111
    public List<V> getValues(String key);
112
    
113
    /** Put single value (replaces existing) */
114
    public V putValue(String key, V value);
115
    
116
    /** Add all values from another MultiMap */
117
    public void addAllValues(MultiMap<V> map);
118
    
119
    /** Remove specific value from key */
120
    public boolean removeValue(String key, V value);
121
    
122
    /** Convert to single-valued map (first values only) */
123
    public Map<String, V> toStringArrayMap();
124
}
125
```
126

127
**Usage Examples:**
128

129
```java
130
import org.eclipse.jetty.util.MultiMap;
131
import java.util.List;
132

133
// Query parameters with multiple values
134
MultiMap<String> params = new MultiMap<>();
135
params.add("tag", "java");
136
params.add("tag", "web");
137
params.add("tag", "server");
138
params.add("limit", "10");
139

140
// Access values
141
String limit = params.getValue("limit");
142
List<String> tags = params.getValues("tag");
143

144
// Check for values
145
if (params.containsKey("tag")) {
146
    tags.forEach(tag -> System.out.println("Tag: " + tag));
147
}
148
```
149

150
### Pool Interface and Implementations
151

152
Generic object pooling interface with lifecycle management for resource reuse.
153

154
```java { .api }
155
/**
156
 * Generic object pool interface
157
 */
158
public interface Pool<P> {
159
    /** Acquire entry from pool */
160
    Pool.Entry<P> acquire();
161
    
162
    /** Release entry back to pool */
163
    boolean release(Pool.Entry<P> entry);
164
    
165
    /** Get maximum pool capacity */
166
    int getMaxEntries();
167
    
168
    /** Get current pool size */
169
    int size();
170
    
171
    /** Get number of available entries */
172
    int getIdleCount();
173
    
174
    /** Get number of entries in use */
175
    int getInUseCount();
176
    
177
    /** Check if pool is closed */
178
    boolean isClosed();
179
    
180
    /** Close pool and release resources */
181
    void close();
182
    
183
    /** Pool entry interface */
184
    interface Entry<P> {
185
        /** Get pooled object */
186
        P getPooled();
187
        
188
        /** Release entry back to pool */
189
        boolean release();
190
        
191
        /** Remove entry from pool permanently */
192
        boolean remove();
193
        
194
        /** Check if entry is reserved */
195
        boolean isReserved();
196
    }
197
}
198

199
/**
200
 * Thread-safe pool implementation
201
 */
202
public class ConcurrentPool<P> implements Pool<P> {
203
    /** Create pool with factory and maximum size */
204
    public ConcurrentPool(Pool.Factory<P> factory, int maxSize);
205
    
206
    /** Create pool with factory, maximum size, and multiplexing */
207
    public ConcurrentPool(Pool.Factory<P> factory, int maxSize, boolean multiplexed);
208
    
209
    /** Pool factory for creating objects */
210
    public interface Factory<P> {
211
        P create();
212
        boolean test(P pooled);
213
        void destroy(P pooled);
214
    }
215
}
216
```
217

218
**Usage Examples:**
219

220
```java
221
import org.eclipse.jetty.util.Pool;
222
import org.eclipse.jetty.util.ConcurrentPool;
223

224
// Database connection pool example
225
ConcurrentPool<Connection> connectionPool = new ConcurrentPool<>(
226
    new Pool.Factory<Connection>() {
227
        @Override
228
        public Connection create() {
229
            return DriverManager.getConnection(url, user, password);
230
        }
231
        
232
        @Override
233
        public boolean test(Connection conn) {
234
            try {
235
                return !conn.isClosed() && conn.isValid(1);
236
            } catch (SQLException e) {
237
                return false;
238
            }
239
        }
240
        
241
        @Override
242
        public void destroy(Connection conn) {
243
            try { conn.close(); } catch (SQLException e) {}
244
        }
245
    },
246
    20 // max connections
247
);
248

249
// Using pooled connection
250
Pool.Entry<Connection> entry = connectionPool.acquire();
251
if (entry != null) {
252
    try {
253
        Connection conn = entry.getPooled();
254
        // Use connection
255
        PreparedStatement stmt = conn.prepareStatement("SELECT * FROM users");
256
        // ...
257
    } finally {
258
        entry.release(); // Return to pool
259
    }
260
}
261
```
262

263
### Index and Trie Implementations
264

265
Immutable string lookup data structures optimized for fast prefix matching.
266

267
```java { .api }
268
/**
269
 * Immutable string-to-value lookup interface
270
 */
271
public interface Index<V> {
272
    /** Get value for exact key match */
273
    V get(String key);
274
    
275
    /** Get value for ByteBuffer key */
276
    V get(ByteBuffer key);
277
    
278
    /** Get best matching value for key */
279
    V getBest(String key);
280
    
281
    /** Get best matching value with prefix length */
282
    V getBest(String key, int offset, int length);
283
    
284
    /** Check if key exists */
285
    boolean isMutable();
286
    
287
    /** Get all keys */
288
    Set<String> keySet();
289
}
290

291
/**
292
 * Abstract base for trie implementations
293
 */
294
public abstract class AbstractTrie<V> implements Index<V> {
295
    /** Put key/value pair */
296
    public abstract boolean put(String key, V value);
297
    
298
    /** Check if case sensitive */
299
    public abstract boolean isCaseInsensitive();
300
}
301

302
/**
303
 * Array-based trie implementation
304
 */
305
public class ArrayTrie<V> extends AbstractTrie<V> {
306
    /** Create case sensitive trie */
307
    public ArrayTrie();
308
    
309
    /** Create trie with case sensitivity option */
310
    public ArrayTrie(boolean insensitive);
311
    
312
    /** Create trie with initial capacity */
313
    public ArrayTrie(int capacity);
314
}
315

316
/**
317
 * Tree-based trie implementation
318
 */
319
public class TreeTrie<V> extends AbstractTrie<V> {
320
    /** Create case sensitive trie */
321
    public TreeTrie();
322
    
323
    /** Create trie with case sensitivity option */
324
    public TreeTrie(boolean insensitive);
325
}
326
```
327

328
**Usage Examples:**
329

330
```java
331
import org.eclipse.jetty.util.ArrayTrie;
332
import org.eclipse.jetty.util.Index;
333

334
// HTTP method lookup
335
ArrayTrie<String> methods = new ArrayTrie<>();
336
methods.put("GET", "GET");
337
methods.put("POST", "POST");
338
methods.put("PUT", "PUT");
339
methods.put("DELETE", "DELETE");
340

341
// Fast lookup
342
String method = methods.get("GET");
343
String bestMatch = methods.getBest("GETDATA"); // Returns "GET"
344

345
// MIME type lookup (case insensitive)
346
ArrayTrie<String> mimeTypes = new ArrayTrie<>(true);
347
mimeTypes.put("html", "text/html");
348
mimeTypes.put("css", "text/css");
349
mimeTypes.put("js", "application/javascript");
350

351
String mimeType = mimeTypes.get("HTML"); // Returns "text/html"
352
```
353

354
### Attributes
355

356
Key-value attribute storage interface with implementations.
357

358
```java { .api }
359
/**
360
 * Key-value attribute storage interface
361
 */
362
public interface Attributes {
363
    /** Get attribute value */
364
    Object getAttribute(String name);
365
    
366
    /** Get attribute names */
367
    Set<String> getAttributeNames();
368
    
369
    /** Set attribute value */
370
    void setAttribute(String name, Object attribute);
371
    
372
    /** Remove attribute */
373
    Object removeAttribute(String name);
374
    
375
    /** Clear all attributes */
376
    void clearAttributes();
377
}
378

379
/**
380
 * Map-based attributes implementation
381
 */
382
public class AttributesMap implements Attributes, Dumpable {
383
    /** Create new attributes map */
384
    public AttributesMap();
385
    
386
    /** Create attributes map from existing map */
387
    public AttributesMap(Map<String, Object> map);
388
    
389
    /** Get underlying map */
390
    public Map<String, Object> getMap();
391
}
392
```
393

394
**Usage Examples:**
395

396
```java
397
import org.eclipse.jetty.util.Attributes;
398
import org.eclipse.jetty.util.AttributesMap;
399

400
// Request attributes
401
Attributes attributes = new AttributesMap();
402
attributes.setAttribute("user", userObject);
403
attributes.setAttribute("startTime", System.currentTimeMillis());
404
attributes.setAttribute("requestId", UUID.randomUUID().toString());
405

406
// Later access
407
User user = (User) attributes.getAttribute("user");
408
Long startTime = (Long) attributes.getAttribute("startTime");
409

410
// Cleanup
411
attributes.removeAttribute("user");
412
attributes.clearAttributes(); // Remove all
413
```
414

415
### Concurrent Collections
416

417
Additional concurrent data structures for high-performance applications.
418

419
```java { .api }
420
/**
421
 * Blocking array queue implementation
422
 */
423
public class BlockingArrayQueue<E> extends AbstractList<E> 
424
    implements BlockingQueue<E> {
425
    /** Create queue with initial capacity */
426
    public BlockingArrayQueue(int capacity);
427
    
428
    /** Create queue with capacity and growth factor */
429
    public BlockingArrayQueue(int capacity, int growBy);
430
    
431
    /** Create queue with capacity and max capacity */
432
    public BlockingArrayQueue(int capacity, int growBy, int maxCapacity);
433
}
434

435
/**
436
 * Atomic operations on two integers
437
 */
438
public class AtomicBiInteger {
439
    /** Create with initial values */
440
    public AtomicBiInteger(int encoded);
441
    
442
    /** Create with separate hi/lo values */  
443
    public AtomicBiInteger(int hi, int lo);
444
    
445
    /** Get hi value */
446
    public int getHi();
447
    
448
    /** Get lo value */  
449
    public int getLo();
450
    
451
    /** Get encoded value */
452
    public int get();
453
    
454
    /** Set both values atomically */
455
    public void set(int hi, int lo);
456
    
457
    /** Compare and set both values */
458
    public boolean compareAndSet(int expectedEncoded, int hi, int lo);
459
    
460
    /** Add to both values */
461
    public int addAndGet(int deltaHi, int deltaLo);
462
}
463
```
464

465
**Usage Examples:**
466

467
```java
468
import org.eclipse.jetty.util.BlockingArrayQueue;
469
import org.eclipse.jetty.util.AtomicBiInteger;
470
import java.util.concurrent.TimeUnit;
471

472
// Producer-consumer queue
473
BlockingArrayQueue<String> queue = new BlockingArrayQueue<>(100);
474

475
// Producer
476
queue.offer("task1");
477
queue.offer("task2", 1, TimeUnit.SECONDS);
478

479
// Consumer  
480
String task = queue.take(); // Blocks until available
481
String nextTask = queue.poll(5, TimeUnit.SECONDS); // Timeout
482

483
// Atomic counters
484
AtomicBiInteger counters = new AtomicBiInteger(0, 0);
485
counters.addAndGet(1, 0); // Increment success count
486
counters.addAndGet(0, 1); // Increment failure count
487

488
int successes = counters.getHi();
489
int failures = counters.getLo();
490
```
491

492
## Performance Characteristics
493

494
- **Fields**: O(1) average access, maintains insertion order
495
- **MultiMap**: O(1) average access per key, O(n) for all values of a key  
496
- **Pool**: O(1) acquire/release with concurrent access support
497
- **ArrayTrie**: O(k) where k is key length, optimized for small alphabets
498
- **TreeTrie**: O(k log n) where k is key length, n is number of keys
499
- **BlockingArrayQueue**: O(1) operations with configurable blocking behavior
500
- **AtomicBiInteger**: O(1) lock-free atomic operations on two integers
501

502
These data structures are specifically optimized for the access patterns common in web servers and high-performance networking applications.