2015年8月

实现锁屏的方法,其实上网一搜一大把,无非是告诉你在Screen Off的时候启动某个Activity,同时把Keyguard禁用掉,但是通常情况下,似乎很难解决HOME键能解锁的这么一个问题,今天我们就来讲一个方案,就是如何近乎完美的实现我们的锁屏。

我们知道,锁屏的界面显示是使用KeyguardViewManager进行添加的,但是这个类属于Android的内部类,我们调用不到,它属于com.android.internal.policy.impl这个包,源码地址:https://github.com/android/platform_frameworks_policies_base/blob/master/phone/com/android/internal/policy/impl/KeyguardViewManager.java

我们可以看到它似乎是使用WindowManager添加View的方式实现了锁屏界面的添加,而不是使用传统的Activity的方式。

那么使用WindowManager是我们可行的方案,它的好处就是可以屏蔽Home键的触发,同时可以做一些特殊的动画效果。

我们首先开启一个Service,在Service中注册SREEN_OFF的广播,触发广播的时候,使用WindowManager加入锁屏页面,实现锁屏即可。
看下我们的Receiver代码:

if (action.equals(Intent.ACTION_SCREEN_OFF)) {
    ViewParent viewParent = mContainer.getParent();
    if (viewParent != null) {
        return;
    }

    mKeyguardLock.disableKeyguard();
    WindowManager windowManager = (WindowManager)getSystemService(WINDOW_SERVICE);
    WindowManager.LayoutParams lp = generateLayoutParams();
    windowManager.addView(mContainer, lp);
}


 private WindowManager.LayoutParams generateLayoutParams() {
    WindowManager windowManager = (WindowManager)getSystemService(WINDOW_SERVICE);
    Display display = windowManager.getDefaultDisplay();
    Point size = new Point();
    display.getSize(size);

    WindowManager.LayoutParams lp = new WindowManager.LayoutParams();
    lp.type = WindowManager.LayoutParams.TYPE_SYSTEM_ALERT;
    lp.flags |= WindowManager.LayoutParams.FLAG_SHOW_WHEN_LOCKED | WindowManager.LayoutParams.FLAG_LAYOUT_IN_SCREEN;
    lp.x = 0;
    lp.y = 0;
    lp.format = PixelFormat.TRANSLUCENT;
    return lp;
}

这里主要的是需要设置WindowManager的布局参数(LayoutParams),如果看WindowManager的源码的话,我们可以看见它的TYPE有一个TYPE_KEYGUARD,这就是系统锁屏用的类型了,但是它不提供给外部使用,因此我们只能使用级别比较高的TYPE_SYSTEM_ALERT,覆盖到锁屏的上面。format设置成TRANSLUCENT的原因是我们需要和锁屏交互的时候,锁屏后面的界面要显示出来,所以它是一个透明的层,这里没有办法,我们只能把一些交互的代码放到需要添加的View层中进行处理。

使用这种方式实现的锁屏,能较好的和Launcher或者其他界面交互(包括渐变、过渡等),而且能使得我们的锁屏界面不响应HOME键(使用Activity的方式的话,home会让我们进入到Launcher里)。

更多的内容我正在探索,敬请期待。

欢迎关注我Github 以及 @Gemini

今天开始看LevelDB的源码,看了几个大大小小的数据结构,印象深刻的应该是SkipList了,作为一个典型的以空间换时间的有序链表 相比平衡二叉树而言,还是简单了不少的(对于大多数操作需要O(log n)平均时间)。
SkipList是一个二维空间的链表。

找了个比较形象的图:

clipboard.png

Skip List的定义

SkipList的定义:

  1. 一个跳表应该有几个层(level)组成;
  2. 跳表的第一层包含所有的元素;
  3. 每一层都是一个有序的链表;
  4. 如果元素x出现在第i层,则所有比i小的层都包含x;
  5. 第i层的元素通过一个down指针指向下一层拥有相同值的元素;
  6. 在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX);
  7. Top指针指向最高层的第一个元素。

然后我们看看LevelDB中是如何实现它的。
首先看下层级的定义,LevelDB中定义了一个SkipList最高层级为12。

enum { kMaxHeight = 12 };

然后层级越高的链中数据越少,也就是说,从下面数上去,最底下一层我们定义为第0层,它拥有所有的数据,它是一条严格递增的链表, 也是我们传统意义上的链表。如果我们在里面找数据,那需要花去O(n)的时间。

结点Node的定义

在LevelDB中,每一个节点用一个Node对象进行存储。Node的定义很简单,抛去一些原子操作,实际上它就是二维链上某个结点,其中包含了所有层级的信息,我们看下它的定义:

template<typename Key, class Comparator>
struct SkipList<Key,Comparator>::Node {
  explicit Node(const Key& k) : key(k) { }

  Key const key;

  // Accessors/mutators for links.  Wrapped in methods so we can
  // add the appropriate barriers as necessary.
  Node* Next(int n) {
    assert(n >= 0);
    // Use an 'acquire load' so that we observe a fully initialized
    // version of the returned Node.
    return reinterpret_cast<Node*>(next_[n].Acquire_Load());
  }
  void SetNext(int n, Node* x) {
    assert(n >= 0);
    // Use a 'release store' so that anybody who reads through this
    // pointer observes a fully initialized version of the inserted node.
    next_[n].Release_Store(x);
  }

  // No-barrier variants that can be safely used in a few locations.
  Node* NoBarrier_Next(int n) {
    assert(n >= 0);
    return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
  }
  void NoBarrier_SetNext(int n, Node* x) {
    assert(n >= 0);
    next_[n].NoBarrier_Store(x);
  }

 private:
  // Array of length equal to the node height.  next_[0] is lowest level link.
  port::AtomicPointer next_[1];
};

template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node*
SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
  char* mem = arena_->AllocateAligned(
      sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
  return new (mem) Node(key);
}

这块其实特别少,它最后用了弹性指针的方式来对不同高度的Node进行不同内存的分配(这里的arena是LevelDB中的内存池,附带了对齐的特性,以后介绍),从而达到节省内存和优化对CPU缓存的目的。

插入结点

我们来简单看一个插入结点的操作。

template<typename Key, class Comparator>
void SkipList<Key,Comparator>::Insert(const Key& key) {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);

  assert(x == NULL || !Equal(key, x->key));

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);

    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (NULL), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since NULL sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
  }

  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    // NoBarrier_SetNext() suffices since we will add a barrier when
    // we publish a pointer to "x" in prev[i].
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

这段代码的幽默感其实蛮强= = 我一开始不太理解RandomHeight的意义,后来查了一些资料才知道SkipList就是概率性的进行分层——我获取一个height的随机数,当然它是有要求的,就是在0和kMaxHeight之间,然后,我插入的这个结点就在0-height层上都分布了,同时需要修改前缀的指针(如果超越了当前的max_height_,那么同时也要修改max_height_)。

这里耗费的空间可能是O(n*kMaxHeight)了,然后浪费了这么多资源,目的当然是为了高效的读嘛,我们来看下它的读取操作是怎么做的。

读取Node

这段代码是读取大于等于key的第一个结点(并把所有层级上在key前面的结点记录到prev数组里)

template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)
    const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != NULL) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}

我们的逻辑从最高层开始,我们已知最高层的结点分布是稀疏的,那么利用KeyIsAfterNode函数进行比较。

  1. 在当前level,如果下一个结点的key比我要比较的key大,到步骤2。
  2. 如果到底层了,返回下一个结点,否则降级,再执行1。

因为当前的x结点的下一个层级必然还是x结点,但是它的下一个结点的情况却是未知,因此把低层级的next结点和key进行比较,如此循环,我们就能利用稀疏的链迅速的在密集的链表中找到我们要的元素。

经过整体分析和理解,其实SkipList还是很简单的,最终也是利用了空间换时间的方法。只是它的生成有概率性,但是和平衡二叉树(AVL Tree)比起来,它整体的性价比还是非常可观的~

PS: Google的cpp代码真的很浅显易懂,稍微思考下,做一下笔记,就能明白其中的道理,真的很棒!(也许是LevelDB本身就很简单= =)

欢迎关注我Github 以及 @Gemini