1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 // 5 // A combined list/hash set for read or write-blocked entities. 6 7 #ifndef NET_QUIC_BLOCKED_LIST_H_ 8 #define NET_QUIC_BLOCKED_LIST_H_ 9 10 #include <list> 11 12 #include "base/containers/hash_tables.h" 13 #include "base/logging.h" 14 15 namespace net { 16 17 template <typename Object> 18 class BlockedList { 19 public: 20 // Called to add an object to the blocked list. This indicates 21 // the object should be notified when it can use the socket again. 22 // 23 // If this object is already on the list, it will not be added again. 24 void AddBlockedObject(Object object) { 25 // Only add the object to the list if we successfully add it to the set. 26 if (object_set_.insert(object).second) { 27 object_list_.push_back(object); 28 } 29 } 30 31 // Called to remove an object from a blocked list. This should be 32 // called in the event the object is being deleted before the list is. 33 void RemoveBlockedObject(Object object) { 34 // Remove the object from the set. We'll check the set before calling 35 // OnCanWrite on a object from the list. 36 // 37 // There is potentially ordering unfairness should a session be removed and 38 // then readded (as it keeps its position in the list) but it's not worth 39 // the overhead to walk the list and remove it. 40 object_set_.erase(object); 41 } 42 43 // Called when the socket is usable and some objects can access it. Returns 44 // the first object and removes it from the list. 45 Object GetNextBlockedObject() { 46 DCHECK(!IsEmpty()); 47 48 // Walk the list to find the first object which was not removed from the 49 // set. 50 while (!object_list_.empty()) { 51 Object object = *object_list_.begin(); 52 object_list_.pop_front(); 53 int removed = object_set_.erase(object); 54 if (removed > 0) { 55 return object; 56 } 57 } 58 59 // This is a bit of a hack: It's illegal to call GetNextBlockedObject() if 60 // the list is empty (see DCHECK above) but we must return something. This 61 // compiles for ints (returns 0) and pointers in the case that someone has a 62 // bug in their call site. 63 return 0; 64 }; 65 66 // Returns the number of objects in the blocked list. 67 int NumObjects() { 68 return object_set_.size(); 69 }; 70 71 // Returns true if there are no objects in the list, false otherwise. 72 bool IsEmpty() { 73 return object_set_.empty(); 74 }; 75 76 private: 77 // A set tracking the objects. This is the authoritative container for 78 // determining if an object is blocked. Objects in the list will always 79 // be in the set. 80 base::hash_set<Object> object_set_; 81 // A list tracking the order in which objects were added to the list. 82 // Objects are added to the back and pulled off the front, but only get 83 // resumption calls if they're still in the set. 84 // It's possible to be in the list twice, but only the first entry will get an 85 // OnCanWrite call. 86 std::list<Object> object_list_; 87 }; 88 89 } // namespace net 90 91 #endif // NET_QUIC_BLOCKED_LIST_H_ 92
