页面

分类

一种Observer的实现

2017/8/24, by wingfire ; 分类: 计算机技术, 代码相关; 0 comments

Observer 模式是很常用的,但是要想实现得正确,并不容易.一个常见但并不很容易解决的问题是在Notify的过程中添加或删除Observer.

一般而言,对于一个目标,可以注册多个观察员对象,这就需要某种列表来记录,这个列表通常可以作为目标的数据成员来实现的.当需要发出通知时,代码大致如下

for(auto& v : observers)
    v.notify(event);

这段代码很简单,但是可能遇到问题,取决于notify的行为。若notify内还会注册/注销观察者,其效果就相当于在遍历的循环内修改了被遍历的容器的元素,若observers的类型是C++ 的std::vector,那将导致未定义行为。即使是std::list,若注销的恰好为当前的观察者,也会导致迭代器失效。而要想避免这种错误,实现起来并不容易。

上述错误发生的前提之一是遍历期间修改了容器,因此,如果在notify实际并不会修改容器,那就没什么问题。虽然API层面上无法保证不被误用,但可以增加一些检查加以防范:

void changed(const event &e){
  assert(!this->is_notifying);
  this->is_notifying = true;
  for(auto& v : observers)
    v.notify(e);
  this->is_notifying = false;
}

void register(observer_type o){
   assert(!this->is_notifying);
   observers.emplace_back(std::move(o));
}

void unregister(observer_type o){
   assert(!this->is_notifying);
   observers.emplace_back(std::move(o));
   observers.erase(std::remove(observers.begin(), observers.end(), o), observers.end());
}

注意,上述代码假设observer_type是可以判等的,std::function显然不满足要求.changed函数不是异常安全的,所以应该写成:

void changed(const event &e){
  assert(!this->is_notifying);
  var_saver guard(this->is_notifying, true);

  for(auto& v : observers)
    v.notify(e);
}

那如果需要允许notify内部注册注销呢?一种可行但低效的做法是,在遍历之前先复制:

void changed(const event &e){
  auto tmp = observers;
  for(auto& v : tmp)
    v.notify(e);
}

这么做的代价可能是相当昂贵的,尤其是当changed发生得非常频繁的时候.还有另外一个问题,即删除的observer不能及时得到处置,仍然可能被发送消息,这可能会带来恼人的结果.为了效率,能否既及时处置注销的观察者又不复制observers呢?

先试试看list类型,似乎简单一些:

void changed(const event &e){
  for(auto i = observers.begin(); i != observers.end(); ){
    auto& v = *i++;
    v.notify(e);
  }
}

可惜,这是错的. i虽然提前递进了,但是无法保证删的不是i所指的那一个,实际上,i无法定位到一个安全的位置上去。嗯,似乎还有办法:

void changed(const event &e){
  for(size_t i = 0; i < observers.size(); ++i){
    auto& v= observers[i];
    v.notify(e);
  }
}

这里observer的类型是vector,这段代码不会导致未定义行为.是不是没问题了?仍然不是.

如果在notify期间删除了在i之前的观察者,导致vector后面的元素都前移,这样在遍历的时候当前i后面的一个将被跳过.这种不确定性是难以被接受的.也不能通过检查observers.size()来察觉这一点,因为notify可以既删又加.

比较一下上述两种方法的得失,因为每一个observer都是特定的,下标法虽然避免了未定义行为,却丢失了observer的身份信息,iterator法的问题是虽然保住了身份信息,却没料到对象自己被删。因此修补的方法是对于下标法,要补记录观察者标志信息,对于iterator法,要将对象身份信息和对象本身脱钩。这两个方法的修订版就变得一致起来:以一种标记法标记observer,标记不依赖observer对象而存在。直观的表示法是

struct item{
   T identify;
   bool is_removed;
   observer_type* observer;
};

上面代码中的类型T应该是什么?原则上,可以是为observer分配的序号,字符串名称,或任何其他类似的东西。但是一个天然的identify就是observer的地址,因此T的类型可以取observer_type*.另外,is_removed可以通过把observer设为nullptr来表示,可以去掉。于是修改为:

struct item1{
   observer_type* identify;
   observer_type* observer;
};

这和下述表示本质上等价:

struct item2{
   bool is_removed;
   observer_type* observer;
};

对于上述定义,unregester都不立即将其从observers中删除,两者的区别在于,对于item1,把observer置为nullptr,identify不动,item2则把is_removed置为true,observer不动.于是changed可以实现为:

void changed(const event &e){
  for(size_t i = 0; i < observers.size(); ++i){
    auto& v= observers[i];
    if (!v.is_removed)
        v.observer->notify(e);
  }

  //注意: 不能在此清理observers中is_removed的项

}

实际上item1/2如果不马上删除,那本身就可以充当observer的identity,因此可以进一步简化为:

std::vector<observer_type*> observers;

void changed(const event &e){
  for(size_t i = 0; i < observers.size(); ++i){
    auto v= observers[i];
    if (v != nullptr)
        v->notify(e);
  }
}

void register(observer_type* observer){
   assert(!contains_(observer));
   observers.emplace_back(observer);
}

void unregister(observer_type* observer){
   assert(contains_(observer));
   auto pos = std::find(observers.begin(), observers.end(), observer);
   *pos = nullptr;
}

实际上,直接得到上面最后的结果也并不困难.剩下的问题是什么时候从observers中实际删除已删除的那些observer呢?这需要在相关函数中中判断一下,是否处于递归过程中,如果不处于递归,就执行实际的删除操作。那如何知道是否处于递归呢?一个简单的方法是计数。

struct counter_guard{
    int & counter;
    counter_guard(int& c) : counter(c){++counter;} 
    ~counter_guard(){--counter;}
};

int enter_counter;

void changed(const event &e){
  counter_guard guard(enter_counter);
  bool has_removed = false;
  for(size_t i = 0; i < observers.size(); ++i){
    auto v= observers[i];
    if (v != nullptr)
        v->notify(e);
    else
        has_removed = true;
  }

  if (has_removed && enter_counter == 1)
    observers.erase(std::remove(observers.begin(), observers.end(), nullptr), observers.end());

}

void register(observer_type* observer){
   assert(!contains_(observer));
   counter_guard guard(enter_counter);
   observers.emplace_back(observer);
}

void unregister(observer_type* observer){
   assert(contains_(observer));
   counter_guard guard(enter_counter);
   auto pos = std::find(observers.begin(), observers.end(), observer);
   if (enter_counter == 1)
     observers.erase(pos);   // no recursive
   else
     *pos = nullptr;    // in recursive
}

如果只在unregister中处理删除节点是不够的,因为真正导致递归的只是changed函数。相对来说changed是会被频繁调用的,因此将真正的删除放在changed中完成。要注意到上面changed中has_removed的计算并不精确,如果在迭代第i个观察者时,前面的某个被注销了,has_remove并不能感知,也就不会删除,要到下一次触发changed才能实际检测到。这样的实现是基于下述假设:

  • unregester相对发生概率低
  • 延迟做实际删除并无重大影响

以上是针对单线程情形下的分析和实现。对于多线程,则情况还要复杂得多,需要引入递归锁对执行线程进行保护。注意不能使用可升级的递归读写锁,因为递归过的顶层过程已经占有读锁,底层是不可能成功升级为排它锁的,这将导致死锁.即便锁的实现支持升级本线程的读锁为写锁,两个线程的竞争也将导致死锁无法避免.

添加评论:

 
 the email would not displayed
 

您可以使用 Markdown 语法。

您必须启用浏览器的 JavaScript 功能才能发表评论。