Programming Java threads in the real world, Part 6

The Observer pattern and mysteries of the AWTEventMulticaster

1 2 3 4 Page 3
Page 3 of 4

Figure 1 shows how an AWTEventMulticaster is used to construct a list of listeners. A static factory_method (add()) is used to create individual multicaster instances -- you can't create them with new. As you can see in Figure 1, this factory method is passed the current head-of-list reference and the listener to add. If either of these is null, it just returns the other, effectively creating a one-element list. If neither argument is null, then an AWTEventMulticaster object, essentially a binary-tree node, is created and initialized so that one child points to the existing list and the other points to the newly added listener. It continues in this way, building a binary tree whose interior nodes are all AWTEventMulticasters and whose leaf notes are standard AWT or Swing listener objects.

Figure 1. Building a subscription list with a multicaster

Notification is done with a simple, recursive tree-traversal. (Which can be a problem. You'll note in Figure 1 that the tree will most likely degrade into a linked list, and recursive traversal of a linked list can use up a lot of runtime stack.) As I mentioned earlier, the AWTEventMulticaster implements all of the standard listener interfaces (actionPerformed(), mouseClicked(), and so on). The multicaster overrides do nothing but pass the message to their children, using instanceof in the case of the leaf nodes to ensure that the message can be received by the actual object.

Immutable objects and blank finals

The most important feature of the AWTEventMulticaster is not actually evident in the diagram. The multicaster is an immutable object: all of its fields are declared static final, but are initialized in the constructor rather than the declaration; like this:

  public class AWTEventMulticaster implements ComponentListener, ...
   {   protected final EventListener a, b;
       protected AWTEventMulticaster(EventListener a, EventListener b)
        {   this.a = a; this.b = b;
        }
        //...
    }

Since everything's final, the object's state can't change once it's created. A Java String is immutable, for example. Immutable objects have a significant advantage over normal objects in multithreaded environments: you never have to synchronize access to them, because they can't change state. Consequently, replacing the Collection in the earlier listings with a multicaster eliminates the synchronization overhead entirely.

A final field that is initialized in the constructor rather than the declaration is called a blank final. You should use them whenever you can, which is unfortunately not as often as you'd like. An oft-reported bug that's been around since the early beta versions of the JDK 1.1 compiler is still there in the Java 2 compiler: The compiler sometimes incorrectly spits out the hard-error "Blank final may not have been initialized," even when the field in question has been initialized. This bug tends to manifest only when you use a lot of inner classes. Because I don't want to corrupt the global or package-level name space with class names that the user could care less about, I usually prefer removing the final to moving the inner class out to the global level.

Using the multicaster

The multicaster exhibits a lot of very desirable behavior. For example, you can safely add listeners to the list while traversals are in progress because the tree is constructed from the bottom up. The new listeners will not be notified by any of the in-progress notification threads, but adding a listener will not damage the list either.

Listener removal elicits the following question: How do you remove nodes from a tree whose nodes can't be modified? The flip answer is that you build another tree. Figure 2 shows the easy scenario. To effectively delete node C, you create a new root node and make its child pointers reference node D and node C's right subtree. If you overwrite subscribers with new_list -- the normal case -- there will be no more references to the gray-colored nodes, and they will eventually be garbage collected.

Figure 2. Deleting a node from a multicaster: the easy case

Figure 3 shows the more difficult process of deleting a node that's further down in the tree (C again). Here, you have to build a second tree that looks exactly like that part of the original tree that's above the deleted node. As before, the gray colored nodes are subject to garbage collection once subscribers is overwritten (and any traversals positioned in that part of the tree complete).

Figure 3. Deleting a node from a multicaster: the hard case

The first time I looked at the AWTEventMulticaster source, I thought the code was weird and unnecessarily complex. On reflection, though, I realized that there's a lot of neat stuff here. The more I looked at it, the more I liked it. Multiple threads can happily add and remove nodes without conflicting either with each other or with threads that are traversing the tree, and multiple threads can traverse the tree simultaneously. Moreover, absolutely no synchronization is required to do any of this. The data structure that's used is no larger than the doubly linked list that I used earlier, and the overhead of copying part of the tree when you do deletions is a lot less than the overhead of copying the entire subscriber list every time you publish an event.

So, not being one to look a gift algorithm in the mouth, I wrote up my own general-purpose version of the multicaster, based on the AWTEventMulticaster. It's in Listing 9. It's remarkable how little code there is here. (Ahh, the miracle of recursion!) All the complexity, in fact, is in the removal. (I'll leave it as an exercise to the reader to puzzle through how it works -- opacity is the down side of most recursive algorithms.) This implementation is very general purpose in that it can publish any Object to any class that implements the generic Subscriber interface (from Listing 2).

Listing 9 (/src/com/holub/tools/Multicaster.java): A roll-your-own multicaster
001  
002  
003  
004  
005  
package com.holub.tools;
import java.util.EventObject;
import com.holub.tools.Subscriber;
/** 
 |    

The multicaster (modeled after the AWTEventMulticaster) provides an efficient way to manage relatively-short lists of subscribers. Each Multicaster object can reference two Subscriber objects, one or both of which can be another multicaster. The top-level multicaster is passed a publish message, which it broadcasts (recursively) to both of the subscribers that it references.

The multicaster is an immutable object, so you can't modify it. The add() method, for example, is passed two multicasters and returns a third one that effectively references all the subscribers referenced by the original two. Any notifications that are in progress when the add() is executed will not be affected by the operation, however. It's perfectly acceptable for notifications to be performed on one thread while a second thread is adding or removing members from the Multicaster. The order in which Subscribers are notified is undefined. (It is not necessarily the order of insertion.)

@see java.awt.AWTEventMulticaster

@see Subscriber

 */
006  
007  
008  
009  
010  
011  
012  
013  
014  
015  
public class Multicaster implements Subscriber
{
   protected final Subscriber a, b;
   protected Multicaster(Subscriber a, Subscriber b)
    {   this.a = a;
        this.b = b;
    }
    /******************************************************************
     |    Ask the subscribers of this multicaster to receive the publication. This is the publish operation, as seen from the perspective of a subscriber. Remember, a multicaster is a list of subscribers. Note that the order of traversal should generally be considered undefined. However, if you really need to notify listeners in a known order, and you consistently add nodes as follows:
subscription_list = Multicaster.add( subscription_list, new_node );

(Where subscription_list is the head-of-list reference and new_node is the node you're adding), subscribers will be notified in the order they were added. Removing nodes does not affect the order of notification. If you transpose the two arguments in the foregoing code:
subscription_list = Multicaster.add( new_node, subscription_list );

subscribers will be notified in reverse order.
     */
016  
017  
018  
019  
020  
021  
  public void receive( Object publication )
    {   a.receive( publication );
        b.receive( publication );
    }
    /******************************************************************
     |    

Add a new subscriber to the list. The way that this call is used can impact the order in which subscribers are notified. (See receive().)

@param a Typically the head-of-list pointer.

@param b

Typically the Subscriber you're adding to the list.

     */
022  
023  
024  
025  
026  
  public static Subscriber add(Subscriber a, Subscriber b)
    {   return  (a == null)  ? b :
                (b == null)  ? a : new Multicaster(a, b);
    }
    /******************************************************************
     |    Remove the indicated subscriber from the list
     */
027  
028  
029  
030  
031  
032  
033  
034  
035  
036  
037  
038  
039  
040  
041  
042  
043  
044  
045  
046  
047  
048  
049  
050  
051  
052  
053  
054  
055  
056  
057  
058  
059  
060  
061  
062  
063  
064  
065  
066  
067  
068  
069  
070  
071  
072  
073  
074  
075  
076  
077  
078  
079  
080  
081  
082  
083  
084  
085  
086  
087  
088  
089  
090  
091  
092  
093  
094  
095  
096  
097  
098  
099  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
public static Subscriber remove(Subscriber list, Subscriber remove_me)
    {
        if( list == remove_me || list == null  )
            return null;
        else if( !(list instanceof Multicaster) )
            return list;
        else
            return ((Multicaster)list).remove( remove_me );
    }
    private Subscriber remove(Subscriber remove_me)
    {
        if (remove_me == a)  return b;
        if (remove_me == b)  return a;
        Subscriber a2 = remove( a, remove_me );
        Subscriber b2 = remove( b, remove_me );
        return (a2 == a && b2 == b ) // it's not here
                ? this
                : add(a2, b2)
                ;
    }
    //================================================================
   public static class Test
   {   private static class Leaf implements Subscriber
        {   String s;
           public Leaf(String s){ this.s = s; }
           public void receive( Object publication )   
            {   System.out.print(s);
            }
        }
       public static void main( String[] args )
        {   Leaf a = new Leaf("A");
            Leaf b = new Leaf("B");
            Leaf c = new Leaf("C");
            Leaf d = new Leaf("D");
            Leaf e = new Leaf("E");
            Subscriber subscription_list = null;
            subscription_list = Multicaster.add( subscription_list, a );
            subscription_list = Multicaster.add( subscription_list, b );
            subscription_list = Multicaster.add( subscription_list, c );
            subscription_list = Multicaster.add( subscription_list, d );
            subscription_list = Multicaster.add( subscription_list, e );
            System.out.print("List is: ");
            subscription_list.receive( null );
            System.out.print("\nRemoving c: ");
            subscription_list = Multicaster.remove( subscription_list, c );
            subscription_list.receive( null );
            System.out.print("\nRemoving a: ");
            subscription_list = Multicaster.remove( subscription_list, a );
            subscription_list.receive( null );
            System.out.print("\nRemoving d: ");
            subscription_list = Multicaster.remove( subscription_list, d );
            subscription_list.receive( null );
            System.out.print("\nRemoving b: ");
            subscription_list = Multicaster.remove( subscription_list, b );
            subscription_list.receive( null );
            System.out.print("\nRemoving e: ");
            subscription_list = Multicaster.remove( subscription_list, e );
            if( subscription_list != null )
                System.out.println("Couldn't remove last node");
            subscription_list = Multicaster.add( a, subscription_list );
            subscription_list = Multicaster.add( b, subscription_list );
            subscription_list = Multicaster.add( c, subscription_list );
            subscription_list = Multicaster.add( d, subscription_list );
            subscription_list = Multicaster.add( e, subscription_list );
            System.out.print("\nShould be: EDCBA: " );
            subscription_list.receive( null );
            System.out.println();
        }
    }
}

The final task, is to modify our publisher to use the multicaster. I've done that in Listing 10 (for this month's final entry in the worlds-most-complicated-way-to-print-"hello world" contest). This version is built on the one-thread-per-publication model discussed earlier.

1 2 3 4 Page 3
Page 3 of 4