obmc/utils/pathtree.py

# Contributors Listed Below - COPYRIGHT 2016
# [+] International Business Machines Corp.
#
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
# implied. See the License for the specific language governing
# permissions and limitations under the License.


class PathTreeItemIterator(object):
    def __init__(self, path_tree, subtree, depth):
        self.path_tree = path_tree
        self.path = []
        self.itlist = []
        self.subtree = ['/'] + list(filter(bool, subtree.split('/')))
        self.depth = depth
        d = path_tree.root
        for k in self.subtree:
            try:
                d = d[k]['children']
            except KeyError:
                raise KeyError(subtree)
        # TODO: openbmc/openbmc#2994 remove python 2 support
        try:  # python 2
            self.it = d.iteritems()
        except AttributeError:  # python 3
            self.it = iter(d.items())

    def __iter__(self):
        return self

    # TODO: openbmc/openbmc#2994 remove python 2 support
    # python 2
    def next(self):
        key, value = self._next()
        path = self.subtree[0] + '/'.join(self.subtree[1:] + self.path)
        return path, value.get('data')

    # python 3
    import sys
    if sys.version_info[0] > 2:
        __next__ = next

    def _next(self):
        try:
            while True:
                x = next(self.it)
                if self.depth:
                    if len(self.path) + 1 > self.depth:
                        continue
                self.itlist.append(self.it)
                self.path.append(x[0])
                # TODO: openbmc/openbmc#2994 remove python 2 support
                try:  # python 2
                    self.it = x[1]['children'].iteritems()
                except AttributeError:  # python 3
                    self.it = iter(x[1]['children'].items())
                break

        except StopIteration:
            if not self.itlist:
                raise StopIteration

            self.it = self.itlist.pop()
            self.path.pop()
            x = self._next()

        return x


class PathTreeKeyIterator(PathTreeItemIterator):
    def __init__(self, path_tree, subtree, depth):
        super(PathTreeKeyIterator, self).__init__(path_tree, subtree, depth)

    # TODO: openbmc/openbmc#2994 remove python 2 support
    # python 2
    def next(self):
        return super(PathTreeKeyIterator, self).next()[0]

    # python 3
    import sys
    if sys.version_info[0] > 2:
        __next__ = next


class PathTree:
    def __init__(self):
        self.root = {}
        self.cache = {}

    def _try_delete_parent(self, elements):
        if len(elements) == 1:
            return False

        kids = 'children'
        elements.pop()
        d = self.root
        for k in elements[:-1]:
            d = d[k][kids]

        if 'data' not in d[elements[-1]] and not d[elements[-1]][kids]:
            del d[elements[-1]]
            self._try_delete_parent(elements)

    def _get_node(self, key):
        kids = 'children'
        elements = ['/'] + list(filter(bool, key.split('/')))
        d = self.root
        for k in elements[:-1]:
            try:
                d = d[k][kids]
            except KeyError:
                raise KeyError(key)

        return d[elements[-1]]

    def __iter__(self):
        return PathTreeItemIterator(self, '/', None)

    def __missing__(self, key):
        for x in self.iterkeys():
            if key == x:
                return False
        return True

    def __delitem__(self, key):
        del self.cache[key]
        kids = 'children'
        elements = ['/'] + list(filter(bool, key.split('/')))
        d = self.root
        for k in elements[:-1]:
            try:
                d = d[k][kids]
            except KeyError:
                raise KeyError(key)

        del d[elements[-1]]
        self._try_delete_parent(elements)

    def __setitem__(self, key, value):
        self.cache[key] = value
        kids = 'children'
        elements = ['/'] + list(filter(bool, key.split('/')))
        d = self.root
        for k in elements[:-1]:
            d = d.setdefault(k, {kids: {}})[kids]

        children = d.setdefault(elements[-1], {kids: {}})[kids]
        d[elements[-1]].update({kids: children, 'data': value})

    def __getitem__(self, key):
        if key in self.cache:
            return self.cache[key]

        return self._get_node(key).get('data')

    def setdefault(self, key, default):
        if not self.get(key):
            self.__setitem__(key, default)

        return self.__getitem__(key)

    def get(self, key, default=None):
        try:
            x = self.__getitem__(key)
        except KeyError:
            x = default

        return x

    def get_children(self, key):
        return [x for x in self._get_node(key)['children'].keys()]

    def demote(self, key):
        n = self._get_node(key)
        if 'data' in n:
            del n['data']

    def keys(self, subtree='/', depth=None):
        return [x for x in self.iterkeys(subtree, depth)]

    def values(self, subtree='/', depth=None):
        return [x[1] for x in self.iteritems(subtree, depth)]

    def items(self, subtree='/', depth=None):
        return [x for x in self.iteritems(subtree, depth)]

    def dataitems(self, subtree='/', depth=None):
        # dataitems() must return an iterable object containing all of the
        # items explicitly inserted into the tree, rooted at subtree with
        # depth number of path elements from the subtree root.
        #
        # Calling dataitems() to request all of the populated entries is
        # unfortunately common, and it's (also) unfortunately expensive to
        # generate (done by iterating over the entire tree). However, given we
        # have a flat dict whose job is to cache the explicitly inserted values
        # we can leverage that to provide a cheap-to-calculate answer to
        # requests for the entire set of populated entries
        if subtree == '/' and not depth:
            return self.cache.items()

        return [x for x in self.iteritems(subtree, depth)
                if x[1] is not None]

    def iterkeys(self, subtree='/', depth=None):
        if not self.root:
            # TODO: openbmc/openbmc#2994 remove python 2 support
            try:  # python 2
                return {}.iterkeys()
            except AttributeError:  # python 3
                return iter({}.keys())
        return PathTreeKeyIterator(self, subtree, depth)

    def iteritems(self, subtree='/', depth=None):
        if not self.root:
            # TODO: openbmc/openbmc#2994 remove python 2 support
            try:  # python 2
                return {}.iteritems()
            except AttributeError:  # python 3
                return iter({}.items())
        return PathTreeItemIterator(self, subtree, depth)

    def dumpd(self, subtree='/'):
        result = {}
        d = result

        for k, v in self.iteritems(subtree):
            elements = ['/'] + list(filter(bool, k.split('/')))
            d = result
            for k in elements:
                d = d.setdefault(k, {})
            if v is not None:
                d.update(v)

        return result