Changeset 2440 in josm for trunk/src


Ignore:
Timestamp:
2009-11-12T19:37:33+01:00 (12 years ago)
Author:
hansendc
Message:

Fixes races reported in trac #3909

This introduces locking to QuadBuckets. This introduces
a QuadBucket-wide lock called 'split_lock'. It protects
a wee bit more than just splits, but splits are its
primary target.

It is used in the iterator to ensure that we do not
encounter temporary dead-ends during tree walks.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

    r2437 r2440  
    1818    public static boolean debug = false;
    1919    static boolean consistency_testing = false;
     20    /*
     21     * Functions prefixed with __ need locking before
     22     * being called.
     23     */
     24    private Object split_lock = new Object();
    2025
    2126    static void abort(String s)
     
    263268            return index;
    264269        }
    265         void split()
     270        /*
     271         * There is a race between this and qb.nextContentNode().
     272         * If nextContentNode() runs into this bucket, it may
     273         * attempt to null out 'children' because it thinks this
     274         * is a dead end.
     275         */
     276        void __split()
    266277        {
    267278            if (debug) {
     
    283294                int new_index = get_index(o, level);
    284295                if (new_index == -1) {
    285                     this.add_content(o);
     296                    this.__add_content(o);
    286297                    //out("adding content to branch: " + this);
    287298                    continue;
     
    297308            }
    298309        }
    299         boolean add_content(T o)
     310        void split() {
     311            synchronized(split_lock) {
     312                __split();
     313            }
     314        }
     315        boolean __add_content(T o)
    300316        {
    301317            boolean ret = false;
     318            // The split_lock will keep two concurrent
     319            // calls from overwriting content
    302320            if (content == null) {
    303321                content = new ArrayList<T>();
     
    309327            return ret;
    310328        }
    311         void add_to_leaf(T o)
    312         {
    313             add_content(o);
     329        void __add_to_leaf(T o)
     330        {
     331            __add_content(o);
    314332            if (content.size() > MAX_OBJECTS_PER_LEVEL) {
    315333                if (debug) {
     
    447465            return next;
    448466        }
     467        QBLevel firstChild()
     468        {
     469            QBLevel ret = null;
     470            for (QBLevel child : this.children) {
     471                if (child == null)
     472                    continue;
     473                ret = child;
     474                break;
     475            }
     476            return ret;
     477        }
    449478        QBLevel nextContentNode()
    450479        {
     
    455484            if (next == null)
    456485                return null;
    457             // Walk back down the tree
    458             // and find the first leaf
     486            // Walk back down the tree and find the first leaf
    459487            while (!next.isLeaf()) {
     488                QBLevel child;
    460489                if (next.hasContent() && next != this) {
    461490                    break;
    462491                }
     492                child = next.firstChild();
    463493                if (debug) {
    464494                    out("["+next.level+"] next node ("+next+") is a branch (content: "+next.hasContent()+"), moving down...");
    465495                }
    466                 boolean progress = false;
    467                 for (QBLevel child : next.children) {
    468                     if (child == null) {
    469                         continue;
    470                     }
    471                     next = child;
    472                     progress = true;
    473                     break;
    474                 }
    475                 if (!progress) {
    476                     // this should out it as not being a branch
    477                     next.children = null;
    478                     break;
    479                 }
    480             }
    481             // This means that there are no leaves or branches
    482             // with content as children.  We must continue to
    483             // search siblings.
    484             if (next == this)
    485                 return nextSibling().nextContentNode();
     496                if (child == null)
     497                    abort("branch node had no children");
     498                next = child;
     499            }
    486500            return next;
    487501        }
     
    561575                }
    562576            }
    563             if (isLeaf()) {
    564                 add_to_leaf(n);
    565             } else {
    566                 add_to_branch(n);
     577            synchronized (split_lock) {
     578                if (isLeaf()) {
     579                    __add_to_leaf(n);
     580                } else {
     581                    __add_to_branch(n);
     582                }
    567583            }
    568584            return true;
    569585        }
    570         QBLevel add_to_branch(T n)
     586        QBLevel __add_to_branch(T n)
    571587        {
    572588            int index = get_index(n, level);
     
    575591                    out("unable to get index for " + n + "at level: " + level + ", adding content to branch: " + this);
    576592                }
    577                 this.add_content(n);
     593                this.__add_content(n);
    578594                return this;
    579595            }
     
    815831        // bounding box.  Just stash it in the root node.
    816832        if (!n.isUsable()) {
    817             ret = root.add_content(n);
     833            synchronized (split_lock) {
     834                ret = root.__add_content(n);
     835            }
    818836        } else {
    819837            ret = root.add(n);
     
    967985                return null;
    968986            QBLevel orig = q;
    969             QBLevel next = q.nextContentNode();
     987            QBLevel next;
     988            synchronized (split_lock) {
     989                next = q.nextContentNode();
     990            }
    970991            //if (consistency_testing && (orig == next))
    971992            if (orig == next) {
Note: See TracChangeset for help on using the changeset viewer.