← Back to branch summary

~ubuntu-branches/ubuntu/trusty/eclipse-linuxtools/trusty

« back to all changes in this revision

Viewing changes to lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/ctfadaptor/CtfIteratorManager.java

  • Committer: Package Import Robot
  • Author(s): tony mancill
  • Date: 2013-05-13 21:43:22 UTC
  • mfrom: (1.2.1) (2.1.2 experimental)
  • Revision ID: package-import@ubuntu.com-20130513214322-6frgd9du1n0w2uo7
Tags: 1.2.1-1
* Team upload.
* New upstream release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/ctfadaptor/CtfIteratorManager.java
 
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
            }
 
145
            retVal.seek((Long) context.getLocation().getLocation());
 
146
        }
 
147
        return retVal;
 
148
    }
 
149
 
 
150
    /**
 
151
     * Add a pair of context and element to the hashmap and the arraylist.
 
152
     *
 
153
     * @param context
 
154
     *            the context
 
155
     * @param elem
 
156
     *            the iterator
 
157
     */
 
158
    private void addElement(final CtfTmfLightweightContext context,
 
159
            final CtfIterator elem) {
 
160
        fMap.put(context, elem);
 
161
        fRandomAccess.add(context);
 
162
    }
 
163
 
 
164
    /**
 
165
     * Replace a random element
 
166
     *
 
167
     * @param context
 
168
     *            the context to swap in
 
169
     * @return the iterator of the removed elements.
 
170
     */
 
171
    private CtfIterator replaceRandomElement(
 
172
            final CtfTmfLightweightContext context) {
 
173
        /*
 
174
         * This needs some explanation too: We need to select a random victim
 
175
         * and remove it. The order of the elements is not important, so instead
 
176
         * of just calling arraylist.remove(element) which has an O(n)
 
177
         * complexity, we pick an random number. The element is swapped out of
 
178
         * the array and removed and replaced in the hashmap.
 
179
         */
 
180
        final int size = fRandomAccess.size();
 
181
        final int pos = fRnd.nextInt(size);
 
182
        final CtfTmfLightweightContext victim = fRandomAccess.get(pos);
 
183
        fRandomAccess.set(pos, context);
 
184
        final CtfIterator elem = fMap.remove(victim);
 
185
        fMap.put(context, elem);
 
186
        return elem;
 
187
    }
 
188
 
 
189
}