[v2,04/21] qapi: add ordereddict/qapi.py helper libraries

diff --git a/scripts/ordereddict.py b/scripts/ordereddict.py
new file mode 100644
index 0000000..e17269f
--- /dev/null
+++ b/scripts/ordereddict.py
@@ -0,0 +1,128 @@ 
+# Copyright (c) 2009 Raymond Hettinger
+#
+# Permission is hereby granted, free of charge, to any person
+# obtaining a copy of this software and associated documentation files
+# (the "Software"), to deal in the Software without restriction,
+# including without limitation the rights to use, copy, modify, merge,
+# publish, distribute, sublicense, and/or sell copies of the Software,
+# and to permit persons to whom the Software is furnished to do so,
+# subject to the following conditions:
+#
+#     The above copyright notice and this permission notice shall be
+#     included in all copies or substantial portions of the Software.
+#
+#     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+#     EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+#     OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+#     NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+#     HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+#     WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+#     FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+#     OTHER DEALINGS IN THE SOFTWARE.
+
+from UserDict import DictMixin
+
+class OrderedDict(dict, DictMixin):
+
+    def __init__(self, *args, **kwds):
+        if len(args) > 1:
+            raise TypeError('expected at most 1 arguments, got %d' % len(args))
+        try:
+            self.__end
+        except AttributeError:
+            self.clear()
+        self.update(*args, **kwds)
+
+    def clear(self):
+        self.__end = end = []
+        end += [None, end, end]         # sentinel node for doubly linked list
+        self.__map = {}                 # key --> [key, prev, next]
+        dict.clear(self)
+
+    def __setitem__(self, key, value):
+        if key not in self:
+            end = self.__end
+            curr = end[1]
+            curr[2] = end[1] = self.__map[key] = [key, curr, end]
+        dict.__setitem__(self, key, value)
+
+    def __delitem__(self, key):
+        dict.__delitem__(self, key)
+        key, prev, next = self.__map.pop(key)
+        prev[2] = next
+        next[1] = prev
+
+    def __iter__(self):
+        end = self.__end
+        curr = end[2]
+        while curr is not end:
+            yield curr[0]
+            curr = curr[2]
+
+    def __reversed__(self):
+        end = self.__end
+        curr = end[1]
+        while curr is not end:
+            yield curr[0]
+            curr = curr[1]
+
+    def popitem(self, last=True):
+        if not self:
+            raise KeyError('dictionary is empty')
+        if last:
+            key = reversed(self).next()
+        else:
+            key = iter(self).next()
+        value = self.pop(key)
+        return key, value
+
+    def __reduce__(self):
+        items = [[k, self[k]] for k in self]
+        tmp = self.__map, self.__end
+        del self.__map, self.__end
+        inst_dict = vars(self).copy()
+        self.__map, self.__end = tmp
+        if inst_dict:
+            return (self.__class__, (items,), inst_dict)
+        return self.__class__, (items,)
+
+    def keys(self):
+        return list(self)
+
+    setdefault = DictMixin.setdefault
+    update = DictMixin.update
+    pop = DictMixin.pop
+    values = DictMixin.values
+    items = DictMixin.items
+    iterkeys = DictMixin.iterkeys
+    itervalues = DictMixin.itervalues
+    iteritems = DictMixin.iteritems
+
+    def __repr__(self):
+        if not self:
+            return '%s()' % (self.__class__.__name__,)
+        return '%s(%r)' % (self.__class__.__name__, self.items())
+
+    def copy(self):
+        return self.__class__(self)
+
+    @classmethod
+    def fromkeys(cls, iterable, value=None):
+        d = cls()
+        for key in iterable:
+            d[key] = value
+        return d
+
+    def __eq__(self, other):
+        if isinstance(other, OrderedDict):
+            if len(self) != len(other):
+                return False
+            for p, q in  zip(self.items(), other.items()):
+                if p != q:
+                    return False
+            return True
+        return dict.__eq__(self, other)
+
+    def __ne__(self, other):
+        return not self == other
+
diff --git a/scripts/qapi.py b/scripts/qapi.py
new file mode 100644
index 0000000..422b6bd
--- /dev/null
+++ b/scripts/qapi.py
@@ -0,0 +1,181 @@ 
+from ordereddict import OrderedDict
+
+def tokenize(data):
+    while len(data):
+        if data[0] in ['{', '}', ':', ',', '[', ']']:
+            yield data[0]
+            data = data[1:]
+        elif data[0] in ' \n':
+            data = data[1:]
+        elif data[0] == "'":
+            data = data[1:]
+            string = ''
+            while data[0] != "'":
+                string += data[0]
+                data = data[1:]
+            data = data[1:]
+            yield string
+
+def parse(tokens):
+    if tokens[0] == '{':
+        ret = OrderedDict()
+        tokens = tokens[1:]
+        while tokens[0] != '}':
+            key = tokens[0]
+            tokens = tokens[1:]
+
+            tokens = tokens[1:] # :
+
+            value, tokens = parse(tokens)
+
+            if tokens[0] == ',':
+                tokens = tokens[1:]
+
+            ret[key] = value
+        tokens = tokens[1:]
+        return ret, tokens
+    elif tokens[0] == '[':
+        ret = []
+        tokens = tokens[1:]
+        while tokens[0] != ']':
+            value, tokens = parse(tokens)
+            if tokens[0] == ',':
+                tokens = tokens[1:]
+            ret.append(value)
+        tokens = tokens[1:]
+        return ret, tokens
+    else:
+        return tokens[0], tokens[1:]
+
+def evaluate(string):
+    return parse(map(lambda x: x, tokenize(string)))[0]
+
+def parse_schema(fp):
+    exprs = []
+    expr = ''
+
+    for line in fp:
+        if line.startswith('#') or line == '\n':
+            continue
+
+        if line.startswith(' '):
+            expr += line
+        elif expr:
+            exprs.append(evaluate(expr))
+            expr = line
+        else:
+            expr += line
+
+    if expr:
+        exprs.append(evaluate(expr))
+
+    return exprs
+
+def parse_args(typeinfo):
+    for member in typeinfo:
+        argname = member
+        argentry = typeinfo[member]
+        optional = False
+        structured = False
+        if member.startswith('*'):
+            argname = member[1:]
+            optional = True
+        if isinstance(argentry, OrderedDict):
+            structured = True
+        yield (argname, argentry, optional, structured)
+
+def de_camel_case(name):
+    new_name = ''
+    for ch in name:
+        if ch.isupper() and new_name:
+            new_name += '_'
+        if ch == '-':
+            new_name += '_'
+        else:
+            new_name += ch.lower()
+    return new_name
+
+def camel_case(name):
+    new_name = ''
+    first = True
+    for ch in name:
+        if ch in ['_', '-']:
+            first = True
+        elif first:
+            new_name += ch.upper()
+            first = False
+        else:
+            new_name += ch.lower()
+    return new_name
+
+def c_var(name):
+    return '_'.join(name.split('-')).lstrip("*")
+
+def c_list_type(name):
+    return '%sList' % name
+
+def type_name(name):
+    if type(name) == list:
+        return c_list_type(name[0])
+    return name
+
+enum_types = []
+
+def add_enum(name):
+    global enum_types
+    enum_types.append(name)
+
+def is_enum(name):
+    global enum_types
+    return (name in enum_types)
+
+def c_type(name):
+    if name == 'str':
+        return 'char *'
+    elif name == 'int':
+        return 'int64_t'
+    elif name == 'bool':
+        return 'bool'
+    elif name == 'number':
+        return 'double'
+    elif type(name) == list:
+        return '%s *' % c_list_type(name[0])
+    elif is_enum(name):
+        return name
+    elif name == None or len(name) == 0:
+        return 'void'
+    elif name == name.upper():
+        return '%sEvent *' % camel_case(name)
+    else:
+        return '%s *' % name
+
+def genindent(count):
+    ret = ""
+    for i in range(count):
+        ret += " "
+    return ret
+
+indent_level = 0
+
+def push_indent(indent_amount=4):
+    global indent_level
+    indent_level += indent_amount
+
+def pop_indent(indent_amount=4):
+    global indent_level
+    indent_level -= indent_amount
+
+def cgen(code, **kwds):
+    indent = genindent(indent_level)
+    lines = code.split('\n')
+    lines = map(lambda x: indent + x, lines)
+    return '\n'.join(lines) % kwds + '\n'
+
+def mcgen(code, **kwds):
+    return cgen('\n'.join(code.split('\n')[1:-1]), **kwds)
+
+def basename(filename):
+    return filename.split("/")[-1]
+
+def guardname(filename):
+    return filename.replace("/", "_").replace("-", "_").split(".")[0].upper()