1 /*******************************************************************************
2 * Copyright (c) 2012 Ericsson
4 * All rights reserved. This program and the accompanying materials are made
5 * available under the terms of the Eclipse Public License v1.0 which
6 * accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
9 * Contributors: Matthew Khouzam - Initial API and implementation
10 *******************************************************************************/
11 package org
.eclipse
.linuxtools
.tmf
.core
.ctfadaptor
;
13 import java
.util
.ArrayList
;
14 import java
.util
.HashMap
;
15 import java
.util
.Random
;
18 * Ctf Iterator Manager, allows mapping of iterators (a limited resource) to
19 * contexts (many many resources).
21 * @author Matthew Khouzam
25 public abstract class CtfIteratorManager
{
27 * A side note synchronized works on the whole object, Therefore add and
28 * remove will be thread safe.
32 * The map of traces to trace managers.
34 private static HashMap
<CtfTmfTrace
, CtfTraceManager
> map
= new HashMap
<CtfTmfTrace
, CtfTraceManager
>();
37 * Registers a trace to the iterator manager, the trace can now get
41 * the trace to register.
43 public static synchronized void addTrace(final CtfTmfTrace trace
) {
44 map
.put(trace
, new CtfTraceManager(trace
));
48 * Removes a trace to the iterator manager.
51 * the trace to register.
53 public static synchronized void removeTrace(final CtfTmfTrace trace
) {
58 * Get an iterator for a given trace and context.
64 * @return the iterator
66 public static synchronized CtfIterator
getIterator(final CtfTmfTrace trace
,
67 final CtfTmfLightweightContext ctx
) {
68 return map
.get(trace
).getIterator(ctx
);
75 * @author Matthew Khouzam
77 class CtfTraceManager
{
79 * Cache size. Under 1023 on linux32 systems. Number of file handles
82 private final static int MAX_SIZE
= 100;
84 * The map of the cache.
86 private final HashMap
<CtfTmfLightweightContext
, CtfIterator
> fMap
;
88 * An array pointing to the same cache. this allows fast "random" accesses.
90 private final ArrayList
<CtfTmfLightweightContext
> fRandomAccess
;
94 private final CtfTmfTrace fTrace
;
96 * Random number generator
98 private final Random fRnd
;
100 public CtfTraceManager(CtfTmfTrace trace
) {
101 fMap
= new HashMap
<CtfTmfLightweightContext
, CtfIterator
>();
102 fRandomAccess
= new ArrayList
<CtfTmfLightweightContext
>();
103 fRnd
= new Random(System
.nanoTime());
108 * This needs explaining: the iterator table is effectively a cache.
109 * Originally the contexts had a 1 to 1 structure with the file handles of a
110 * trace. This failed since there is a limit to how many file handles we can
111 * have opened simultaneously. Then a round-robin scheme was implemented,
112 * this lead up to a two competing contexts syncing up and using the same
113 * file handler, causing horrible slowdowns. Now a random replacement
114 * algorithm is selected. This is the same as used by arm processors, and it
115 * works quite well when many cores so this looks promising for very
116 * multi-threaded systems.
119 * the context to look up
120 * @return the iterator refering to the context
122 public CtfIterator
getIterator(final CtfTmfLightweightContext context
) {
124 * if the element is in the map, we don't need to do anything else.
126 CtfIterator retVal
= fMap
.get(context
);
127 if (retVal
== null) {
129 * Assign an iterator to a context, this means we will need to seek
132 if (fRandomAccess
.size() < MAX_SIZE
) {
134 * if we're not full yet, just add an element.
136 retVal
= new CtfIterator(fTrace
);
137 addElement(context
, retVal
);
141 * if we're full, randomly replace an element
143 retVal
= replaceRandomElement(context
);
145 final CtfLocationData location
= (CtfLocationData
) context
.getLocation().getLocationInfo();
146 retVal
.seek( location
);
152 * Add a pair of context and element to the hashmap and the arraylist.
159 private void addElement(final CtfTmfLightweightContext context
,
160 final CtfIterator elem
) {
161 fMap
.put(context
, elem
);
162 fRandomAccess
.add(context
);
166 * Replace a random element
169 * the context to swap in
170 * @return the iterator of the removed elements.
172 private CtfIterator
replaceRandomElement(
173 final CtfTmfLightweightContext context
) {
175 * This needs some explanation too: We need to select a random victim
176 * and remove it. The order of the elements is not important, so instead
177 * of just calling arraylist.remove(element) which has an O(n)
178 * complexity, we pick an random number. The element is swapped out of
179 * the array and removed and replaced in the hashmap.
181 final int size
= fRandomAccess
.size();
182 final int pos
= fRnd
.nextInt(size
);
183 final CtfTmfLightweightContext victim
= fRandomAccess
.get(pos
);
184 fRandomAccess
.set(pos
, context
);
185 final CtfIterator elem
= fMap
.remove(victim
);
186 fMap
.put(context
, elem
);