MethodTernaryTree


1   /*
2    * Copyright (C) The MX4J Contributors.
3    * All rights reserved.
4    *
5    * This software is distributed under the terms of the MX4J License version 1.0.
6    * See the terms of the MX4J License in the documentation provided with this software.
7    */
8   
9   package mx4j.util;
10  
11  /**
12   * Specialized ternary tree for method metadata information. <p>
13   * In JMX methods are referred to with the method name and the String[] representing the signature.
14   * One can decide to cache method information using as key a concatenation of method name + signature,
15   * but the cost of concatenation is very high, while hashmap access is fast.
16   * Ternary trees avoid string concatenation, and result to be 10x faster than concatenation + hashmap.
17   * However, the signature of a standard TernaryTree would be <code>Object get(Object[] key)</code> and
18   * <code>void put(Object[] key, Object value)</code>. Unfortunately normalizing method name + signature
19   * into a single array is also very expensive. <br>
20   * This version leaves method name and signature separated to have the fastest access possible to
21   * method information.
22   * See <a HREF="http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm">here</a> for further information
23   * on TernaryTrees.
24   *
25   * @version $Revision: 1.3 $
26   */
27  public class MethodTernaryTree
28  {
29     private Node m_root;
30  
31     /**
32      * Returns the method information given the method name and its signature.
33      *
34      * @see #put
35      */
36     public Object   get(String   methodName, String  [] signature)
37     {
38        if (signature == null)
39        {
40           throw new IllegalArgumentException  ();
41        }
42        return search(methodName, signature);
43     }
44  
45     /**
46      * Inserts in this TernaryTree the given method information, using as key the method name and its signature
47      *
48      * @see #get
49      */
50     public void put(String   methodName, String  [] signature, Object   information)
51     {
52        if (signature == null)
53        {
54           throw new IllegalArgumentException  ();
55        }
56        m_root = insert(m_root, methodName, signature, signature.length, information);
57     }
58  
59     private Object   search(String   methodName, String  [] signature)
60     {
61        Node node = m_root;
62        int index = 0;
63        while (node != null)
64        {
65           Object   key = index == 0 ? methodName : signature[index - 1];
66           if (key == null)
67           {
68              throw new IllegalArgumentException  ();
69           }
70  
71           int split = splitFunction(key);
72           if (split < node.splitValue)
73           {
74              node = node.left;
75           }
76           else if (split == node.splitValue)
77           {
78              if (index == signature.length)
79              {
80                 // Two objects may return the same split, because the splitFunction is not perfect
81                 // (ie does not always yield different values for different objects, eg hash functions)
82                 if (node.keys == null)
83                 {
84                    return null;
85                 }
86                 for (int i = 0; i < node.keys.length; ++i)
87                 {
88                    if (node.keys[i].equals(key))
89                    {
90                       return node.values[i];
91                    }
92                 }
93                 return null;
94              }
95              else
96              {
97                 ++index;
98                 node = node.middle;
99              }
100          }
101          else
102          {
103             node = node.right;
104          }
105       }
106       return null;
107    }
108 
109    private Node insert(Node node, String   methodName, String  [] signature, int length, Object   value)
110    {
111       Object   key = methodName;
112       if (key == null)
113       {
114          throw new IllegalArgumentException  ();
115       }
116 
117       int split = splitFunction(key);
118       if (node == null)
119       {
120          node = new Node();
121          node.splitValue = split;
122       }
123 
124       if (split < node.splitValue)
125       {
126          node.left = insert(node.left, methodName, signature, length, value);
127       }
128       else if (split == node.splitValue)
129       {
130          // Two objects may return the same split, because the splitFunction is not perfect
131          // (ie does not always yield different values for different objects, eg hash functions)
132          if (length == 0)
133          {
134             if (node.keys == null)
135             {
136                node.keys = new Object  [1];
137                node.values = new Object  [1];
138                node.keys[0] = key;
139                node.values[0] = value;
140             }
141             else
142             {
143                // Loop to see if the key already exists
144                boolean found = false;
145                for (int i = 0; i < node.keys.length; ++i)
146                {
147                   if (node.keys[i].equals(key))
148                   {
149                      // Already present, replace the value
150                      node.keys[i] = key;
151                      node.values[i] = value;
152                      found = true;
153                      break;
154                   }
155                }
156                // Not present, add it
157                if (!found)
158                {
159                   int len = node.keys.length;
160                   Object  [] olds = node.keys;
161                   node.keys = new Object  [len + 1];
162                   System.arraycopy(olds, 0, node.keys, 0, len);
163                   node.keys[len] = key;
164 
165                   olds = node.values;
166                   node.values = new Object  [len + 1];
167                   System.arraycopy(olds, 0, node.values, 0, len);
168                   node.values[len] = value;
169                }
170             }
171          }
172          else
173          {
174             node.middle = insert(node.middle, signature[signature.length - length], signature, length - 1, value);
175          }
176       }
177       else
178       {
179          node.right = insert(node.right, methodName, signature, length, value);
180       }
181 
182       return node;
183    }
184 
185    protected int splitFunction(Object   obj)
186    {
187       return obj.hashCode();
188    }
189 
190    private class Node
191    {
192       private int splitValue;
193       private Node right;
194       private Node middle;
195       private Node left;
196       private Object  [] keys;
197       private Object  [] values;
198    }
199 }
200
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags