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
) {
54 CtfTraceManager mgr
= map
.remove(trace
);
61 * Get an iterator for a given trace and context.
67 * @return the iterator
70 public static synchronized CtfIterator
getIterator(final CtfTmfTrace trace
,
71 final CtfTmfContext ctx
) {
72 return map
.get(trace
).getIterator(ctx
);
79 * @author Matthew Khouzam
81 class CtfTraceManager
{
83 * Cache size. Under 1023 on linux32 systems. Number of file handles
86 private final static int MAX_SIZE
= 100;
88 * The map of the cache.
90 private final HashMap
<CtfTmfContext
, CtfIterator
> fMap
;
92 * An array pointing to the same cache. this allows fast "random" accesses.
94 private final ArrayList
<CtfTmfContext
> fRandomAccess
;
98 private final CtfTmfTrace fTrace
;
100 * Random number generator
102 private final Random fRnd
;
104 public CtfTraceManager(CtfTmfTrace trace
) {
105 fMap
= new HashMap
<CtfTmfContext
, CtfIterator
>();
106 fRandomAccess
= new ArrayList
<CtfTmfContext
>();
107 fRnd
= new Random(System
.nanoTime());
112 * This needs explaining: the iterator table is effectively a cache.
113 * Originally the contexts had a 1 to 1 structure with the file handles of a
114 * trace. This failed since there is a limit to how many file handles we can
115 * have opened simultaneously. Then a round-robin scheme was implemented,
116 * this lead up to a two competing contexts syncing up and using the same
117 * file handler, causing horrible slowdowns. Now a random replacement
118 * algorithm is selected. This is the same as used by arm processors, and it
119 * works quite well when many cores so this looks promising for very
120 * multi-threaded systems.
123 * the context to look up
124 * @return the iterator refering to the context
126 public CtfIterator
getIterator(final CtfTmfContext context
) {
128 * if the element is in the map, we don't need to do anything else.
130 CtfIterator retVal
= fMap
.get(context
);
131 if (retVal
== null) {
133 * Assign an iterator to a context, this means we will need to seek
136 if (fRandomAccess
.size() < MAX_SIZE
) {
138 * if we're not full yet, just add an element.
140 retVal
= fTrace
.createIterator();
141 addElement(context
, retVal
);
145 * if we're full, randomly replace an element
147 retVal
= replaceRandomElement(context
);
149 if (context
.getLocation() != null) {
150 final CtfLocationInfo location
= (CtfLocationInfo
) context
.getLocation().getLocationInfo();
151 retVal
.seek(location
);
158 * Add a pair of context and element to the hashmap and the arraylist.
165 private void addElement(final CtfTmfContext context
,
166 final CtfIterator elem
) {
167 fMap
.put(context
, elem
);
168 fRandomAccess
.add(context
);
172 * Replace a random element
175 * the context to swap in
176 * @return the iterator of the removed elements.
178 private CtfIterator
replaceRandomElement(
179 final CtfTmfContext context
) {
181 * This needs some explanation too: We need to select a random victim
182 * and remove it. The order of the elements is not important, so instead
183 * of just calling arraylist.remove(element) which has an O(n)
184 * complexity, we pick an random number. The element is swapped out of
185 * the array and removed and replaced in the hashmap.
187 final int size
= fRandomAccess
.size();
188 final int pos
= fRnd
.nextInt(size
);
189 final CtfTmfContext victim
= fRandomAccess
.get(pos
);
190 fRandomAccess
.set(pos
, context
);
191 final CtfIterator elem
= fMap
.remove(victim
);
192 fMap
.put(context
, elem
);
197 for (CtfIterator iterator
: fMap
.values()) {
201 fRandomAccess
.clear();
This page took 0.03583 seconds and 6 git commands to generate.