← Back to branch summary

~ubuntu-branches/ubuntu/trusty/jenkins/trusty

« back to all changes in this revision

Viewing changes to core/src/main/java/jenkins/model/lazy/AbstractLazyLoadRunMap.java

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-13 12:35:19 UTC
  • mfrom: (1.1.13)
  • Revision ID: package-import@ubuntu.com-20130813123519-tizgfxcr70trl7r0
Tags: 1.509.2+dfsg-1
http://bugs.debian.org/706725
http://bugs.debian.org/701163
http://bugs.debian.org/704848
* New upstream release (Closes: #706725):
  - d/control: Update versioned BD's:
    * jenkins-executable-war >= 1.28.
    * jenkins-instance-identity >= 1.3.
    * libjenkins-remoting-java >= 2.23.
    * libjenkins-winstone-java >= 0.9.10-jenkins-44.
    * libstapler-java >= 1.207.
    * libjenkins-json-java >= 2.4-jenkins-1.
    * libstapler-adjunct-timeline-java >= 1.4.
    * libstapler-adjunct-codemirror-java >= 1.2.
    * libmaven-hpi-plugin-java >= 1.93.
    * libjenkins-xstream-java >= 1.4.4-jenkins-3.
  - d/maven.rules: Map to older version of animal-sniffer-maven-plugin.
  - Add patch for compatibility with guava >= 0.14.
  - Add patch to exclude asm4 dependency via jnr-posix.
  - Fixes the following security vulnerabilities:
    CVE-2013-2034, CVE-2013-2033, CVE-2013-2034, CVE-2013-1808
* d/patches/*: Switch to using git patch-queue for managing patches.
* De-duplicate jars between libjenkins-java and jenkins-external-job-monitor
  (Closes: #701163):
  - d/control: Add dependency between jenkins-external-job-monitor ->
    libjenkins-java.
  - d/rules: 
    Drop installation of jenkins-core in jenkins-external-job-monitor.
  - d/jenkins-external-job-monitor.{links,install}: Link to jenkins-core
    in /usr/share/java instead of included version.
* Wait longer for jenkins to stop during restarts (Closes: #704848):
  - d/jenkins.init: Re-sync init script from upstream codebase.

Show diffs side-by-side

added added

removed removed

Lines of Context:
core/src/main/java/jenkins/model/lazy/AbstractLazyLoadRunMap.java
 
1
/*
 
2
 * The MIT License
 
3
 *
 
4
 * Copyright (c) 2012, CloudBees, Inc.
 
5
 *
 
6
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 
7
 * of this software and associated documentation files (the "Software"), to deal
 
8
 * in the Software without restriction, including without limitation the rights
 
9
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 
10
 * copies of the Software, and to permit persons to whom the Software is
 
11
 * furnished to do so, subject to the following conditions:
 
12
 *
 
13
 * The above copyright notice and this permission notice shall be included in
 
14
 * all copies or substantial portions of the Software.
 
15
 *
 
16
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
17
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
18
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 
19
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 
20
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 
21
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 
22
 * THE SOFTWARE.
 
23
 */
 
24
package jenkins.model.lazy;
 
25
 
 
26
import hudson.model.Job;
 
27
import hudson.model.Run;
 
28
import hudson.model.RunMap;
 
29
import org.apache.commons.collections.keyvalue.DefaultMapEntry;
 
30
import org.kohsuke.accmod.Restricted;
 
31
import org.kohsuke.accmod.restrictions.NoExternalUse;
 
32
 
 
33
import java.io.File;
 
34
import java.io.FilenameFilter;
 
35
import java.io.IOException;
 
36
import java.lang.ref.Reference;
 
37
import java.util.AbstractMap;
 
38
import java.util.ArrayList;
 
39
import java.util.Arrays;
 
40
import java.util.Collections;
 
41
import java.util.Comparator;
 
42
import java.util.Map;
 
43
import java.util.NoSuchElementException;
 
44
import java.util.Set;
 
45
import java.util.SortedMap;
 
46
import java.util.TreeMap;
 
47
import java.util.logging.Level;
 
48
import java.util.logging.Logger;
 
49
 
 
50
import static jenkins.model.lazy.AbstractLazyLoadRunMap.Direction.*;
 
51
import static jenkins.model.lazy.Boundary.*;
 
52
 
 
53
/**
 
54
 * {@link SortedMap} that keeps build records by their build numbers, in the descending order
 
55
 * (newer ones first.)
 
56
 *
 
57
 * <p>
 
58
 * The main thing about this class is that it encapsulates the lazy loading logic.
 
59
 * That is, while this class looks and feels like a normal {@link SortedMap} from outside,
 
60
 * it actually doesn't have every item in the map instantiated yet. As items in the map get
 
61
 * requested, this class {@link #retrieve(File) retrieves them} on demand, one by one.
 
62
 *
 
63
 * <p>
 
64
 * The lookup is primarily done by using the build number as the key (hence the key type is {@link Integer}),
 
65
 * but this class also provides look up based on {@linkplain #getIdOf(Object) the build ID}.
 
66
 *
 
67
 * <p>
 
68
 * This class makes the following assumption about the on-disk layout of the data:
 
69
 *
 
70
 * <ul>
 
71
 *     <li>Every build is stored in a directory, named after its ID.
 
72
 *     <li>ID and build number are in the consistent order. That is,
 
73
 *         if there are two builds #M and #N, {@code M>N <=> M.id > N.id}.
 
74
 * </ul>
 
75
 *
 
76
 * <p>
 
77
 * On certain platforms, there are symbolic links named after build numbers that link to the build ID.
 
78
 * If these are available, they are used as a hint to speed up the lookup. Otherwise
 
79
 * we rely on the assumption above and perform a binary search to locate the build.
 
80
 * (notice that we'll have to do linear search if we don't have the consistent ordering assumption,
 
81
 * which robs the whole point of doing lazy loading.)
 
82
 *
 
83
 * <p>
 
84
 * Some of the {@link SortedMap} operations are weakly implemented. For example,
 
85
 * {@link #size()} may be inaccurate because we only count the number of directories that look like
 
86
 * build records, without checking if they are loadable. But these weaknesses aren't distinguishable
 
87
 * from concurrent modifications, where another thread deletes a build while one thread iterates them.
 
88
 *
 
89
 * <p>
 
90
 * Some of the {@link SortedMap} operations are inefficiently implemented, by
 
91
 * {@linkplain #all() loading all the build records eagerly}. We hope to replace
 
92
 * these implementations by more efficient lazy-loading ones as we go.
 
93
 *
 
94
 * <p>
 
95
 * Object lock of {@code this} is used to make sure mutation occurs sequentially.
 
96
 * That is, ensure that only one thread is actually calling {@link #retrieve(File)} and
 
97
 * updating {@link Index#byNumber} and {@link Index#byId}.
 
98
 *
 
99
 * @author Kohsuke Kawaguchi
 
100
 * @since 1.485
 
101
 */
 
102
public abstract class AbstractLazyLoadRunMap<R> extends AbstractMap<Integer,R> implements SortedMap<Integer,R> {
 
103
    /**
 
104
     * Used in {@link #all()} to quickly determine if we've already loaded everything.
 
105
     */
 
106
    private boolean fullyLoaded;
 
107
 
 
108
    /**
 
109
     * Currently visible index.
 
110
     * Updated atomically. Once set to this field, the index object may not be modified.
 
111
     */
 
112
    private volatile Index index = new Index();
 
113
 
 
114
    /**
 
115
     * Pair of two maps into a single class, so that the changes can be made visible atomically,
 
116
     * and updates can happen concurrently to read.
 
117
     *
 
118
     * The idiom is that you put yourself in a synchronized block, {@linkplain #copy() make a copy of this},
 
119
     * update the copy, then set it to {@link #index}.
 
120
     */
 
121
    private class Index {
 
122
        /**
 
123
         * Stores the mapping from build number to build, for builds that are already loaded.
 
124
         */
 
125
        private final TreeMap<Integer,BuildReference<R>> byNumber;
 
126
 
 
127
        /**
 
128
         * Stores the build ID to build number for builds that we already know.
 
129
         *
 
130
         * If we have known load failure of the given ID, we record that in the map
 
131
         * by using the null value (not to be confused with a non-null {@link BuildReference}
 
132
         * with null referent, which just means the record was GCed.)
 
133
         */
 
134
        private final TreeMap<String,BuildReference<R>> byId;
 
135
 
 
136
        private Index() {
 
137
            byId = new TreeMap<String,BuildReference<R>>();
 
138
            byNumber = new TreeMap<Integer,BuildReference<R>>(COMPARATOR);
 
139
        }
 
140
 
 
141
        private Index(Index rhs) {
 
142
            byId     = new TreeMap<String, BuildReference<R>>(rhs.byId);
 
143
            byNumber = new TreeMap<Integer,BuildReference<R>>(rhs.byNumber);
 
144
        }
 
145
 
 
146
        /**
 
147
         * Returns the build record #M (<=n)
 
148
         */
 
149
        private Map.Entry<Integer,BuildReference<R>> ceilingEntry(int n) {
 
150
// switch to this once we depend on JDK6
 
151
//            return byNumber.ceilingEntry(n);
 
152
 
 
153
            Set<Entry<Integer, BuildReference<R>>> s = byNumber.tailMap(n).entrySet();
 
154
            if (s.isEmpty())    return null;
 
155
            else                return s.iterator().next();
 
156
        }
 
157
 
 
158
        /**
 
159
         * Returns the build record #M (>=n)
 
160
         */
 
161
        // >= and not <= because byNumber is in the descending order
 
162
        private Map.Entry<Integer,BuildReference<R>> floorEntry(int n) {
 
163
// switch to this once we depend on JDK6
 
164
//            return byNumber.floorEntry(n);
 
165
 
 
166
            SortedMap<Integer, BuildReference<R>> sub = byNumber.headMap(n);
 
167
            if (sub.isEmpty())    return null;
 
168
            Integer k = sub.lastKey();
 
169
            return new DefaultMapEntry(k,sub.get(k));
 
170
        }
 
171
    }
 
172
 
 
173
    /**
 
174
     * Build IDs found as directories, in the ascending order.
 
175
     */
 
176
    // copy on write
 
177
    private volatile SortedList<String> idOnDisk = new SortedList<String>(Collections.<String>emptyList());
 
178
 
 
179
    /**
 
180
     * Build number shortcuts found on disk, in the ascending order.
 
181
     */
 
182
    // copy on write
 
183
    private volatile SortedIntList numberOnDisk = new SortedIntList(0);
 
184
 
 
185
    /**
 
186
     * Base directory for data.
 
187
     * In effect this is treated as a final field, but can't mark it final
 
188
     * because the compatibility requires that we make it settable
 
189
     * in the first call after the constructor.
 
190
     */
 
191
    private File dir;
 
192
 
 
193
    protected AbstractLazyLoadRunMap(File dir) {
 
194
        initBaseDir(dir);
 
195
    }
 
196
 
 
197
    @Restricted(NoExternalUse.class)
 
198
    protected void initBaseDir(File dir) {
 
199
        assert this.dir==null;
 
200
        this.dir = dir;
 
201
        if (dir!=null)
 
202
            loadIdOnDisk();
 
203
    }
 
204
 
 
205
    /**
 
206
     * @return true if {@link AbstractLazyLoadRunMap#AbstractLazyLoadRunMap} was called with a non-null param, or {@link RunMap#load(Job, RunMap.Constructor)} was called
 
207
     */
 
208
    @Restricted(NoExternalUse.class)
 
209
    public final boolean baseDirInitialized() {
 
210
        return dir != null;
 
211
    }
 
212
 
 
213
    /**
 
214
     * Let go of all the loaded references.
 
215
     *
 
216
     * This is a bit more sophisticated version of forcing GC.
 
217
     * Primarily for debugging and testing lazy loading behaviour.
 
218
     */
 
219
    public void purgeCache() {
 
220
        index = new Index();
 
221
    }
 
222
 
 
223
    private void loadIdOnDisk() {
 
224
        String[] buildDirs = dir.list(createDirectoryFilter());
 
225
        if (buildDirs==null) {
 
226
            // the job may have just been created
 
227
            buildDirs=EMPTY_STRING_ARRAY;
 
228
        }
 
229
        // wrap into ArrayList to enable mutation
 
230
        Arrays.sort(buildDirs);
 
231
        idOnDisk = new SortedList(new ArrayList<String>(Arrays.asList(buildDirs)));
 
232
 
 
233
        // TODO: should we check that shortcuts is a symlink?
 
234
        String[] shortcuts = dir.list();
 
235
        if (shortcuts==null)    shortcuts=EMPTY_STRING_ARRAY;
 
236
        SortedIntList list = new SortedIntList(shortcuts.length/2);
 
237
        for (String s : shortcuts) {
 
238
            try {
 
239
                list.add(Integer.parseInt(s));
 
240
            } catch (NumberFormatException e) {
 
241
                // this isn't a shortcut
 
242
            }
 
243
        }
 
244
        list.sort();
 
245
        numberOnDisk = list;
 
246
    }
 
247
 
 
248
    public Comparator<? super Integer> comparator() {
 
249
        return COMPARATOR;
 
250
    }
 
251
 
 
252
    /**
 
253
     * If we have non-zero R in memory, we can return false right away.
 
254
     * If we have zero R in memory, try loading one and see if we can find something.
 
255
     */
 
256
    @Override
 
257
    public boolean isEmpty() {
 
258
        return index.byId.isEmpty() && search(Integer.MAX_VALUE, DESC)==null;
 
259
    }
 
260
 
 
261
    @Override
 
262
    public Set<Entry<Integer, R>> entrySet() {
 
263
        assert baseDirInitialized();
 
264
        return Collections.unmodifiableSet(new BuildReferenceMapAdapter<R>(this,all()).entrySet());
 
265
    }
 
266
 
 
267
    /**
 
268
     * Returns a read-only view of records that has already been loaded.
 
269
     */
 
270
    public SortedMap<Integer,R> getLoadedBuilds() {
 
271
        return Collections.unmodifiableSortedMap(new BuildReferenceMapAdapter<R>(this, index.byNumber));
 
272
    }
 
273
 
 
274
    /**
 
275
     * @param fromKey
 
276
     *      Biggest build number to be in the returned set.
 
277
     * @param toKey
 
278
     *      Smallest build number-1 to be in the returned set (-1 because this is exclusive)
 
279
     */
 
280
    public SortedMap<Integer, R> subMap(Integer fromKey, Integer toKey) {
 
281
        // TODO: if this method can produce a lazy map, that'd be wonderful
 
282
        // because due to the lack of floor/ceil/higher/lower kind of methods
 
283
        // to look up keys in SortedMap, various places of Jenkins rely on
 
284
        // subMap+firstKey/lastKey combo.
 
285
 
 
286
        R start = search(fromKey, DESC);
 
287
        if (start==null)    return EMPTY_SORTED_MAP;
 
288
 
 
289
        R end = search(toKey, ASC);
 
290
        if (end==null)      return EMPTY_SORTED_MAP;
 
291
 
 
292
        for (R i=start; i!=end; ) {
 
293
            i = search(getNumberOf(i)-1,DESC);
 
294
            assert i!=null;
 
295
        }
 
296
 
 
297
        return Collections.unmodifiableSortedMap(new BuildReferenceMapAdapter<R>(this, index.byNumber.subMap(fromKey, toKey)));
 
298
    }
 
299
 
 
300
    public SortedMap<Integer, R> headMap(Integer toKey) {
 
301
        return subMap(Integer.MAX_VALUE, toKey);
 
302
    }
 
303
 
 
304
    public SortedMap<Integer, R> tailMap(Integer fromKey) {
 
305
        return subMap(fromKey, Integer.MIN_VALUE);
 
306
    }
 
307
 
 
308
    public Integer firstKey() {
 
309
        R r = newestBuild();
 
310
        if (r==null)    throw new NoSuchElementException();
 
311
        return getNumberOf(r);
 
312
    }
 
313
 
 
314
    public Integer lastKey() {
 
315
        R r = oldestBuild();
 
316
        if (r==null)    throw new NoSuchElementException();
 
317
        return getNumberOf(r);
 
318
    }
 
319
 
 
320
    public R newestBuild() {
 
321
        return search(Integer.MAX_VALUE, DESC);
 
322
    }
 
323
 
 
324
    public R oldestBuild() {
 
325
        return search(Integer.MIN_VALUE, ASC);
 
326
    }
 
327
 
 
328
    @Override
 
329
    public R get(Object key) {
 
330
        if (key instanceof Integer) {
 
331
            int n = (Integer) key;
 
332
            return get(n);
 
333
        }
 
334
        return super.get(key);
 
335
    }
 
336
 
 
337
    public R get(int n) {
 
338
        return search(n,Direction.EXACT);
 
339
    }
 
340
 
 
341
    /**
 
342
     * Finds the build #M where M is nearby the given 'n'.
 
343
     *
 
344
     * <p>
 
345
     *
 
346
     *
 
347
     * @param n
 
348
     *      the index to start the search from
 
349
     * @param d
 
350
     *      defines what we mean by "nearby" above.
 
351
     *      If EXACT, find #N or return null.
 
352
     *      If ASC, finds the closest #M that satisfies M>=N.
 
353
     *      If DESC, finds the closest #M that satisfies M<=N.
 
354
     */
 
355
    public R search(final int n, final Direction d) {
 
356
        Entry<Integer, BuildReference<R>> c = index.ceilingEntry(n);
 
357
        if (c!=null && c.getKey()== n) {
 
358
            R r = c.getValue().get();
 
359
            if (r!=null)
 
360
            return r;    // found the exact #n
 
361
        }
 
362
 
 
363
        // at this point we know that we don't have #n loaded yet
 
364
 
 
365
        {// check numberOnDisk as a cache to see if we can find it there
 
366
            int npos = numberOnDisk.find(n);
 
367
            if (npos>=0) {// found exact match
 
368
                R r = load(numberOnDisk.get(npos), null);
 
369
                if (r!=null)
 
370
                    return r;
 
371
            }
 
372
 
 
373
            switch (d) {
 
374
            case ASC:
 
375
            case DESC:
 
376
                // didn't find the exact match, but what's the nearest ascending value in the cache?
 
377
                int neighbor = (d==ASC?HIGHER:LOWER).apply(npos);
 
378
                if (numberOnDisk.isInRange(neighbor)) {
 
379
                    R r = getByNumber(numberOnDisk.get(neighbor));
 
380
                    if (r!=null) {
 
381
                        // make sure that the cache is accurate by looking at the previous ID
 
382
                        // and it actually satisfies the constraint
 
383
                        int prev = (d==ASC?LOWER:HIGHER).apply(idOnDisk.find(getIdOf(r)));
 
384
                        if (idOnDisk.isInRange(prev)) {
 
385
                            R pr = getById(idOnDisk.get(prev));
 
386
                            // sign*sign is making sure that #pr and #r sandwiches #n.
 
387
                            if (pr!=null && signOfCompare(getNumberOf(pr),n)*signOfCompare(n,getNumberOf(r))>0)
 
388
                                return r;
 
389
                            else {
 
390
                                // cache is lying. there's something fishy.
 
391
                                // ignore the cache and do the slow search
 
392
                            }
 
393
                        } else {
 
394
                            // r is the build with youngest ID
 
395
                            return r;
 
396
                        }
 
397
                    } else {
 
398
                        // cache says we should have a build but we didn't.
 
399
                        // ignore the cache and do the slow search
 
400
                    }
 
401
                }
 
402
                break;
 
403
            case EXACT:
 
404
                // fall through
 
405
            }
 
406
 
 
407
            // didn't find it in the cache, but don't give up yet
 
408
            // maybe the cache just doesn't exist.
 
409
            // so fall back to the slow search
 
410
        }
 
411
 
 
412
        // capture the snapshot and work off with it since it can be overwritten by other threads
 
413
        SortedList<String> idOnDisk = this.idOnDisk;
 
414
        boolean clonedIdOnDisk = false; // if we modify idOnDisk we need to write it back. this flag is set to true when we overwrit idOnDisk local var
 
415
 
 
416
        // slow path: we have to find the build from idOnDisk by guessing ID of the build.
 
417
        // first, narrow down the candidate IDs to try by using two known number-to-ID mapping
 
418
        if (idOnDisk.isEmpty())     return null;
 
419
 
 
420
        Entry<Integer, BuildReference<R>> f = index.floorEntry(n);
 
421
 
 
422
        // if bound is null, use a sentinel value
 
423
        String cid = c==null ? "\u0000"  : c.getValue().id;
 
424
        String fid = f==null ? "\uFFFF" : f.getValue().id;
 
425
        // at this point, #n must be in (cid,fid)
 
426
 
 
427
        // We know that the build we are looking for exists in [lo,hi)  --- it's "hi)" and not "hi]" because we do +1.
 
428
        // we will narrow this down via binary search
 
429
        final int initialSize = idOnDisk.size();
 
430
        int lo = idOnDisk.higher(cid);
 
431
        int hi = idOnDisk.lower(fid)+1;
 
432
 
 
433
        final int initialLo = lo, initialHi = hi;
 
434
 
 
435
        if (!(0<=lo && lo<=hi && hi<=idOnDisk.size())) {
 
436
            // assertion error, but we are so far unable to get to the bottom of this bug.
 
437
            // but don't let this kill the loading the hard way
 
438
            String msg = String.format(
 
439
                    "JENKINS-15652 Assertion error #1: failing to load %s #%d %s: lo=%d,hi=%d,size=%d,size2=%d",
 
440
                    dir, n, d, lo, hi, idOnDisk.size(), initialSize);
 
441
            LOGGER.log(Level.WARNING, msg);
 
442
            return null;
 
443
        }
 
444
 
 
445
        while (lo<hi) {
 
446
            final int pivot = (lo+hi)/2;
 
447
            if (!(0<=lo && lo<=pivot && pivot<hi && hi<=idOnDisk.size())) {
 
448
                // assertion error, but we are so far unable to get to the bottom of this bug.
 
449
                // but don't let this kill the loading the hard way
 
450
                String msg = String.format(
 
451
                        "JENKINS-15652 Assertion error #2: failing to load %s #%d %s: lo=%d,hi=%d,pivot=%d,size=%d (initial:lo=%d,hi=%d,size=%d)",
 
452
                        dir, n, d, lo, hi, pivot, idOnDisk.size(), initialLo, initialHi, initialSize);
 
453
                LOGGER.log(Level.WARNING, msg);
 
454
                return null;
 
455
            }
 
456
            R r = load(idOnDisk.get(pivot), null);
 
457
            if (r==null) {
 
458
                // this ID isn't valid. get rid of that and retry pivot
 
459
                hi--;
 
460
                if (!clonedIdOnDisk) {// if we are making an edit, we need to own a copy
 
461
                    idOnDisk = new SortedList<String>(idOnDisk);
 
462
                    clonedIdOnDisk = true;
 
463
                }
 
464
                idOnDisk.remove(pivot);
 
465
                continue;
 
466
            }
 
467
 
 
468
            int found = getNumberOf(r);
 
469
            if (found==n)
 
470
                return r;   // exact match
 
471
 
 
472
            if (found<n)    lo = pivot+1;   // the pivot was too small. look in the upper half
 
473
            else            hi = pivot;     // the pivot was too big. look in the lower half
 
474
        }
 
475
 
 
476
        if (clonedIdOnDisk)
 
477
            this.idOnDisk = idOnDisk;   // feedback the modified result atomically
 
478
 
 
479
        assert lo==hi;
 
480
        // didn't find the exact match
 
481
        // both lo and hi point to the insertion point on idOnDisk
 
482
        switch (d) {
 
483
        case ASC:
 
484
            if (hi==idOnDisk.size())    return null;
 
485
            return getById(idOnDisk.get(hi));
 
486
        case DESC:
 
487
            if (lo<=0)                 return null;
 
488
            if (lo-1>=idOnDisk.size()) {
 
489
                // assertion error, but we are so far unable to get to the bottom of this bug.
 
490
                // but don't let this kill the loading the hard way
 
491
                LOGGER.log(Level.WARNING, String.format(
 
492
                        "JENKINS-15652 Assertion error #3: failing to load %s #%d %s: lo=%d,hi=%d,size=%d (initial:lo=%d,hi=%d,size=%d)",
 
493
                        dir, n,d,lo,hi,idOnDisk.size(), initialLo,initialHi,initialSize));
 
494
                return null;
 
495
            }
 
496
            return getById(idOnDisk.get(lo-1));
 
497
        case EXACT:
 
498
            return null;
 
499
        default:
 
500
            throw new AssertionError();
 
501
        }
 
502
    }
 
503
 
 
504
    /**
 
505
     * sign of (a-b).
 
506
     */
 
507
    private static int signOfCompare(int a, int b) {
 
508
        if (a>b)    return 1;
 
509
        if (a<b)    return -1;
 
510
        return 0;
 
511
    }
 
512
 
 
513
    public R getById(String id) {
 
514
        Index snapshot = index;
 
515
        if (snapshot.byId.containsKey(id)) {
 
516
            BuildReference<R> ref = snapshot.byId.get(id);
 
517
            if (ref==null)      return null;    // known failure
 
518
            R v = unwrap(ref);
 
519
            if (v!=null)        return v;       // already in memory
 
520
            // otherwise fall through to load
 
521
        }
 
522
        return load(id,null);
 
523
    }
 
524
 
 
525
    public R getByNumber(int n) {
 
526
        return search(n,Direction.EXACT);
 
527
    }
 
528
 
 
529
    public R put(R value) {
 
530
        return _put(value);
 
531
    }
 
532
 
 
533
    protected R _put(R value) {
 
534
        return put(getNumberOf(value),value);
 
535
    }
 
536
 
 
537
    @Override
 
538
    public synchronized R put(Integer key, R r) {
 
539
        String id = getIdOf(r);
 
540
        int n = getNumberOf(r);
 
541
 
 
542
        Index copy = copy();
 
543
        BuildReference<R> ref = createReference(r);
 
544
        BuildReference<R> old = copy.byId.put(id,ref);
 
545
        copy.byNumber.put(n,ref);
 
546
        index = copy;
 
547
 
 
548
        /*
 
549
            search relies on the fact that every object added via
 
550
            put() method be available in the xyzOnDisk index, so I'm adding them here
 
551
            however, this is awfully inefficient. I wonder if there's any better way to do this?
 
552
         */
 
553
        if (!idOnDisk.contains(id)) {
 
554
            ArrayList<String> a = new ArrayList<String>(idOnDisk);
 
555
            a.add(id);
 
556
            Collections.sort(a);
 
557
            idOnDisk = new SortedList<String>(a);
 
558
        }
 
559
 
 
560
        if (!numberOnDisk.contains(n)) {
 
561
            SortedIntList a = new SortedIntList(numberOnDisk);
 
562
            a.add(n);
 
563
            a.sort();
 
564
            numberOnDisk = a;
 
565
        }
 
566
 
 
567
        return unwrap(old);
 
568
    }
 
569
 
 
570
    private R unwrap(Reference<R> ref) {
 
571
        return ref!=null ? ref.get() : null;
 
572
    }
 
573
 
 
574
    @Override
 
575
    public synchronized void putAll(Map<? extends Integer,? extends R> rhs) {
 
576
        Index copy = copy();
 
577
        for (R r : rhs.values()) {
 
578
            String id = getIdOf(r);
 
579
            BuildReference<R> ref = createReference(r);
 
580
            copy.byId.put(id,ref);
 
581
            copy.byNumber.put(getNumberOf(r),ref);
 
582
        }
 
583
        index = copy;
 
584
    }
 
585
 
 
586
    /**
 
587
     * Loads all the build records to fully populate the map.
 
588
     * Calling this method results in eager loading everything,
 
589
     * so the whole point of this class is to avoid this call as much as possible
 
590
     * for typical code path.
 
591
     *
 
592
     * @return
 
593
     *      fully populated map.
 
594
     */
 
595
    private TreeMap<Integer,BuildReference<R>> all() {
 
596
        if (!fullyLoaded) {
 
597
            synchronized (this) {
 
598
                if (!fullyLoaded) {
 
599
                    Index copy = copy();
 
600
                    for (String id : idOnDisk) {
 
601
                        if (!copy.byId.containsKey(id))
 
602
                            load(id,copy);
 
603
                    }
 
604
                    index = copy;
 
605
                    fullyLoaded = true;
 
606
                }
 
607
            }
 
608
        }
 
609
        return index.byNumber;
 
610
    }
 
611
 
 
612
    /**
 
613
     * Creates a duplicate for the COW data structure in preparation for mutation.
 
614
     */
 
615
    private Index copy() {
 
616
        return new Index(index);
 
617
   }
 
618
 
 
619
    /**
 
620
     * Tries to load the record #N by using the shortcut.
 
621
     * 
 
622
     * @return null if the data failed to load.
 
623
     */
 
624
    protected R load(int n, Index editInPlace) {
 
625
        R r = null;
 
626
        File shortcut = new File(dir,String.valueOf(n));
 
627
        if (shortcut.isDirectory()) {
 
628
            synchronized (this) {
 
629
                r = load(shortcut,editInPlace);
 
630
 
 
631
                // make sure what we actually loaded is #n,
 
632
                // because the shortcuts can lie.
 
633
                if (r!=null && getNumberOf(r)!=n)
 
634
                    r = null;
 
635
 
 
636
                if (r==null) {
 
637
                    // if failed to locate, record that fact
 
638
                    SortedIntList update = new SortedIntList(numberOnDisk);
 
639
                    update.removeValue(n);
 
640
                    numberOnDisk = update;
 
641
                }
 
642
            }
 
643
        }
 
644
        return r;
 
645
    }
 
646
 
 
647
 
 
648
    protected R load(String id, Index editInPlace) {
 
649
        assert dir != null;
 
650
        R v = load(new File(dir, id), editInPlace);
 
651
        if (v==null && editInPlace!=null) {
 
652
            // remember the failure.
 
653
            // if editInPlace==null, we can create a new copy for this, but not sure if it's worth doing,
 
654
            // given that we also update idOnDisk anyway.
 
655
            editInPlace.byId.put(id,null);
 
656
        }
 
657
        return v;
 
658
    }
 
659
 
 
660
    /**
 
661
     * @param editInPlace
 
662
     *      If non-null, update this data structure.
 
663
     *      Otherwise do a copy-on-write of {@link #index}
 
664
     */
 
665
    protected synchronized R load(File dataDir, Index editInPlace) {
 
666
        try {
 
667
            R r = retrieve(dataDir);
 
668
            if (r==null)    return null;
 
669
 
 
670
            Index copy = editInPlace!=null ? editInPlace : new Index(index);
 
671
 
 
672
            String id = getIdOf(r);
 
673
            BuildReference<R> ref = createReference(r);
 
674
            copy.byId.put(id,ref);
 
675
            copy.byNumber.put(getNumberOf(r),ref);
 
676
 
 
677
            if (editInPlace==null)  index = copy;
 
678
 
 
679
            return r;
 
680
        } catch (IOException e) {
 
681
            LOGGER.log(Level.WARNING, "Failed to load "+dataDir,e);
 
682
        }
 
683
        return null;
 
684
    }
 
685
 
 
686
    /**
 
687
     * Subtype to provide {@link Run#getNumber()} so that this class doesn't have to depend on it.
 
688
     */
 
689
    protected abstract int getNumberOf(R r);
 
690
    /**
 
691
     * Subtype to provide {@link Run#getId()} so that this class doesn't have to depend on it.
 
692
     */
 
693
    protected abstract String getIdOf(R r);
 
694
 
 
695
    /**
 
696
     * Allow subtype to capture a reference.
 
697
     */
 
698
    protected BuildReference<R> createReference(R r) {
 
699
        return new BuildReference<R>(getIdOf(r),r);
 
700
    }
 
701
 
 
702
 
 
703
    /**
 
704
     * Parses {@code R} instance from data in the specified directory.
 
705
     *
 
706
     * @return
 
707
     *      null if the parsing failed.
 
708
     * @throws IOException
 
709
     *      if the parsing failed. This is just like returning null
 
710
     *      except the caller will catch the exception and report it.
 
711
     */
 
712
    protected abstract R retrieve(File dir) throws IOException;
 
713
 
 
714
    public synchronized boolean removeValue(R run) {
 
715
        Index copy = copy();
 
716
        copy.byNumber.remove(getNumberOf(run));
 
717
        BuildReference<R> old = copy.byId.remove(getIdOf(run));
 
718
        this.index = copy;
 
719
 
 
720
        return unwrap(old)!=null;
 
721
    }
 
722
 
 
723
    /**
 
724
     * Replaces all the current loaded Rs with the given ones.
 
725
     */
 
726
    public synchronized void reset(TreeMap<Integer,R> builds) {
 
727
        Index index = new Index();
 
728
        for (R r : builds.values()) {
 
729
            String id = getIdOf(r);
 
730
            BuildReference<R> ref = createReference(r);
 
731
            index.byId.put(id,ref);
 
732
            index.byNumber.put(getNumberOf(r),ref);
 
733
        }
 
734
 
 
735
        this.index = index;
 
736
    }
 
737
 
 
738
    @Override
 
739
    public int hashCode() {
 
740
        return System.identityHashCode(this);
 
741
    }
 
742
 
 
743
    @Override
 
744
    public boolean equals(Object o) {
 
745
        return o==this;
 
746
    }
 
747
 
 
748
    /**
 
749
     * Lists the actual data directory
 
750
     */
 
751
    protected abstract FilenameFilter createDirectoryFilter();
 
752
 
 
753
    private static final Comparator<Comparable> COMPARATOR = new Comparator<Comparable>() {
 
754
        public int compare(Comparable o1, Comparable o2) {
 
755
            return -o1.compareTo(o2);
 
756
        }
 
757
    };
 
758
    
 
759
    public enum Direction {
 
760
        ASC, DESC, EXACT
 
761
    }
 
762
 
 
763
    private static final String[] EMPTY_STRING_ARRAY = new String[0];
 
764
 
 
765
    private static final SortedMap EMPTY_SORTED_MAP = Collections.unmodifiableSortedMap(new TreeMap());
 
766
 
 
767
    static final Logger LOGGER = Logger.getLogger(AbstractLazyLoadRunMap.class.getName());
 
768
}