From 35c87f2b8e5cc62c91a3bdbaec4de50d366f6228 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Thu, 16 Sep 2010 19:10:17 +0000
Subject: Issue 9865:  add __sizeof__ to OrderedDict.

---
 Lib/collections.py           | 31 ++++++++++++++++++++-----------
 Lib/test/test_collections.py |  6 ++++++
 Misc/NEWS                    |  2 ++
 3 files changed, 28 insertions(+), 11 deletions(-)

diff --git a/Lib/collections.py b/Lib/collections.py
index 68e9b28..f05d7b4 100644
--- a/Lib/collections.py
+++ b/Lib/collections.py
@@ -97,17 +97,6 @@ class OrderedDict(dict, MutableMapping):
             yield curr.key
             curr = curr.prev
 
-    def __reduce__(self):
-        'Return state information for pickling'
-        items = [[k, self[k]] for k in self]
-        tmp = self.__map, self.__root, self.__hardroot
-        del self.__map, self.__root, self.__hardroot
-        inst_dict = vars(self).copy()
-        self.__map, self.__root, self.__hardroot = tmp
-        if inst_dict:
-            return (self.__class__, (items,), inst_dict)
-        return self.__class__, (items,)
-
     def clear(self):
         'od.clear() -> None.  Remove all items from od.'
         root = self.__root
@@ -162,6 +151,26 @@ class OrderedDict(dict, MutableMapping):
             link.next = first
             root.next = first.prev = link
 
+    def __reduce__(self):
+        'Return state information for pickling'
+        items = [[k, self[k]] for k in self]
+        tmp = self.__map, self.__root, self.__hardroot
+        del self.__map, self.__root, self.__hardroot
+        inst_dict = vars(self).copy()
+        self.__map, self.__root, self.__hardroot = tmp
+        if inst_dict:
+            return (self.__class__, (items,), inst_dict)
+        return self.__class__, (items,)
+
+    def __sizeof__(self):
+        sizeof = _sys.getsizeof
+        n = len(self) + 1                       # number of links including root
+        size = sizeof(self.__dict__)            # instance dictionary
+        size += sizeof(self.__map) * 2          # internal dict and inherited dict
+        size += sizeof(self.__hardroot) * n     # link objects
+        size += sizeof(self.__root) * n         # proxy objects
+        return size
+
     setdefault = MutableMapping.setdefault
     update = MutableMapping.update
     pop = MutableMapping.pop
diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py
index 514dc39..51e93e4 100644
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -994,6 +994,12 @@ class TestOrderedDict(unittest.TestCase):
         with self.assertRaises(KeyError):
             od.move_to_end('x')
 
+    def test_sizeof(self):
+        # Wimpy test: Just verify the reported size is larger than a regular dict
+        d = dict(a=1)
+        od = OrderedDict(**d)
+        self.assertGreater(sys.getsizeof(od), sys.getsizeof(d))
+
 class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
     type2test = OrderedDict
 
diff --git a/Misc/NEWS b/Misc/NEWS
index 60b62b2..1903cb6 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -52,6 +52,8 @@ Core and Builtins
 Library
 -------
 
+- Issue #9865:  collections.OrderedDict now has a __sizeof__ method.
+
 - Issue #9854: The default read() implementation in io.RawIOBase now
   handles non-blocking readinto() returning None correctly.
 
-- 
cgit v0.12