OSDN Git Service

bionic: reimplement property area as hybrid trie/binary tree
authorGreg Hackmann <ghackmann@google.com>
Thu, 20 Jun 2013 18:27:56 +0000 (11:27 -0700)
committerGreg Hackmann <ghackmann@google.com>
Mon, 24 Jun 2013 20:14:09 +0000 (13:14 -0700)
commit6ac8e6a46d71a51bec16938efa89f275fa89cf7d
tree774b64dd8a3c9a9c9390eefd073d1c993269ef69
parenta82388354867435bfac443bd0239cad25b4511b5
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).

Change-Id: I491305bc7aca59609abcd871a5f33d97f89ce714
Signed-off-by: Greg Hackmann <ghackmann@google.com>
libc/bionic/system_properties.c
libc/include/sys/_system_properties.h