polymorphic method cache example implementation

pmc.cpp

#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <cstdint>
#include <cassert>

struct selector
{
  std::string s;
};
struct method
{
  selector *name;
};
struct klass
{
  std::vector<method*> methods;

  method* lookup (selector* s)
  {
    for(const auto& m: methods)
      if(m->name == s) return m;
    return nullptr;
  }
};


struct pmic
{
  pmic() {}

  struct item
  {
    uintptr_t key;
    klass* c;
    method* m;
  };
  std::vector<item> items;

  method* lookup (klass* c, selector* s)
  {
    uintptr_t key = (uintptr_t)c ^ (uintptr_t)s;
    auto ptr = std::lower_bound(items.begin(), items.end(), key,
      [](item& a, uintptr_t b) {
        return a.key < b;
      }
    );
    for(; ptr != items.end() && ptr->key == key; ++ptr)
      if(ptr->c == c)
        return ptr->m;
    // failed to find method in cache

    // "normal" lookup
    method* m = c->lookup(s);
    if(m)
      // method found, store it
      items.insert(ptr, item{key, c, m});

    return m;
  }

  void dump ()
  {
    for(const auto& x: items)
    std::cout << x.key << ": " << x.m->name->s << " @" << x.c << std::endl;
  }
  
};



int main()
{
  klass *a = new klass, *b = new klass;
  selector *m1 = new selector{"foo"}, *m2 = new selector{"bar"};
  method *a1 = new method{m1}, *a2 = new method{m2},
         *b1 = new method{m1}, *b2 = new method{m2};
  a->methods.push_back(a1);
  a->methods.push_back(a2);
  b->methods.push_back(b1);
  b->methods.push_back(b2);

  pmic p;
  assert(p.lookup(a, m1) == a1);
  assert(p.lookup(b, m1) == b1);
  p.dump();
  std::cout << "----" << std::endl;

  assert(p.lookup(a, m2) == a2);
  assert(p.lookup(b, m2) == b2);
  p.dump();

  return 0;
}