bionic: reimplement property area as hybrid trie/binary tree

See the comments for an explanation of how properties are stored.

The trie structure is designed to scale better than the previous
array-based implementation.  Searching an array with n properties
required average O(n) string compares of the entire key; searching the
trie requires average O(log n) string compares of each token (substrings
between '.' characters).

Signed-off-by: Greg Hackmann <>

(cherry picked from commit 6ac8e6a46d71a51bec16938efa89f275fa89cf7d)

Change-Id: Icbe31908572f33b4d9b85d5b62ac837cbd0f85e0
2 files changed