[gobject-introspection] giscanner: use SqlAlchemy's OrderedDict implementation

[Dieter Verfaillie <dieterv src gnome org>]

commit 5ed56c0b62f917b448d28bf4742300fa173dbd90
Author: Dieter Verfaillie <dieterv optionexplicit be>
Date:   Thu Feb 14 17:41:49 2013 +0100

    giscanner: use SqlAlchemy's OrderedDict implementation
    
    g-ir-scanner can be a bit on the slow side. While true we
    now do a bit more work parsing GTK-Doc comment blocks and
    more is still to come, one of the biggest hotspots besides
    what's going on in _giscanner.SourceScanner() comes from
    the OrderedDict implementations we have been using.
    
    For example, time needed to build Gtk-3.0.gir on a relatively
    slow machine using "python2 -m cProfile -o $prefix/bin/g-ir-scanner ...":
    
    1) Our original DictMixin sublass:
         92,79867 seconds
    2) Python's collections.OrderedDict class:
         88,65786 seconds
    3) Larosa/Foord implementation from http://www.voidspace.org.uk/python/odict.html :
         71,64323 seconds
    4) SqlAlchemy's implementation:
         66,12449 seconds
    
    Looks like we have a clear winner with the SqlAclchemy
    implementation, which comes in at around 20 seconds
    without profiling on the same machine. Not bad.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=697620

 giscanner/annotationparser.py |    8 ++--
 giscanner/ast.py              |    4 +-
 giscanner/odict.py            |  111 +++++++++++++++++++++++++++++++++--------
 3 files changed, 95 insertions(+), 28 deletions(-)
---
diff --git a/giscanner/annotationparser.py b/giscanner/annotationparser.py
index 2314457..f722346 100644
--- a/giscanner/annotationparser.py
+++ b/giscanner/annotationparser.py
@@ -26,7 +26,7 @@
 import re
 
 from . import message
-from .odict import odict
+from .odict import OrderedDict
 
 
 # GTK-Doc comment block parts
@@ -367,9 +367,9 @@ class DocBlock(object):
         self.name = name
         self.options = DocOptions()
         self.value = None
-        self.tags = odict()
+        self.tags = OrderedDict()
         self.comment = None
-        self.params = odict()
+        self.params = OrderedDict()
         self.position = None
 
     def __cmp__(self, other):
@@ -655,7 +655,7 @@ class DocOption(object):
     def __init__(self, tag, option):
         self.tag = tag
         self._array = []
-        self._dict = odict()
+        self._dict = OrderedDict()
         # (annotation option1=value1 option2=value2) etc
         for p in option.split(' '):
             if '=' in p:
diff --git a/giscanner/ast.py b/giscanner/ast.py
index 5854091..d307b55 100644
--- a/giscanner/ast.py
+++ b/giscanner/ast.py
@@ -25,7 +25,7 @@ from itertools import chain
 from . import message
 
 from .message import Position
-from .odict import odict
+from .odict import OrderedDict
 from .utils import to_underscores
 
 class Type(object):
@@ -367,7 +367,7 @@ class Namespace(object):
             self.symbol_prefixes = [to_underscores(p).lower() for p in ps]
         # cache upper-cased versions
         self._ucase_symbol_prefixes = [p.upper() for p in self.symbol_prefixes]
-        self.names = odict() # Maps from GIName -> node
+        self.names = OrderedDict() # Maps from GIName -> node
         self.aliases = {} # Maps from GIName -> GIName
         self.type_names = {} # Maps from GTName -> node
         self.ctypes = {} # Maps from CType -> node
diff --git a/giscanner/odict.py b/giscanner/odict.py
index fa164c3..f955895 100644
--- a/giscanner/odict.py
+++ b/giscanner/odict.py
@@ -16,35 +16,102 @@
 # License along with this library; if not, write to the
 # Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 # Boston, MA 02111-1307, USA.
+
+
+# Borrowed from:
+# http://hg.sqlalchemy.org/sqlalchemy/raw-file/77e2264283d4/lib/sqlalchemy/util/_collections.py
+# http://hg.sqlalchemy.org/sqlalchemy/raw-file/77e2264283d4/AUTHORS
+#
+# util/_collections.py
+# Copyright (C) 2005-2012 the SQLAlchemy authors and contributors <see AUTHORS file>
 #
+# This module is part of SQLAlchemy and is released under
+# the MIT License: http://www.opensource.org/licenses/mit-license.php
+class OrderedDict(dict):
+    """A dict that returns keys/values/items in the order they were added."""
+
+    def __init__(self, ____sequence=None, **kwargs):
+        self._list = []
+        if ____sequence is None:
+            if kwargs:
+                self.update(**kwargs)
+        else:
+            self.update(____sequence, **kwargs)
+
+    def clear(self):
+        self._list = []
+        dict.clear(self)
+
+    def copy(self):
+        return self.__copy__()
+
+    def __copy__(self):
+        return OrderedDict(self)
+
+    def sort(self, *arg, **kw):
+        self._list.sort(*arg, **kw)
+
+    def update(self, ____sequence=None, **kwargs):
+        if ____sequence is not None:
+            if hasattr(____sequence, 'keys'):
+                for key in ____sequence.keys():
+                    self.__setitem__(key, ____sequence[key])
+            else:
+                for key, value in ____sequence:
+                    self[key] = value
+        if kwargs:
+            self.update(kwargs)
+
+    def setdefault(self, key, value):
+        if key not in self:
+            self.__setitem__(key, value)
+            return value
+        else:
+            return self.__getitem__(key)
+
+    def __iter__(self):
+        return iter(self._list)
+
+    def values(self):
+        return [self[key] for key in self._list]
 
-"""odict - an ordered dictionary"""
+    def itervalues(self):
+        return iter([self[key] for key in self._list])
 
-try:
-    # Starting with Python 2.7 we can use collections.OrderedDict
-    from collections import OrderedDict as odict
-except ImportError:
-    # But we still support Python 2.5 and 2.6
-    from UserDict import DictMixin
+    def keys(self):
+        return list(self._list)
 
+    def iterkeys(self):
+        return iter(self.keys())
 
-    class odict(DictMixin):
+    def items(self):
+        return [(key, self[key]) for key in self.keys()]
 
-        def __init__(self):
-            self._items = {}
-            self._keys = []
+    def iteritems(self):
+        return iter(self.items())
 
-        def __setitem__(self, key, value):
-            if key not in self._items:
-                self._keys.append(key)
-            self._items[key] = value
+    def __setitem__(self, key, obj):
+        if key not in self:
+            try:
+                self._list.append(key)
+            except AttributeError:
+                # work around Python pickle loads() with
+                # dict subclass (seems to ignore __setstate__?)
+                self._list = [key]
+        dict.__setitem__(self, key, obj)
 
-        def __getitem__(self, key):
-            return self._items[key]
+    def __delitem__(self, key):
+        dict.__delitem__(self, key)
+        self._list.remove(key)
 
-        def __delitem__(self, key):
-            del self._items[key]
-            self._keys.remove(key)
+    def pop(self, key, *default):
+        present = key in self
+        value = dict.pop(self, key, *default)
+        if present:
+            self._list.remove(key)
+        return value
 
-        def keys(self):
-            return self._keys[:]
+    def popitem(self):
+        item = dict.popitem(self)
+        self._list.remove(item[0])
+        return item