ryu/build/lib.linux-armv7l-2.7/ryu/services/protocols/bgp/utils/circlist.py

   1 # Copyright (C) 2014 Nippon Telegraph and Telephone Corporation.
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #    http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
  12 # implied.
  13 # See the License for the specific language governing permissions and
  14 # limitations under the License.
  15
  16 import six
  17 if six.PY3:
  18     from sys import intern
  19
  20
  21 class CircularListType(object):
  22     """Instances of this class represent a specific type of list.
  23     Nodes are linked in a circular fashion, using attributes on the
  24     nodes themselves.
  25
  26     Example:
  27
  28       ItemList = CircularListType(next_attr='_next',
  29                                   prev_attr='_prev')
  30
  31       l = ItemList()
  32       l.prepend(item)
  33
  34     The created list has the following properties:
  35
  36       - A node can be inserted O(1) time at the head, tail, or
  37         after/before another specified node.
  38
  39       - A node can be removed in O(1) time from any list it may be on,
  40         without providing a reference to the list.
  41
  42       - The current node in an iteration can be deleted safely.
  43
  44      """
  45
  46     class List(object):
  47         """An object that represents a list.
  48
  49         This class is not expected to be used directly by clients. Rather, they
  50         would use the 'create' method of a CircularListType object to create an
  51         instance.
  52         """
  53
  54         # Define the set of valid attributes so as to make the list
  55         # head lightweight.
  56         #
  57         # We override __getattr__ and __setattr__ so as to store the
  58         # the next and previous references on the list head in
  59         # _next_slot_ and _prev_slot_ respectively.
  60         __slots__ = ["list_type", "head", "_next_slot_",
  61                      "_prev_slot_"]
  62
  63         def __init__(self, list_type):
  64             self.list_type = list_type
  65
  66             # Save memory by using the List object itself as the head.
  67             self.head = self
  68             self.list_type.node_init(self.head)
  69
  70         def __getattr__(self, name):
  71             if(name == self.list_type.next_name):
  72                 return self._next_slot_
  73
  74             if(name == self.list_type.prev_name):
  75                 return self._prev_slot_
  76
  77             raise AttributeError(name)
  78
  79         def __setattr__(self, name, value):
  80             if(name in CircularListType.List.__slots__):
  81                 object.__setattr__(self, name, value)
  82                 return
  83
  84             if(name == self.list_type.next_name):
  85                 self._next_slot_ = value
  86                 return
  87
  88             if(name == self.list_type.prev_name):
  89                 self._prev_slot_ = value
  90                 return
  91
  92             raise AttributeError(name)
  93
  94         def is_empty(self):
  95             return not self.list_type.node_is_on_list(self.head)
  96
  97         def clear(self):
  98             """Remove all items from the list."""
  99
 100             # Make sure that all items are unlinked.
 101             for node in self:
 102                 self.remove(node)
 103
 104         def is_on_list(self, node):
 105             return self.list_type.node_is_on_list(node)
 106
 107         def append(self, node):
 108             self.list_type.node_insert_before(self.head, node)
 109
 110         def prepend(self, node):
 111             self.list_type.node_insert_after(self.head, node)
 112
 113         def __iter__(self):
 114             return self.generator()
 115
 116         def remove(self, node):
 117             """List the given node from the list.
 118
 119             Note that this does not verify that the node is on this
 120             list. It could even be on a different list.
 121             """
 122             self.list_type.node_unlink(node)
 123
 124             self.list_type.node_del_attrs(node)
 125
 126         def pop_first(self):
 127             """Remove the first item in the list and return it."""
 128             node = self.list_type.node_next(self.head)
 129             if(node is self.head):
 130                 return None
 131
 132             self.remove(node)
 133             return node
 134
 135         def generator(self):
 136             """Enables iteration over the list.
 137
 138             The current item can safely be removed from the list during
 139             iteration.
 140             """
 141             # Keep a pointer to the next node when returning the
 142             # current node. This allows the caller to remove the
 143             # current node safely.
 144             node = self.list_type.node_next(self.head)
 145             next = self.list_type.node_next(node)
 146             while(node is not self.head):
 147                 yield node
 148
 149                 node = next
 150                 next = self.list_type.node_next(node)
 151
 152     #
 153     # CircularListType methods
 154     #
 155
 156     def __init__(self, next_attr_name=None, prev_attr_name=None):
 157         """Initializes this list.
 158
 159         next_attr_name: The name of the attribute that holds a reference
 160                         to the next item in the list.
 161
 162         prev_attr_name: the name of the attribute that holds a reference
 163                         to the previous item in the list.
 164         """
 165
 166         # Keep an interned version of the attribute names. This should
 167         # speed up the process of looking up the attributes.
 168         self.next_name = intern(next_attr_name)
 169         self.prev_name = intern(prev_attr_name)
 170
 171     def create(self):
 172         return CircularListType.List(self)
 173
 174     def __call__(self):
 175         """Make a CircularListType instance look like a class by
 176         creating a list object.
 177         """
 178         return self.create()
 179
 180     def node_init(self, node):
 181         assert(not self.node_is_on_list(node))
 182
 183         # Set the node to point to itself as the previous and next
 184         # entries.
 185         self.node_set_next(node, node)
 186         self.node_set_prev(node, node)
 187
 188     def node_next(self, node):
 189         try:
 190             return getattr(node, self.next_name)
 191         except AttributeError:
 192             return None
 193
 194     def node_set_next(self, node, next):
 195         setattr(node, self.next_name, next)
 196
 197     def node_prev(self, node):
 198         try:
 199             return getattr(node, self.prev_name)
 200         except AttributeError:
 201             return None
 202
 203     def node_set_prev(self, node, prev):
 204         setattr(node, self.prev_name, prev)
 205
 206     def node_del_attrs(self, node):
 207         """Remove all attributes that are used for putting this node
 208         on this type of list.
 209         """
 210         try:
 211             delattr(node, self.next_name)
 212             delattr(node, self.prev_name)
 213         except AttributeError:
 214             pass
 215
 216     def node_is_on_list(self, node):
 217         """Returns True if this node is on *some* list.
 218
 219         A node is not on any list if it is linked to itself, or if it
 220         does not have the next and/prev attributes at all.
 221         """
 222         next = self.node_next(node)
 223         if next == node or next is None:
 224             assert(self.node_prev(node) is next)
 225             return False
 226
 227         return True
 228
 229     def node_insert_after(self, node, new_node):
 230         """Insert the new node after node."""
 231
 232         assert(not self.node_is_on_list(new_node))
 233         assert(node is not new_node)
 234
 235         next = self.node_next(node)
 236         assert(next is not None)
 237         self.node_set_next(node, new_node)
 238         self.node_set_prev(new_node, node)
 239
 240         self.node_set_next(new_node, next)
 241         self.node_set_prev(next, new_node)
 242
 243     def node_insert_before(self, node, new_node):
 244         """Insert the new node before node."""
 245
 246         assert(not self.node_is_on_list(new_node))
 247         assert(node is not new_node)
 248
 249         prev = self.node_prev(node)
 250         assert(prev is not None)
 251         self.node_set_prev(node, new_node)
 252         self.node_set_next(new_node, node)
 253
 254         self.node_set_prev(new_node, prev)
 255         self.node_set_next(prev, new_node)
 256
 257     def node_unlink(self, node):
 258
 259         if not self.node_is_on_list(node):
 260             return
 261
 262         prev = self.node_prev(node)
 263         next = self.node_next(node)
 264
 265         self.node_set_next(prev, next)
 266         self.node_set_prev(next, prev)
 267
 268         self.node_set_next(node, node)
 269         self.node_set_prev(node, node)