Add a basic hashtable data structure, with tests!
The basic hashtable is intended to be used to support a variety
of different datastructures such as map, set, multimap,
multiset, linkedmap, generationcache, etc.
Consequently its interface is fairly primitive.
The basic hashtable supports copy-on-write style functionality
using SharedBuffer.
The change introduces a simple generic function in TypeHelpers for
specifying hash functions. The idea is to add template
specializations of hash_type<T> next to the relevant data structures
such as String8, String16, sp<T>, etc.
Change-Id: I2c479229e9d4527b4fbfe3b8b04776a2fd32c973
diff --git a/libs/utils/primes.py b/libs/utils/primes.py
new file mode 100755
index 0000000..e161dd8
--- /dev/null
+++ b/libs/utils/primes.py
@@ -0,0 +1,47 @@
+#!/usr/bin/env python2.6
+#
+# Copyright (C) 2011 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+#
+# Generates a table of prime numbers for use in BasicHashtable.cpp.
+#
+# Each prime is chosen such that it is a little more than twice as large as
+# the previous prime in the table. This makes it easier to choose a new
+# hashtable size when the underlying array is grown by as nominal factor
+# of two each time.
+#
+
+def is_odd_prime(n):
+ limit = (n - 1) / 2
+ d = 3
+ while d <= limit:
+ if n % d == 0:
+ return False
+ d += 2
+ return True
+
+print "static size_t PRIMES[] = {"
+
+n = 5
+max = 2**31 - 1
+while n < max:
+ print " %d," % (n)
+ n = n * 2 + 1
+ while not is_odd_prime(n):
+ n += 2
+
+print " 0,"
+print "};"