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 | * | |
9 | * Contributors: Matthew Khouzam - Initial API and implementation | |
10 | *******************************************************************************/ | |
11 | package org.eclipse.linuxtools.tmf.core.ctfadaptor; | |
12 | ||
13 | import java.util.ArrayList; | |
14 | import java.util.HashMap; | |
15 | import java.util.Random; | |
16 | ||
17 | /** | |
18 | * Ctf Iterator Manager, allows mapping of iterators (a limited resource) to | |
19 | * contexts (many many resources). | |
20 | * | |
21 | * @author Matthew Khouzam | |
22 | * @version 1.0 | |
23 | * @since 1.1 | |
24 | */ | |
25 | public abstract class CtfIteratorManager { | |
26 | /* | |
27 | * A side note synchronized works on the whole object, Therefore add and | |
28 | * remove will be thread safe. | |
29 | */ | |
30 | ||
31 | /* | |
32 | * The map of traces to trace managers. | |
33 | */ | |
34 | private static HashMap<CtfTmfTrace, CtfTraceManager> map = new HashMap<CtfTmfTrace, CtfTraceManager>(); | |
35 | ||
36 | /** | |
37 | * Registers a trace to the iterator manager, the trace can now get | |
38 | * iterators. | |
39 | * | |
40 | * @param trace | |
41 | * the trace to register. | |
42 | */ | |
43 | public static synchronized void addTrace(final CtfTmfTrace trace) { | |
44 | map.put(trace, new CtfTraceManager(trace)); | |
45 | } | |
46 | ||
47 | /** | |
48 | * Removes a trace to the iterator manager. | |
49 | * | |
50 | * @param trace | |
51 | * the trace to register. | |
52 | */ | |
53 | public static synchronized void removeTrace(final CtfTmfTrace trace) { | |
5d1c6919 PT |
54 | CtfTraceManager mgr = map.remove(trace); |
55 | if (mgr != null) { | |
56 | mgr.clear(); | |
57 | } | |
53b235e1 MK |
58 | } |
59 | ||
60 | /** | |
61 | * Get an iterator for a given trace and context. | |
62 | * | |
63 | * @param trace | |
64 | * the trace | |
65 | * @param ctx | |
66 | * the context | |
67 | * @return the iterator | |
81a2d02e | 68 | * @since 2.0 |
53b235e1 MK |
69 | */ |
70 | public static synchronized CtfIterator getIterator(final CtfTmfTrace trace, | |
81a2d02e | 71 | final CtfTmfContext ctx) { |
53b235e1 MK |
72 | return map.get(trace).getIterator(ctx); |
73 | } | |
74 | } | |
75 | ||
76 | /** | |
77 | * A trace manager | |
78 | * | |
79 | * @author Matthew Khouzam | |
80 | */ | |
81 | class CtfTraceManager { | |
82 | /* | |
83 | * Cache size. Under 1023 on linux32 systems. Number of file handles | |
84 | * created. | |
85 | */ | |
86 | private final static int MAX_SIZE = 100; | |
87 | /* | |
88 | * The map of the cache. | |
89 | */ | |
81a2d02e | 90 | private final HashMap<CtfTmfContext, CtfIterator> fMap; |
53b235e1 MK |
91 | /* |
92 | * An array pointing to the same cache. this allows fast "random" accesses. | |
93 | */ | |
81a2d02e | 94 | private final ArrayList<CtfTmfContext> fRandomAccess; |
53b235e1 MK |
95 | /* |
96 | * The parent trace | |
97 | */ | |
98 | private final CtfTmfTrace fTrace; | |
99 | /* | |
100 | * Random number generator | |
101 | */ | |
102 | private final Random fRnd; | |
103 | ||
104 | public CtfTraceManager(CtfTmfTrace trace) { | |
81a2d02e AM |
105 | fMap = new HashMap<CtfTmfContext, CtfIterator>(); |
106 | fRandomAccess = new ArrayList<CtfTmfContext>(); | |
53b235e1 MK |
107 | fRnd = new Random(System.nanoTime()); |
108 | fTrace = trace; | |
109 | } | |
110 | ||
111 | /** | |
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. | |
121 | * | |
122 | * @param context | |
123 | * the context to look up | |
124 | * @return the iterator refering to the context | |
125 | */ | |
81a2d02e | 126 | public CtfIterator getIterator(final CtfTmfContext context) { |
53b235e1 MK |
127 | /* |
128 | * if the element is in the map, we don't need to do anything else. | |
129 | */ | |
130 | CtfIterator retVal = fMap.get(context); | |
131 | if (retVal == null) { | |
132 | /* | |
133 | * Assign an iterator to a context, this means we will need to seek | |
134 | * at the end. | |
135 | */ | |
136 | if (fRandomAccess.size() < MAX_SIZE) { | |
137 | /* | |
138 | * if we're not full yet, just add an element. | |
139 | */ | |
36dd544c | 140 | retVal = fTrace.createIterator(); |
53b235e1 MK |
141 | addElement(context, retVal); |
142 | ||
143 | } else { | |
144 | /* | |
145 | * if we're full, randomly replace an element | |
146 | */ | |
147 | retVal = replaceRandomElement(context); | |
148 | } | |
575beffc | 149 | if (context.getLocation() != null) { |
f5df94f8 | 150 | final CtfLocationInfo location = (CtfLocationInfo) context.getLocation().getLocationInfo(); |
575beffc PT |
151 | retVal.seek(location); |
152 | } | |
53b235e1 MK |
153 | } |
154 | return retVal; | |
155 | } | |
156 | ||
157 | /** | |
158 | * Add a pair of context and element to the hashmap and the arraylist. | |
159 | * | |
160 | * @param context | |
161 | * the context | |
162 | * @param elem | |
163 | * the iterator | |
164 | */ | |
81a2d02e | 165 | private void addElement(final CtfTmfContext context, |
53b235e1 MK |
166 | final CtfIterator elem) { |
167 | fMap.put(context, elem); | |
168 | fRandomAccess.add(context); | |
169 | } | |
170 | ||
171 | /** | |
172 | * Replace a random element | |
173 | * | |
174 | * @param context | |
175 | * the context to swap in | |
176 | * @return the iterator of the removed elements. | |
177 | */ | |
178 | private CtfIterator replaceRandomElement( | |
81a2d02e | 179 | final CtfTmfContext context) { |
53b235e1 MK |
180 | /* |
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. | |
186 | */ | |
187 | final int size = fRandomAccess.size(); | |
188 | final int pos = fRnd.nextInt(size); | |
81a2d02e | 189 | final CtfTmfContext victim = fRandomAccess.get(pos); |
53b235e1 MK |
190 | fRandomAccess.set(pos, context); |
191 | final CtfIterator elem = fMap.remove(victim); | |
192 | fMap.put(context, elem); | |
193 | return elem; | |
194 | } | |
195 | ||
5d1c6919 PT |
196 | void clear() { |
197 | for (CtfIterator iterator : fMap.values()) { | |
198 | iterator.dispose(); | |
199 | } | |
200 | fMap.clear(); | |
201 | fRandomAccess.clear(); | |
202 | } | |
53b235e1 | 203 | } |