Associative containers

In addition to the sequenced containers , fbl:: offers two types of "associative" container:

  • HashTable is an unordered associative container.
  • WAVLTree is an ordered associative container.

Associative containers associate each object in the container with a key whose type and properties can be specified by the user. Elements can be found or removed using this key, and in the case of the WAVLTree, the order of enumeration will be determined by this key and its properties. Since HashTable is an unordered container, the order of enumeration is not guaranteed to be anything in particular.

Please refer to Setting up build dependencies for details on which files need to be included in order to use the various container types.

This section of the guide will show you how to

  1. Define keys for objects, and teach containers how to access them
  2. Control how keys are used by your container using trait classes
  3. Add elements to your container
  4. Remove elements from your container
  5. Find elements in your container
  6. Handling collisions while adding elements
  7. Update the key of an element while it is in a container

Defining a key type and providing access to the container

Like node state, keys for objects held in associative containers are intrusive properties of the object itself. They are not static members of the node state, and do not technically require any extra storage in the object, they simply need to be computable from the object in a consistent and deterministic fashion. The easiest way to expose a key to a container is to allow the container to use the default key traits, and to implement a GetKey function. Here is an example:

class Obj : public fbl::WAVLTreeContainable<Obj*>  {
 public:
  explicit Obj(uint32_t awesomeness) : awesomeness_(awesomeness) {}
  uint32_t GetKey() const { return awesomeness_; }

 private:
  const uint32_t awesomeness_;
};

using ObjSortedByAwesomeness = fbl::WAVLTree<uint32_t, Obj*>;

Here, a container has been defined, which is keyed using 32 bit unsigned integers, and which will end up holding a collection of Objs sorted by ascending awesomeness. There are rules that need to be obeyed.

  1. The GetKey method needs to be const.
  2. Whenever an object is in the associative container, the GetKey method must be consistent. Each time it is called, it needs to return the same value.

In this example, we guarantee that rule 2 is followed by making the awesomeness_ member of our object const. While this is an easy way to prevent mistakes, it is not always a practical approach for some code.

Keys may sometimes need to be mutable, see Updating the key of an object while it is in a container for information on how to properly handle this pattern.

Controlling key behavior with key traits

By default, keys need to be copyable types with a defined == operator for a HashTable, and defined < and == operators for a WAVLTree. When used in an ordered container (the WAVLTree) the objects will be stored in ascending order. What if you wanted to take more control of this? What if your type was not copyable, or if you wanted to sort in descending instead of ascending order?

For this, you can use custom key traits class. As with custom node traits, you need to define a struct or class that exposes three public static methods, which can be used to fetch a key from an object, and to compare those keys. Here is an example:

struct Endpoint {
  // Move only, for some reason
  Endpoint() = default;
  Endpoint(const Endpoint&) = delete;
  Endpoint& operator=(const Endpoint&) = delete;
  Endpoint(Endpoint&&) = default;
  Endpoint& operator=(Endpoint&&) = default;

  uint32_t ipv4_addr_{0};
  uint16_t ipv4_port_{0};
};

class Obj : public WAVLTreeContainable<Obj*> {
 public:
  // ...

 private:
  struct EndpointKeyTraits {
    static const Endpoint& GetKey(const Obj& obj) const { return obj.ep_; }
    static bool LessThan(const Endpoint& ep1, const Endpoint& ep2) {
        return (ep1.ipv4_addr_ > ep2.ipv4_addr_) ||
               ((ep1.ipv4_addr_ == ep2.ipv4_addr_) &&
                (ep1.ipv4_port_ > ep2.ipv4_port_));
    }

    static bool EqualTo(const Endpoint& ep1, const Endpoint& ep2) {
        return (ep1.ipv4_addr_ == ep2.ipv4_addr_) &&
               (ep1.ipv4_port_ == ep2.ipv4_port_);
    }
  };

  friend struct EndpointKeyTraits;

  Endpoint ep_;

 public:
  using ByEndpointMap = fbl::WAVLTree<Endpoint, Obj*, EndpointKeyTraits>;
};

Obj::ByEndpointMap objs_by_descending_endpoint_;

The traits tell the container both where to find the key, as well as how to order the keys. In this example, a constant reference to the Endpoint in GetKey is returned instead of a copy, avoiding the issue that Endpoints are move-only. Additionally, the sense of the LessThan operation is inverted, resulting in a tree that holds objects in descending Endpoint order instead of ascending. The LessThan and EqualTo operations defined by the user are required to be deterministic, transitive, and commutative. In other words:

  • Performing a comparison operation for the same pair of keys multiple times must always return the same results.
  • LessThan(A, B) and LessThan(B, C) implies LessThan(A, C)
  • EqualTo(A, B) and EqualTo(B, C) implies EqualTo(A, C)
  • EqualTo(A, B) if-and-only-if EqualTo(B, A)
  • LessThan(A, B) if-and-only-if (not LessThan(B, A))
  • not LessThan(A, B) if-and-only-if EqualTo(B, A) or LessThan(B, A)

Adding elements to an associative container

Because associative containers do not maintain a specific sequence defined by a user's operations, adding elements to an associative container is a more straight-forward process. Simply call insert on the container passing the appropriate type of pointer. As with the sequenced containers, managed pointers may either be copied, or moved in order to transfer ownership of the pointer to the container.

class Obj : public fbl::RefCounted<Obj>,
            public fbl::WAVLTreeContainable<fbl::RefPtr<Obj>> {
 public:
  explicit Obj(int val) : val_(val) {}
  int val() const { return val_; }
  int GetKey() const { return val(); }
 private:
  const int val_;
};

fbl::WAVLTree<int, fbl::RefPtr<Obj>> objects;

for (int i = 0; i < 100; ++i) {
  fbl::RefPtr<Obj> obj_ref = fbl::MakeRefPtr<Obj>(i);
  if (i % 2) {
    // For odd numbered elements, move our reference directly into the
    // collection of objects.
    objects.insert(std::move(obj_ref));
  } else {
    // For even number elements, make a copy of our pointer (so, another
    // AddRef), and then give away our reference to someone else.
    objects.insert(obj_ref);
    TakeEvenElementReference(std::move(obj_ref));
  }
}

Removing elements from an associative container

As noted earlier, elements in an associative container either have their enumeration order determined by key (WAVLTree), or do not have a guaranteed enumeration order (HashTable). They still have an enumeration order, however, and therefore a front() and a back(). Because of this, the methods used to remove elements from a fbl:: associative collection are identical to those for a DoublyLinkedList, just without the erase_next.

  • pop_front()
  • pop_back()
  • erase(Iter or Obj&)
  • clear()

As the usage example would be very similar to those of the sequenced containers, they have been omitted for brevity.

Finding elements in an associative container

Members of associative containers can be located by key when present in the container using the find(Key) method. The computational complexity of the find operation is O(log n) for the WAVLTree. Hashtables use linked list chaining for conflict resolution, so their find operation is technically an O(n) operation, however performance can approximate O(1) if there are enough buckets relative to N, and the hash function is flat.

If no element with the desired key exists in the container, the value of end() for the container will be returned instead.

void PrintValueForKey(const SomeAssociativeContainerType& container, KeyType key) {
  auto iter = container.find(key);
  if (iter.IsValid()) {
    cout << "Found val (" << iter->val() << "for Key (" << key << ") in the container.\n";
  } else {
    cout << "Key (" << key << ") was not found in the container.\n";
  }
}

Because it is an ordered associative container, WAVLTree also supports upper_bound(Key) and lower_bound(Key) operations, in keeping with the std:: APIs.

  • lower_bound(Key) find the first element in the container with a key greater than or equal to the provided key.
  • upper_bound(Key) find the first element in the container with a key strictly greater than the provided key.
// Given a set of objects whose keys are initially
// "1 5 25 67 100"
fbl::WAVLTree<uint32_t, std::unique_ptr<Obj>> objects;
fbl::WAVLTree<uint32_t, std::unique_ptr<Obj>>::iterator iter;

iter = objects.lower_bound(5);    // iter->GetKey() == 5
iter = objects.upper_bound(5);    // iter->GetKey() == 25
iter = objects.lower_bound(26);   // iter->GetKey() == 67
iter = objects.upper_bound(26);   // iter->GetKey() == 67
iter = objects.lower_bound(100);  // iter->GetKey() == 100
iter = objects.upper_bound(100);  // (iter == objects.end()) && !iter.IsValid()
iter = objects.lower_bound(101);  // (iter == objects.end()) && !iter.IsValid()

Handling collisions in associative containers

Like std::map, associative containers in fbl:: require that the set of keys in the container be unique. No collisions are allowed. If a collision occurs during an insert operation, it will trigger a ZX_DEBUG_ASERT or result in undefined behavior of debug asserts are not enabled.

So, how can insertion in an environment where collisions might take place be handled? Two methods are provided that allow us to efficiently control the behavior of insertion when a collision occurs. They are:

  • insert_or_find
  • insert_or_replace

If no collision occurs, then these are both the equivalent of a simple insert. Otherwise, insert_or_find will not perform the insertion and can return an iterator to the object that your insert collided with if desired. The function returns a bool, which indicates a successful insert (no collision) when true.

insert_or_replace will simply replace the element in the container and give back to you a reference to the object you collided with, or a nullptr version of your pointer type in the case of no collision. So, in code this looks like the following:

// Attempt to insert an object into the container, but do nothing in the case of
// a collision.
Obj* ptr = GetAnObj();
container.insert_or_find(ptr);

// Attempt to insert an object into the container.  In the case of collision,
// the reference stored in ptr will not be consumed.  Put it back and log a
// message about the collision.
ContainerType::iterator collided;
std::unique_ptr<Obj> ptr = GetAnObj();
if (!container.insert_or_find(std::move(ptr), &collided)) {
  ASSERT(ptr.get() != nullptr);
  ASSERT(collided.IsValid());
  printf("Collided with obj \"%s\" when trying to insert obj \"%s\"\n",
         collided->name(), ptr->name());
  PutAnObjBack(std::move(ptr));
}

// Attempt to insert an object into the container, replacing whatever was there
// before and letting the reference to the replaced object drop on the ground,
// destroying the object if this was a managed pointer and the last reference to
// the object.
std::unique_ptr<Obj> ptr = GetAnObj();
container.insert_or_replace(std::move(ptr));

// Attempt to insert an object into the container, recovering the object
// replaced in the case of a collision.
std::unique_ptr<Obj> ptr = GetAnObj();
std::unique_ptr<Obj> replaced = container.insert_or_replace(std::move(ptr));
if (replaced != nullptr) {
  // We collided and replaced the element we collided with. Put this object
  // back.
  PutAnObjBack(std::move(replaced));
}

Updating the key of an object while it is in a container

In the example given in the section about how to define the key used by a container, an object's awesomeness was a constant property of the object. The value of a key cannot be allowed to change while the key is present in the container without violating the container's invariants and producing undefined behavior. A key can change, however while the object is not in its container without any trouble. Let's update the previous example to allow mutable awesomeness and see what it would look like to update the awesomeness of an Obj in a container.

class Obj : public fbl::WAVLTreeContainable<Obj*>  {
 public:
  explicit Obj(uint32_t awesomeness) : awesomeness_(awesomeness) {}
  uint32_t GetKey() const { return awesomeness; }

  void UpdateAwesomeness(uint32_t awesomeness) {
    ZX_DEBUG_ASSERT(!InContainer());
    awesomeness_ = awesomeness;
  }

 private:
  uint32_t awesomeness_;
};

fbl::WAVLTree<uint32_t, Obj*> all_objs;

void UpdateAwesomeness(Obj& obj, uint32_t new_val) {
  ZX_DEBUG_ASSERT(obj.InContainer());
  all_objs.erase(obj);
  UpdateAwesomeness(new_val);
  all_objs.insert(*obj);
}

Note that (to prevent accidents) the example asserts that an object being updated is not in the container at the time that the value of the key is changed. InContainer is implemented by the object's WAVLTreeContainable mix-in and may be invoked from the UpdateAwesomeness() by simply saying InContainer().

Also that there is no need to find the object in the tree before removing it. Given a reference to the object to be updated, it is already known where the object is in the container's internal structure because of the intrusive nature of the container.