Commit | Line | Data |
---|---|---|
53b235e1 MK |
1 | /******************************************************************************* |
2 | * Copyright (c) 2012 Ericsson | |
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) { | |
54 | map.remove(trace); | |
55 | } | |
56 | ||
57 | /** | |
58 | * Get an iterator for a given trace and context. | |
59 | * | |
60 | * @param trace | |
61 | * the trace | |
62 | * @param ctx | |
63 | * the context | |
64 | * @return the iterator | |
65 | */ | |
66 | public static synchronized CtfIterator getIterator(final CtfTmfTrace trace, | |
67 | final CtfTmfLightweightContext ctx) { | |
68 | return map.get(trace).getIterator(ctx); | |
69 | } | |
70 | } | |
71 | ||
72 | /** | |
73 | * A trace manager | |
74 | * | |
75 | * @author Matthew Khouzam | |
76 | */ | |
77 | class CtfTraceManager { | |
78 | /* | |
79 | * Cache size. Under 1023 on linux32 systems. Number of file handles | |
80 | * created. | |
81 | */ | |
82 | private final static int MAX_SIZE = 100; | |
83 | /* | |
84 | * The map of the cache. | |
85 | */ | |
86 | private final HashMap<CtfTmfLightweightContext, CtfIterator> fMap; | |
87 | /* | |
88 | * An array pointing to the same cache. this allows fast "random" accesses. | |
89 | */ | |
90 | private final ArrayList<CtfTmfLightweightContext> fRandomAccess; | |
91 | /* | |
92 | * The parent trace | |
93 | */ | |
94 | private final CtfTmfTrace fTrace; | |
95 | /* | |
96 | * Random number generator | |
97 | */ | |
98 | private final Random fRnd; | |
99 | ||
100 | public CtfTraceManager(CtfTmfTrace trace) { | |
101 | fMap = new HashMap<CtfTmfLightweightContext, CtfIterator>(); | |
102 | fRandomAccess = new ArrayList<CtfTmfLightweightContext>(); | |
103 | fRnd = new Random(System.nanoTime()); | |
104 | fTrace = trace; | |
105 | } | |
106 | ||
107 | /** | |
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. | |
117 | * | |
118 | * @param context | |
119 | * the context to look up | |
120 | * @return the iterator refering to the context | |
121 | */ | |
122 | public CtfIterator getIterator(final CtfTmfLightweightContext context) { | |
123 | /* | |
124 | * if the element is in the map, we don't need to do anything else. | |
125 | */ | |
126 | CtfIterator retVal = fMap.get(context); | |
127 | if (retVal == null) { | |
128 | /* | |
129 | * Assign an iterator to a context, this means we will need to seek | |
130 | * at the end. | |
131 | */ | |
132 | if (fRandomAccess.size() < MAX_SIZE) { | |
133 | /* | |
134 | * if we're not full yet, just add an element. | |
135 | */ | |
136 | retVal = new CtfIterator(fTrace); | |
137 | addElement(context, retVal); | |
138 | ||
139 | } else { | |
140 | /* | |
141 | * if we're full, randomly replace an element | |
142 | */ | |
143 | retVal = replaceRandomElement(context); | |
144 | } | |
132a02b0 MK |
145 | final CtfLocationData location = (CtfLocationData) context.getLocation().getLocation(); |
146 | retVal.seek( location); | |
53b235e1 MK |
147 | } |
148 | return retVal; | |
149 | } | |
150 | ||
151 | /** | |
152 | * Add a pair of context and element to the hashmap and the arraylist. | |
153 | * | |
154 | * @param context | |
155 | * the context | |
156 | * @param elem | |
157 | * the iterator | |
158 | */ | |
159 | private void addElement(final CtfTmfLightweightContext context, | |
160 | final CtfIterator elem) { | |
161 | fMap.put(context, elem); | |
162 | fRandomAccess.add(context); | |
163 | } | |
164 | ||
165 | /** | |
166 | * Replace a random element | |
167 | * | |
168 | * @param context | |
169 | * the context to swap in | |
170 | * @return the iterator of the removed elements. | |
171 | */ | |
172 | private CtfIterator replaceRandomElement( | |
173 | final CtfTmfLightweightContext context) { | |
174 | /* | |
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. | |
180 | */ | |
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); | |
187 | return elem; | |
188 | } | |
189 | ||
190 | } |