From 800b8429cb46a303c413510e22da1f4347e36946 Mon Sep 17 00:00:00 2001
From: Tony Mack <tmack@cs.princeton.edu>
Date: Wed, 12 Aug 2009 03:18:07 +0000
Subject: [PATCH] use a prefix tree to decide which registry to send the
 request to. The prefix tree finds the chooses the longest matching hrn

---
 sfa/methods/list.py    | 44 +++++++++++++------
 sfa/util/prefixTree.py | 97 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 127 insertions(+), 14 deletions(-)
 create mode 100755 sfa/util/prefixTree.py

diff --git a/sfa/methods/list.py b/sfa/methods/list.py
index efbf8d3c..e9be62e7 100644
--- a/sfa/methods/list.py
+++ b/sfa/methods/list.py
@@ -6,8 +6,8 @@ from sfa.util.method import Method
 from sfa.util.parameter import Parameter, Mixed
 from sfa.trust.auth import Auth
 from sfa.util.record import GeniRecord
-
 from sfa.server.registry import Registries
+from sfa.util.prefixTree import prefixTree
 
 class list(Method):
     """
@@ -31,20 +31,36 @@ class list(Method):
         
         self.api.auth.check(cred, 'list')
         records = []
-        try:
-            if not self.api.auth.hierarchy.auth_exists(hrn):
-                raise MissingAuthority(hrn)
-            table = self.api.auth.get_auth_table(hrn)   
-            records = table.list()
-        except MissingAuthority:
-            # is this a foreign authority
-            registries = Registries(self.api)
+
+        # load all know registry names into a prefix tree and attempt to find
+        # the longest matching prefix  
+        registries = Registries(self.api)
+        hrns = registries.keys()
+        tree = prefixTree()
+        tree.load(hrns)
+        registry_hrn = tree.best_match(hrn)
+
+        #if there was no match then this record belongs to an unknow registry
+        if not registry_hrn:
+            raise MissingAuthority(hrn)
+        
+        # if the best match (longest matching hrn) is not the local registry,
+        # forward the request
+        if registry_hrn != self.api.hrn:
             credential = self.api.getCredential()
-            for registry in registries:
-                if hrn.startswith(registry) and registry not in [self.api.hrn]:
-                    record_list = registries[registry].list(credential, hrn)
-                    for record in record_list:
-                        records.append(record.as_dict()) 
+            try:
+                record_list = registries[registry_hrn].list(credential, hrn)
+                records = [record.as_dict() for record in record_list]
+                if records:
                     return records
+            except:
+                pass
+
+        # if we still havnt found the record yet, try the local registry
+        if not self.api.auth.hierarchy.auth_exists(hrn):
+            raise MissingAuthority(hrn)
         
+        table = self.api.auth.get_auth_table(hrn)
+        records = table.list()
+          
         return records
diff --git a/sfa/util/prefixTree.py b/sfa/util/prefixTree.py
new file mode 100755
index 00000000..93b0c5cd
--- /dev/null
+++ b/sfa/util/prefixTree.py
@@ -0,0 +1,97 @@
+class prefixNode:
+
+    def __init__(self, prefix):
+        self.prefix = prefix
+        self.children = []
+    
+
+class prefixTree:
+    
+    def __init__(self):
+        self.root = prefixNode("")
+
+    def insert(self, prefix, node = None):
+        """
+        insert a prefix into the tree
+        """
+        if not node:
+            node = self.root
+
+        parts = prefix.split(".")
+        length = len(parts)
+
+        if length > 1:
+            for i in range(1, length + 1):
+                name = ".".join(parts[:i])
+                if not self.exists(name) and not name == prefix:
+                    self.insert(name)
+         
+        if prefix.startswith(node.prefix):
+            if prefix == node.prefix:
+                pass
+            elif not node.children:
+                node.children.append(prefixNode(prefix))
+            else:
+                inserted  = False
+                for child in node.children:
+                    if prefix.startswith(child.prefix):
+                        self.insert(prefix, child)
+                        inserted = True
+                if not inserted:
+                    node.children.append(prefixNode(prefix)) 
+
+    def load(self, prefix_list):
+        """
+        load a list of prefixes into the tree
+        """
+        for prefix in prefix_list:
+            self.insert(prefix)
+
+    def exists(self, prefix, node = None):
+        """
+        returns true if the specified prefix exists anywhere in the tree,
+        false if it doesnt. 
+        """
+        if not node:
+            node = self.root
+
+        if not prefix.startswith(node.prefix):
+            return False
+        elif node.prefix == prefix:
+            return True
+        elif not node.children:
+            return False
+        else:
+            for child in node.children:
+                if prefix.startswith(child.prefix):
+                    return self.exists(prefix, child)
+
+    def best_match(self, prefix, node = None):
+        """
+        searches the tree and returns the prefix that best matches the 
+        specified prefix  
+        """
+        if not node:
+            node = self.root
+        
+        if prefix.startswith(node.prefix):
+            if not node.children:
+                return node.prefix
+            for child in node.children:
+                if prefix.startswith(child.prefix):
+                    return self.best_match(prefix, child)
+            return node.prefix
+         
+    def dump(self, node = None):
+        """
+        print the tree
+        """
+        if not node:
+            node = self.root
+            print node.prefix
+
+        for child in node.children:
+            print child.prefix, 
+         
+        for child in node.children:
+            self.dump(child)
-- 
2.43.0