Loading...
--- dyld/dyld-960/common/PerfectHash.cpp
+++ dyld/dyld-1340/common/PerfectHash.cpp
@@ -40,10 +40,18 @@
------------------------------------------------------------------------------
*/
+#include <TargetConditionals.h>
+
+#if !TARGET_OS_EXCLAVEKIT
+
+#include <strings.h>
#include "PerfectHash.h"
-#if BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS
-#include <dispatch/dispatch.h>
+#if BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS || BUILDING_CACHE_BUILDER_UNIT_TESTS
+#include <string>
+#include <vector>
+
+#include "Algorithm.h"
#endif
namespace objc {
@@ -176,6 +184,8 @@
return c;
}
+#if BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS || BUILDING_CACHE_BUILDER_UNIT_TESTS
+
/*
------------------------------------------------------------------------------
This generates a minimal perfect hash function. That means, given a
@@ -324,19 +334,17 @@
* put keys in tabb according to key->b_k
* check if the initial hash might work
*/
-static int inittab(dyld3::OverflowSafeArray<bstuff>& tabb, dyld3::OverflowSafeArray<key>& keys, int complete)
+static int inittab(dyld3::OverflowSafeArray<bstuff>& tabb, std::span<key> keys)
// bstuff *tabb; /* output, list of keys with b for (a,b) */
// ub4 blen; /* length of tabb */
// key *keys; /* list of keys already hashed */
-// int complete; /* TRUE means to complete init despite collisions */
-{
- int nocollision = TRUE;
+{
ub4 i;
- memset((void *)tabb.begin(), 0, (size_t)(sizeof(bstuff)*tabb.maxCount()));
+ memset((void *)tabb.data(), 0, (size_t)(sizeof(bstuff)*tabb.count()));
/* Two keys with the same (a,b) guarantees a collision */
- for (i = 0; i < keys.count(); i++) {
+ for (i = 0; i < keys.size(); i++) {
key *mykey = &keys[i];
key *otherkey;
@@ -346,9 +354,7 @@
{
if (mykey->a_k == otherkey->a_k)
{
- nocollision = FALSE;
- if (!complete)
- return FALSE;
+ return FALSE;
}
}
++tabb[mykey->b_k].listlen_b;
@@ -357,12 +363,12 @@
}
/* no two keys have the same (a,b) pair */
- return nocollision;
+ return true;
}
/* Do the initial hash for normal mode (use lookup and checksum) */
-static void initnorm(dyld3::OverflowSafeArray<key>& keys, ub4 alen, ub4 blen, ub4 smax, ub8 salt)
+static void initnorm(std::span<key> allKeys, ub4 alen, ub4 blen, ub4 smax, ub8 salt)
// key *keys; /* list of all keys */
// ub4 alen; /* (a,b) has a in 0..alen-1, a power of 2 */
// ub4 blen; /* (a,b) has b in 0..blen-1, a power of 2 */
@@ -371,27 +377,18 @@
// gencode *final; /* output, code for the final hash */
{
ub4 loga = log2u(alen); /* log based 2 of blen */
-#if BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS
- dispatch_apply(keys.count(), DISPATCH_APPLY_AUTO, ^(size_t index) {
- ub4 i = (ub4)index;
- key *mykey = &keys[i];
- ub8 hash = lookup8(mykey->name1_k, mykey->len1_k, salt);
- if ( mykey->name2_k != nullptr ) {
- ub8 hash2 = lookup8(mykey->name2_k, mykey->len2_k, salt);
- hash = hash ^ hash2;
+ size_t chunkSize = 0x2000;
+ mapReduce(allKeys, chunkSize, ^(size_t chunkIndex, int&, std::span<key> keys) {
+ for ( auto& mykey : keys ) {
+ ub8 hash = lookup8(mykey.name1_k, mykey.len1_k, salt);
+ if ( mykey.name2_k != nullptr ) {
+ ub8 hash2 = lookup8(mykey.name2_k, mykey.len2_k, salt);
+ hash = hash ^ hash2;
+ }
+ mykey.a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
+ mykey.b_k = (blen > 1) ? (hash & (blen-1)) : 0;
}
- mykey->a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
- mykey->b_k = (blen > 1) ? (hash & (blen-1)) : 0;
});
-#else
- for (size_t index = 0; index != keys.count(); ++index) {
- ub4 i = (ub4)index;
- key *mykey = &keys[i];
- ub8 hash = lookup8(mykey->name_k, mykey->len_k, salt);
- mykey->a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
- mykey->b_k = (blen > 1) ? (hash & (blen-1)) : 0;
- };
-#endif
}
@@ -690,7 +687,7 @@
/* Try to find distinct (A,B) for all keys */
*salt = si * 0x9e3779b97f4a7c13LL; /* golden ratio (arbitrary value) */
initnorm(keys, *alen, blen, smax, *salt);
- rslinit = inittab(tabb, keys, FALSE);
+ rslinit = inittab(tabb, keys);
if (rslinit == 0)
{
/* didn't find distinct (a,b) */
@@ -782,20 +779,18 @@
}
}
-#if BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS
-
-void PerfectHash::make_perfect(const string_map& strings, objc::PerfectHash& phash)
+void PerfectHash::make_perfect(const std::vector<ObjCString>& strings, objc::PerfectHash& phash)
{
dyld3::OverflowSafeArray<key> keys;
/* read in the list of keywords */
keys.reserve(strings.size());
- size_t i;
- string_map::const_iterator s;
- for (i = 0, s = strings.begin(); s != strings.end(); ++s, ++i) {
+
+ for ( const ObjCString& stringAndOffset: strings ) {
+ const std::string_view& str = stringAndOffset.first;
key mykey;
- mykey.name1_k = (ub1 *)s->first;
- mykey.len1_k = (ub4)strlen(s->first);
+ mykey.name1_k = (ub1 *)str.data();
+ mykey.len1_k = (ub4)str.size();
mykey.name2_k = (ub1 *)nullptr;
mykey.len2_k = (ub4)0;
keys.push_back(mykey);
@@ -804,29 +799,8 @@
make_perfect(keys, phash);
}
-#endif
-
-void PerfectHash::make_perfect(const dyld3::OverflowSafeArray<const char*>& strings, objc::PerfectHash& phash)
-{
- dyld3::OverflowSafeArray<key> keys;
-
- /* read in the list of keywords */
- keys.reserve(strings.count());
- for (const char* s : strings) {
- key mykey;
-#if BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS
- mykey.name1_k = (ub1 *)s;
- mykey.len1_k = (ub4)strlen(s);
- mykey.name2_k = (ub1 *)nullptr;
- mykey.len2_k = (ub4)0;
-#else
- mykey.name_k = (ub1 *)s;
- mykey.len_k = (ub4)strlen(s);
-#endif
- keys.push_back(mykey);
- }
-
- make_perfect(keys, phash);
-}
+#endif // BUILDING_CACHE_BUILDER || BUILDING_UNIT_TESTS || BUILDING_CACHE_BUILDER_UNIT_TESTS
} // namespace objc
+
+#endif // !TARGET_OS_EXCLAVEKIT