hw/arm/virt: parameter passing cleanups
[qemu.git] / scripts / ordereddict.py
1 # Copyright (c) 2009 Raymond Hettinger
2 #
3 # Permission is hereby granted, free of charge, to any person
4 # obtaining a copy of this software and associated documentation files
5 # (the "Software"), to deal in the Software without restriction,
6 # including without limitation the rights to use, copy, modify, merge,
7 # publish, distribute, sublicense, and/or sell copies of the Software,
8 # and to permit persons to whom the Software is furnished to do so,
9 # subject to the following conditions:
10 #
11 # The above copyright notice and this permission notice shall be
12 # included in all copies or substantial portions of the Software.
13 #
14 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
16 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
17 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
18 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
19 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
21 # OTHER DEALINGS IN THE SOFTWARE.
22
23 from UserDict import DictMixin
24
25
26 class OrderedDict(dict, DictMixin):
27
28 def __init__(self, *args, **kwds):
29 if len(args) > 1:
30 raise TypeError('expected at most 1 arguments, got %d' % len(args))
31 try:
32 self.__end
33 except AttributeError:
34 self.clear()
35 self.update(*args, **kwds)
36
37 def clear(self):
38 self.__end = end = []
39 end += [None, end, end] # sentinel node for doubly linked list
40 self.__map = {} # key --> [key, prev, next]
41 dict.clear(self)
42
43 def __setitem__(self, key, value):
44 if key not in self:
45 end = self.__end
46 curr = end[1]
47 curr[2] = end[1] = self.__map[key] = [key, curr, end]
48 dict.__setitem__(self, key, value)
49
50 def __delitem__(self, key):
51 dict.__delitem__(self, key)
52 key, prev, next = self.__map.pop(key)
53 prev[2] = next
54 next[1] = prev
55
56 def __iter__(self):
57 end = self.__end
58 curr = end[2]
59 while curr is not end:
60 yield curr[0]
61 curr = curr[2]
62
63 def __reversed__(self):
64 end = self.__end
65 curr = end[1]
66 while curr is not end:
67 yield curr[0]
68 curr = curr[1]
69
70 def popitem(self, last=True):
71 if not self:
72 raise KeyError('dictionary is empty')
73 if last:
74 key = reversed(self).next()
75 else:
76 key = iter(self).next()
77 value = self.pop(key)
78 return key, value
79
80 def __reduce__(self):
81 items = [[k, self[k]] for k in self]
82 tmp = self.__map, self.__end
83 del self.__map, self.__end
84 inst_dict = vars(self).copy()
85 self.__map, self.__end = tmp
86 if inst_dict:
87 return (self.__class__, (items,), inst_dict)
88 return self.__class__, (items,)
89
90 def keys(self):
91 return list(self)
92
93 setdefault = DictMixin.setdefault
94 update = DictMixin.update
95 pop = DictMixin.pop
96 values = DictMixin.values
97 items = DictMixin.items
98 iterkeys = DictMixin.iterkeys
99 itervalues = DictMixin.itervalues
100 iteritems = DictMixin.iteritems
101
102 def __repr__(self):
103 if not self:
104 return '%s()' % (self.__class__.__name__,)
105 return '%s(%r)' % (self.__class__.__name__, self.items())
106
107 def copy(self):
108 return self.__class__(self)
109
110 @classmethod
111 def fromkeys(cls, iterable, value=None):
112 d = cls()
113 for key in iterable:
114 d[key] = value
115 return d
116
117 def __eq__(self, other):
118 if isinstance(other, OrderedDict):
119 if len(self) != len(other):
120 return False
121 for p, q in zip(self.items(), other.items()):
122 if p != q:
123 return False
124 return True
125 return dict.__eq__(self, other)
126
127 def __ne__(self, other):
128 return not self == other