Commit | Line | Data |
---|---|---|
53b235e1 | 1 | /******************************************************************************* |
61759503 | 2 | * Copyright (c) 2012, 2013 Ericsson |
53b235e1 MK |
3 | * |
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 | |
8 | * | |
f0414df8 SD |
9 | * Contributors: |
10 | * Matthew Khouzam - Initial API and implementation | |
11 | * Simon Delisle - Added a method to remove the iterator | |
53b235e1 MK |
12 | *******************************************************************************/ |
13 | package org.eclipse.linuxtools.tmf.core.ctfadaptor; | |
14 | ||
15 | import java.util.ArrayList; | |
16 | import java.util.HashMap; | |
17 | import java.util.Random; | |
18 | ||
19 | /** | |
20 | * Ctf Iterator Manager, allows mapping of iterators (a limited resource) to | |
21 | * contexts (many many resources). | |
22 | * | |
23 | * @author Matthew Khouzam | |
24 | * @version 1.0 | |
25 | * @since 1.1 | |
26 | */ | |
27 | public abstract class CtfIteratorManager { | |
28 | /* | |
29 | * A side note synchronized works on the whole object, Therefore add and | |
30 | * remove will be thread safe. | |
31 | */ | |
32 | ||
33 | /* | |
34 | * The map of traces to trace managers. | |
35 | */ | |
a4524c1b | 36 | private static HashMap<CtfTmfTrace, CtfTraceManager> map = new HashMap<>(); |
53b235e1 MK |
37 | |
38 | /** | |
39 | * Registers a trace to the iterator manager, the trace can now get | |
40 | * iterators. | |
41 | * | |
42 | * @param trace | |
43 | * the trace to register. | |
44 | */ | |
45 | public static synchronized void addTrace(final CtfTmfTrace trace) { | |
46 | map.put(trace, new CtfTraceManager(trace)); | |
47 | } | |
48 | ||
49 | /** | |
50 | * Removes a trace to the iterator manager. | |
51 | * | |
52 | * @param trace | |
53 | * the trace to register. | |
54 | */ | |
55 | public static synchronized void removeTrace(final CtfTmfTrace trace) { | |
5d1c6919 PT |
56 | CtfTraceManager mgr = map.remove(trace); |
57 | if (mgr != null) { | |
58 | mgr.clear(); | |
59 | } | |
53b235e1 MK |
60 | } |
61 | ||
62 | /** | |
63 | * Get an iterator for a given trace and context. | |
64 | * | |
65 | * @param trace | |
66 | * the trace | |
67 | * @param ctx | |
68 | * the context | |
69 | * @return the iterator | |
81a2d02e | 70 | * @since 2.0 |
53b235e1 MK |
71 | */ |
72 | public static synchronized CtfIterator getIterator(final CtfTmfTrace trace, | |
81a2d02e | 73 | final CtfTmfContext ctx) { |
53b235e1 MK |
74 | return map.get(trace).getIterator(ctx); |
75 | } | |
f0414df8 SD |
76 | |
77 | /** | |
78 | * Remove an iterator for a given trace and context | |
79 | * | |
80 | * @param trace | |
81 | * the trace | |
82 | * @param ctx | |
83 | * the context | |
84 | * @since 2.1 | |
85 | */ | |
86 | public static synchronized void removeIterator(final CtfTmfTrace trace, final CtfTmfContext ctx) { | |
87 | CtfTraceManager traceManager = map.get(trace); | |
88 | if (traceManager != null) { | |
89 | traceManager.removeIterator(ctx); | |
90 | } | |
91 | } | |
53b235e1 MK |
92 | } |
93 | ||
94 | /** | |
95 | * A trace manager | |
96 | * | |
97 | * @author Matthew Khouzam | |
98 | */ | |
99 | class CtfTraceManager { | |
100 | /* | |
101 | * Cache size. Under 1023 on linux32 systems. Number of file handles | |
102 | * created. | |
103 | */ | |
104 | private final static int MAX_SIZE = 100; | |
105 | /* | |
106 | * The map of the cache. | |
107 | */ | |
81a2d02e | 108 | private final HashMap<CtfTmfContext, CtfIterator> fMap; |
53b235e1 MK |
109 | /* |
110 | * An array pointing to the same cache. this allows fast "random" accesses. | |
111 | */ | |
81a2d02e | 112 | private final ArrayList<CtfTmfContext> fRandomAccess; |
53b235e1 MK |
113 | /* |
114 | * The parent trace | |
115 | */ | |
116 | private final CtfTmfTrace fTrace; | |
117 | /* | |
118 | * Random number generator | |
119 | */ | |
120 | private final Random fRnd; | |
121 | ||
122 | public CtfTraceManager(CtfTmfTrace trace) { | |
a4524c1b AM |
123 | fMap = new HashMap<>(); |
124 | fRandomAccess = new ArrayList<>(); | |
53b235e1 MK |
125 | fRnd = new Random(System.nanoTime()); |
126 | fTrace = trace; | |
127 | } | |
128 | ||
129 | /** | |
130 | * This needs explaining: the iterator table is effectively a cache. | |
131 | * Originally the contexts had a 1 to 1 structure with the file handles of a | |
132 | * trace. This failed since there is a limit to how many file handles we can | |
133 | * have opened simultaneously. Then a round-robin scheme was implemented, | |
134 | * this lead up to a two competing contexts syncing up and using the same | |
135 | * file handler, causing horrible slowdowns. Now a random replacement | |
136 | * algorithm is selected. This is the same as used by arm processors, and it | |
137 | * works quite well when many cores so this looks promising for very | |
138 | * multi-threaded systems. | |
139 | * | |
140 | * @param context | |
141 | * the context to look up | |
ecb12461 | 142 | * @return the iterator referring to the context |
53b235e1 | 143 | */ |
81a2d02e | 144 | public CtfIterator getIterator(final CtfTmfContext context) { |
53b235e1 MK |
145 | /* |
146 | * if the element is in the map, we don't need to do anything else. | |
147 | */ | |
148 | CtfIterator retVal = fMap.get(context); | |
149 | if (retVal == null) { | |
150 | /* | |
151 | * Assign an iterator to a context, this means we will need to seek | |
152 | * at the end. | |
153 | */ | |
154 | if (fRandomAccess.size() < MAX_SIZE) { | |
155 | /* | |
156 | * if we're not full yet, just add an element. | |
157 | */ | |
36dd544c | 158 | retVal = fTrace.createIterator(); |
53b235e1 MK |
159 | addElement(context, retVal); |
160 | ||
161 | } else { | |
162 | /* | |
163 | * if we're full, randomly replace an element | |
164 | */ | |
165 | retVal = replaceRandomElement(context); | |
166 | } | |
575beffc | 167 | if (context.getLocation() != null) { |
f5df94f8 | 168 | final CtfLocationInfo location = (CtfLocationInfo) context.getLocation().getLocationInfo(); |
575beffc PT |
169 | retVal.seek(location); |
170 | } | |
53b235e1 MK |
171 | } |
172 | return retVal; | |
173 | } | |
174 | ||
f0414df8 SD |
175 | public void removeIterator(CtfTmfContext context) { |
176 | fMap.remove(context); | |
177 | fRandomAccess.remove(context); | |
178 | } | |
179 | ||
53b235e1 MK |
180 | /** |
181 | * Add a pair of context and element to the hashmap and the arraylist. | |
182 | * | |
183 | * @param context | |
184 | * the context | |
185 | * @param elem | |
186 | * the iterator | |
187 | */ | |
81a2d02e | 188 | private void addElement(final CtfTmfContext context, |
53b235e1 MK |
189 | final CtfIterator elem) { |
190 | fMap.put(context, elem); | |
191 | fRandomAccess.add(context); | |
192 | } | |
193 | ||
194 | /** | |
195 | * Replace a random element | |
196 | * | |
197 | * @param context | |
198 | * the context to swap in | |
199 | * @return the iterator of the removed elements. | |
200 | */ | |
201 | private CtfIterator replaceRandomElement( | |
81a2d02e | 202 | final CtfTmfContext context) { |
53b235e1 MK |
203 | /* |
204 | * This needs some explanation too: We need to select a random victim | |
205 | * and remove it. The order of the elements is not important, so instead | |
206 | * of just calling arraylist.remove(element) which has an O(n) | |
207 | * complexity, we pick an random number. The element is swapped out of | |
208 | * the array and removed and replaced in the hashmap. | |
209 | */ | |
210 | final int size = fRandomAccess.size(); | |
211 | final int pos = fRnd.nextInt(size); | |
81a2d02e | 212 | final CtfTmfContext victim = fRandomAccess.get(pos); |
53b235e1 MK |
213 | fRandomAccess.set(pos, context); |
214 | final CtfIterator elem = fMap.remove(victim); | |
215 | fMap.put(context, elem); | |
216 | return elem; | |
217 | } | |
218 | ||
5d1c6919 PT |
219 | void clear() { |
220 | for (CtfIterator iterator : fMap.values()) { | |
221 | iterator.dispose(); | |
222 | } | |
223 | fMap.clear(); | |
224 | fRandomAccess.clear(); | |
225 | } | |
53b235e1 | 226 | } |