Loading...
--- dyld/dyld-360.21/include/objc-shared-cache.h
+++ dyld/dyld-852/include/objc-shared-cache.h
@@ -81,6 +81,10 @@
*/
#include <stdint.h>
#include <stdlib.h>
+#ifdef CLOSURE_SELOPT_WRITE
+#include "Array.h"
+#include "Map.h"
+#endif
#ifdef SELOPT_WRITE
#include <unordered_map>
#endif
@@ -110,23 +114,23 @@
static uint64_t lookup8( uint8_t *k, size_t length, uint64_t level);
-#ifdef SELOPT_WRITE
+#if defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
// Perfect hash code is at the end of this file.
-struct perfect_hash {
+struct __attribute__((packed)) perfect_hash {
uint32_t capacity;
uint32_t occupied;
uint32_t shift;
uint32_t mask;
uint64_t salt;
+
+ uint32_t scramble[256];
+ dyld3::OverflowSafeArray<uint8_t> tab; // count == mask+1
- uint32_t scramble[256];
- uint8_t *tab; // count == mask+1; free with delete[]
+ perfect_hash() { }
- perfect_hash() : tab(0) { }
-
- ~perfect_hash() { if (tab) delete[] tab; }
+ ~perfect_hash() { }
};
struct eqstr {
@@ -141,25 +145,32 @@
}
};
+#endif // defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
+
+#ifdef SELOPT_WRITE
+
// cstring => cstring's vmaddress
// (used for selector names and class names)
typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> string_map;
// protocol name => protocol vmaddress
-typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> protocol_map;
+typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> legacy_protocol_map;
+
+// protocol name => (protocol vmaddress, header_info vmaddress)
+typedef std::unordered_multimap<const char *, std::pair<uint64_t, uint64_t>, hashstr, eqstr> protocol_map;
// class name => (class vmaddress, header_info vmaddress)
typedef std::unordered_multimap<const char *, std::pair<uint64_t, uint64_t>, hashstr, eqstr> class_map;
-static perfect_hash make_perfect(const string_map& strings);
-
-#endif
+static void make_perfect(const string_map& strings, perfect_hash& phash);
+
+#endif // defined(SELOPT_WRITE)
// Precomputed perfect hash table of strings.
// Base class for precomputed selector table and class table.
-// Edit objc-sel-table.s and OPT_INITIALIZER if you change this structure.
-struct objc_stringhash_t {
+// Edit objc-sel-table.s if you change this structure.
+struct __attribute__((packed)) objc_stringhash_t {
uint32_t capacity;
uint32_t occupied;
uint32_t shift;
@@ -167,7 +178,7 @@
uint32_t unused1; // was zero
uint32_t unused2; // alignment pad
uint64_t salt;
-
+
uint32_t scramble[256];
uint8_t tab[0]; /* tab[mask+1] (always power-of-2) */
// uint8_t checkbytes[capacity]; /* check byte for each string */
@@ -275,7 +286,8 @@
return NULL;
}
- perfect_hash phash = make_perfect(strings);
+ perfect_hash phash;
+ make_perfect(strings, phash);
if (phash.capacity == 0) {
return "perfect hash failed (metadata not optimized)";
}
@@ -332,21 +344,36 @@
#endif
};
-
// Precomputed selector table.
-// Edit objc-sel-table.s and OPT_INITIALIZER if you change this structure.
-struct objc_selopt_t : objc_stringhash_t {
- const char *get(const char *key) const
+// Edit objc-sel-table.s if you change this structure.
+struct objc_selopt_t : objc_stringhash_t {
+
+ const char* getEntryForIndex(uint32_t index) const {
+ return (const char *)this + offsets()[index];
+ }
+
+ uint32_t getIndexForKey(const char *key) const {
+ return getIndex(key);
+ }
+
+ uint32_t getSentinelIndex() const {
+ return INDEX_NOT_FOUND;
+ }
+
+ const char* get(const char *key) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) return NULL;
-
- return (const char *)this + offsets()[h];
+ return getEntryForIndex(h);
+ }
+
+ size_t usedCount() const {
+ return capacity;
}
};
// Precomputed class list.
-// Edit objc-sel-table.s and OPT_INITIALIZER if you change these structures.
+// Edit objc-sel-table.s if you change these structures.
struct objc_classheader_t {
objc_stringhash_offset_t clsOffset;
@@ -376,17 +403,37 @@
objc_classheader_t *duplicateOffsets() { return (objc_classheader_t *)(&duplicateCount()+1); }
const objc_classheader_t *duplicateOffsets() const { return (const objc_classheader_t *)(&duplicateCount()+1); }
+ const char* getClassNameForIndex(uint32_t index) const {
+ return (const char *)this + offsets()[index];
+ }
+
+ void* getClassForIndex(uint32_t index, uint32_t duplicateIndex) const {
+ const objc_classheader_t& clshi = classOffsets()[index];
+ if (! clshi.isDuplicate()) {
+ // class appears in exactly one header
+ return (void *)((const char *)this + clshi.clsOffset);
+ }
+ else {
+ // class appears in more than one header - use getClassesAndHeaders
+ const objc_classheader_t *list = &duplicateOffsets()[clshi.duplicateIndex()];
+ return (void *)((const char *)this + list[duplicateIndex].clsOffset);
+ }
+ }
+
// 0/NULL/NULL: not found
// 1/ptr/ptr: found exactly one
// n/NULL/NULL: found N - use getClassesAndHeaders() instead
- uint32_t getClassAndHeader(const char *key, void*& cls, void*& hi) const
+ uint32_t getClassHeaderAndIndex(const char *key, void*& cls, void*& hi, uint32_t& index) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) {
cls = NULL;
hi = NULL;
+ index = 0;
return 0;
}
+
+ index = h;
const objc_classheader_t& clshi = classOffsets()[h];
if (! clshi.isDuplicate()) {
@@ -426,6 +473,15 @@
}
}
+ // 0/NULL/NULL: not found
+ // 1/ptr/ptr: found exactly one
+ // n/NULL/NULL: found N - use getClassesAndHeaders() instead
+ uint32_t getClassAndHeader(const char *key, void*& cls, void*& hi) const
+ {
+ uint32_t unusedIndex = 0;
+ return getClassHeaderAndIndex(key, cls, hi, unusedIndex);
+ }
+
#ifdef SELOPT_WRITE
size_t size()
@@ -437,7 +493,14 @@
+ duplicateCount() * sizeof(objc_classheader_t);
}
- void byteswap(bool little_endian)
+ size_t sizeWithoutDups()
+ {
+ return
+ objc_stringhash_t::size()
+ + capacity * sizeof(objc_classheader_t);
+ }
+
+ void byteswap(bool little_endian)
{
objc_classheader_t *o;
@@ -464,7 +527,10 @@
const char *err;
err = objc_stringhash_t::write(base, remaining, strings);
if (err) return err;
-
+
+ if (sizeWithoutDups() > remaining) {
+ return "selector section too small (metadata not optimized)";
+ }
if (size() > remaining) {
return "selector section too small (metadata not optimized)";
}
@@ -489,7 +555,7 @@
continue;
}
- uint32_t count = classes.count(c->first);
+ uint32_t count = (uint32_t)classes.count(c->first);
if (count == 1) {
// only one class with this name
@@ -550,7 +616,6 @@
};
-
struct objc_protocolopt_t : objc_stringhash_t {
// ...objc_stringhash_t fields...
// uint32_t protocolOffsets[capacity]; /* offsets from &capacity to protocol_t */
@@ -558,10 +623,10 @@
objc_stringhash_offset_t *protocolOffsets() { return (objc_stringhash_offset_t *)&offsets()[capacity]; }
const objc_stringhash_offset_t *protocolOffsets() const { return (const objc_stringhash_offset_t *)&offsets()[capacity]; }
- void* getProtocol(const char *key) const
+ void* getProtocol(const char *key) const
{
uint32_t h = getIndex(key);
- if (h == INDEX_NOT_FOUND) {
+ if (h == INDEX_NOT_FOUND) {
return NULL;
}
@@ -570,26 +635,26 @@
#ifdef SELOPT_WRITE
- size_t size()
+ size_t size()
{
return
objc_stringhash_t::size() + capacity * sizeof(objc_stringhash_offset_t);
}
- void byteswap(bool little_endian)
+ void byteswap(bool little_endian)
{
objc_stringhash_offset_t *o;
-
+
o = protocolOffsets();
- for (objc_stringhash_offset_t i = 0; i < capacity; i++) {
+ for (objc_stringhash_offset_t i = 0; i < (int)capacity; i++) {
S32(o[i]);
}
objc_stringhash_t::byteswap(little_endian);
}
-
- const char *write(uint64_t base, size_t remaining,
- string_map& strings, protocol_map& protocols,
+
+ const char *write(uint64_t base, size_t remaining,
+ string_map& strings, legacy_protocol_map& protocols,
bool verbose)
{
const char *err;
@@ -604,10 +669,10 @@
for (uint32_t i = 0; i < capacity; i++) {
protocolOffsets()[i] = 0;
}
-
+
// Set real protocol offsets
# define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
- protocol_map::const_iterator c;
+ legacy_protocol_map::const_iterator c;
for (c = protocols.begin(); c != protocols.end(); ++c) {
uint32_t h = getIndex(c->first);
if (h == INDEX_NOT_FOUND) {
@@ -622,7 +687,7 @@
protocolOffsets()[h] = (objc_stringhash_offset_t)offset;
}
# undef SHIFT
-
+
return NULL;
}
@@ -630,26 +695,72 @@
#endif
};
+struct objc_protocolopt2_t : objc_clsopt_t {
+
+ void* getProtocol(const char *key,
+ bool (*callback)(const void* header_info)) const
+ {
+ uint32_t h = getIndex(key);
+ if (h == INDEX_NOT_FOUND) {
+ return NULL;
+ }
+
+ const objc_classheader_t& clshi = classOffsets()[h];
+ if (! clshi.isDuplicate()) {
+ // protocol appears in exactly one header
+ void* cls = (void *)((const char *)this + clshi.clsOffset);
+ void* hi = (void *)((const char *)this + clshi.hiOffset);
+ return callback(hi) ? cls : NULL;
+ }
+ else {
+ // protocol appears in more than one header
+ uint32_t count = clshi.duplicateCount();
+ const objc_classheader_t *list = &duplicateOffsets()[clshi.duplicateIndex()];
+ for (uint32_t i = 0; i < count; i++) {
+ void* cls = (void *)((const char *)this + list[i].clsOffset);
+ void* hi = (void *)((const char *)this + list[i].hiOffset);
+ if (callback(hi))
+ return cls;
+ }
+ return NULL;
+ }
+ }
+
+};
+
// Precomputed image list.
-struct objc_headeropt_t;
+struct objc_headeropt_ro_t;
+
+// Precomputed image list.
+struct objc_headeropt_rw_t;
// Precomputed class list.
struct objc_clsopt_t;
// Edit objc-sel-table.s if you change this value.
-enum { VERSION = 13 };
+// lldb and Symbolication read these structures. Inform them of any changes.
+enum { VERSION = 15 };
+
+// Values for objc_opt_t::flags
+enum : uint32_t {
+ IsProduction = (1 << 0), // never set in development cache
+ NoMissingWeakSuperclasses = (1 << 1) // set in development cache and customer
+};
// Top-level optimization structure.
-// Edit objc-sel-table.s and OPT_INITIALIZER if you change this structure.
+// Edit objc-sel-table.s if you change this structure.
struct alignas(alignof(void*)) objc_opt_t {
uint32_t version;
+ uint32_t flags;
int32_t selopt_offset;
- int32_t headeropt_offset;
+ int32_t headeropt_ro_offset;
int32_t clsopt_offset;
+ int32_t unused_protocolopt_offset; // This is now 0 as we've moved to the new protocolopt_offset
+ int32_t headeropt_rw_offset;
int32_t protocolopt_offset;
- const objc_selopt_t* selopt() const {
+ const objc_selopt_t* selopt() const {
if (selopt_offset == 0) return NULL;
return (objc_selopt_t *)((uint8_t *)this + selopt_offset);
}
@@ -658,9 +769,9 @@
return (objc_selopt_t *)((uint8_t *)this + selopt_offset);
}
- struct objc_headeropt_t* headeropt() const {
- if (headeropt_offset == 0) return NULL;
- return (struct objc_headeropt_t *)((uint8_t *)this + headeropt_offset);
+ struct objc_headeropt_ro_t* headeropt_ro() const {
+ if (headeropt_ro_offset == 0) return NULL;
+ return (struct objc_headeropt_ro_t *)((uint8_t *)this + headeropt_ro_offset);
}
struct objc_clsopt_t* clsopt() const {
@@ -668,28 +779,24 @@
return (objc_clsopt_t *)((uint8_t *)this + clsopt_offset);
}
- struct objc_protocolopt_t* protocolopt() const {
+ struct objc_protocolopt_t* protocolopt() const {
+ if (unused_protocolopt_offset == 0) return NULL;
+ return (objc_protocolopt_t *)((uint8_t *)this + unused_protocolopt_offset);
+ }
+
+ struct objc_protocolopt2_t* protocolopt2() const {
if (protocolopt_offset == 0) return NULL;
- return (objc_protocolopt_t *)((uint8_t *)this + protocolopt_offset);
+ return (objc_protocolopt2_t *)((uint8_t *)this + protocolopt_offset);
+ }
+
+ struct objc_headeropt_rw_t* headeropt_rw() const {
+ if (headeropt_rw_offset == 0) return NULL;
+ return (struct objc_headeropt_rw_t *)((uint8_t *)this + headeropt_rw_offset);
}
};
// sizeof(objc_opt_t) must be pointer-aligned
STATIC_ASSERT(sizeof(objc_opt_t) % sizeof(void*) == 0);
-
-// Initializer for empty opt of type uint32_t[].
-#define X8(x) x, x, x, x, x, x, x, x
-#define X64(x) X8(x), X8(x), X8(x), X8(x), X8(x), X8(x), X8(x), X8(x)
-#define X256(x) X64(x), X64(x), X64(x), X64(x)
-#define OPT_INITIALIZER { \
- /* objc_opt_t */ \
- objc_opt::VERSION, 16, 0, 0, \
- /* objc_selopt_t */ \
- 4, 4, 63, 3, 0, 0, 0,0, X256(0), 0, 0, 16, 16, 16, 16 \
- /* no objc_headeropt_t */ \
- /* no objc_clsopt_t */ \
- /* no objc_protocolopt_t */ \
-}
// List of offsets in libobjc that the shared cache optimization needs to use.
@@ -792,6 +899,8 @@
/*------------------------------------- handle the last 23 bytes */
c += length;
+#pragma clang diagnostic push
+#pragma clang diagnostic ignored "-Wimplicit-fallthrough"
switch(len) /* all the case statements fall through */
{
case 23: c+=((uint64_t)k[22]<<56);
@@ -820,13 +929,14 @@
case 1: a+=((uint64_t)k[ 0]);
/* case 0: nothing left to add */
}
+#pragma clang diagnostic pop
mix64(a,b,c);
/*-------------------------------------------- report the result */
return c;
}
-#ifdef SELOPT_WRITE
+#if defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
/*
------------------------------------------------------------------------------
@@ -988,7 +1098,7 @@
* put keys in tabb according to key->b_k
* check if the initial hash might work
*/
-static int inittab(bstuff *tabb, ub4 blen, key *keys, ub4 nkeys, int complete)
+static int inittab(dyld3::OverflowSafeArray<bstuff>& tabb, dyld3::OverflowSafeArray<key>& keys, int complete)
// bstuff *tabb; /* output, list of keys with b for (a,b) */
// ub4 blen; /* length of tabb */
// key *keys; /* list of keys already hashed */
@@ -997,11 +1107,11 @@
int nocollision = TRUE;
ub4 i;
- memset((void *)tabb, 0, (size_t)(sizeof(bstuff)*blen));
+ memset((void *)tabb.begin(), 0, (size_t)(sizeof(bstuff)*tabb.maxCount()));
/* Two keys with the same (a,b) guarantees a collision */
- for (i = 0; i < nkeys; i++) {
- key *mykey = keys+i;
+ for (i = 0; i < keys.count(); i++) {
+ key *mykey = &keys[i];
key *otherkey;
for (otherkey=tabb[mykey->b_k].list_b;
@@ -1026,7 +1136,7 @@
/* Do the initial hash for normal mode (use lookup and checksum) */
-static void initnorm(key *keys, ub4 nkeys, ub4 alen, ub4 blen, ub4 smax, ub8 salt)
+static void initnorm(dyld3::OverflowSafeArray<key>& keys, 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 */
@@ -1035,18 +1145,31 @@
// gencode *final; /* output, code for the final hash */
{
ub4 loga = log2u(alen); /* log based 2 of blen */
- ub4 i;
- for (i = 0; i < nkeys; i++) {
- key *mykey = keys+i;
+#if BUILDING_CACHE_BUILDER
+ dispatch_apply(keys.count(), DISPATCH_APPLY_AUTO, ^(size_t index) {
+ ub4 i = (ub4)index;
+ key *mykey = &keys[i];
ub8 hash = lookup8(mykey->name_k, mykey->len_k, salt);
- mykey->a_k = (loga > 0) ? 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
}
/* Try to apply an augmenting list */
-static int apply(bstuff *tabb, hstuff *tabh, qstuff *tabq, ub4 blen, ub4 *scramble, ub4 tail, int rollback)
+static int apply(dyld3::OverflowSafeArray<bstuff>& tabb,
+ dyld3::OverflowSafeArray<hstuff>& tabh,
+ dyld3::OverflowSafeArray<qstuff>& tabq,
+ ub4 *scramble, ub4 tail, int rollback)
// bstuff *tabb;
// hstuff *tabh;
// qstuff *tabq;
@@ -1055,52 +1178,52 @@
// ub4 tail;
// int rollback; /* FALSE applies augmenting path, TRUE rolls back */
{
- ub4 hash;
- key *mykey;
- bstuff *pb;
- ub4 child;
- ub4 parent;
- ub4 stabb; /* scramble[tab[b]] */
-
- /* walk from child to parent */
- for (child=tail-1; child; child=parent)
- {
- parent = tabq[child].parent_q; /* find child's parent */
- pb = tabq[parent].b_q; /* find parent's list of siblings */
-
- /* erase old hash values */
- stabb = scramble[pb->val_b];
- for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
- {
- hash = mykey->a_k^stabb;
- if (mykey == tabh[hash].key_h)
- { /* erase hash for all of child's siblings */
- tabh[hash].key_h = (key *)0;
- }
- }
-
- /* change pb->val_b, which will change the hashes of all parent siblings */
- pb->val_b = (rollback ? tabq[child].oldval_q : tabq[child].newval_q);
-
- /* set new hash values */
- stabb = scramble[pb->val_b];
- for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
- {
- hash = mykey->a_k^stabb;
- if (rollback)
- {
- if (parent == 0) continue; /* root never had a hash */
- }
- else if (tabh[hash].key_h)
- {
- /* very rare: roll back any changes */
- apply(tabb, tabh, tabq, blen, scramble, tail, TRUE);
- return FALSE; /* failure, collision */
- }
- tabh[hash].key_h = mykey;
- }
- }
- return TRUE;
+ ub4 hash;
+ key *mykey;
+ bstuff *pb;
+ ub4 child;
+ ub4 parent;
+ ub4 stabb; /* scramble[tab[b]] */
+
+ /* walk from child to parent */
+ for (child=tail-1; child; child=parent)
+ {
+ parent = tabq[child].parent_q; /* find child's parent */
+ pb = tabq[parent].b_q; /* find parent's list of siblings */
+
+ /* erase old hash values */
+ stabb = scramble[pb->val_b];
+ for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
+ {
+ hash = mykey->a_k^stabb;
+ if (mykey == tabh[hash].key_h)
+ { /* erase hash for all of child's siblings */
+ tabh[hash].key_h = (key *)0;
+ }
+ }
+
+ /* change pb->val_b, which will change the hashes of all parent siblings */
+ pb->val_b = (rollback ? tabq[child].oldval_q : tabq[child].newval_q);
+
+ /* set new hash values */
+ stabb = scramble[pb->val_b];
+ for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
+ {
+ hash = mykey->a_k^stabb;
+ if (rollback)
+ {
+ if (parent == 0) continue; /* root never had a hash */
+ }
+ else if (tabh[hash].key_h)
+ {
+ /* very rare: roll back any changes */
+ apply(tabb, tabh, tabq, scramble, tail, TRUE);
+ return FALSE; /* failure, collision */
+ }
+ tabh[hash].key_h = mykey;
+ }
+ }
+ return TRUE;
}
@@ -1123,118 +1246,125 @@
this approach to take about nlogn time to map all single-key b's.
-------------------------------------------------------------------------------
*/
-static int augment(bstuff *tabb, hstuff *tabh, qstuff *tabq, ub4 blen, ub4 *scramble, ub4 smax, bstuff *item, ub4 nkeys,
- ub4 highwater)
+static int augment(dyld3::OverflowSafeArray<bstuff>& tabb,
+ dyld3::OverflowSafeArray<hstuff>& tabh,
+ dyld3::OverflowSafeArray<qstuff>& tabq,
+ ub4 *scramble, ub4 smax, bstuff *item, ub4 nkeys,
+ ub4 highwater)
// bstuff *tabb; /* stuff indexed by b */
// hstuff *tabh; /* which key is associated with which hash, indexed by hash */
// qstuff *tabq; /* queue of *b* values, this is the spanning tree */
-// ub4 blen; /* length of tabb */
// ub4 *scramble; /* final hash is a^scramble[tab[b]] */
// ub4 smax; /* highest value in scramble */
// bstuff *item; /* &tabb[b] for the b to be mapped */
// ub4 nkeys; /* final hash must be in 0..nkeys-1 */
// ub4 highwater; /* a value higher than any now in tabb[].water_b */
{
- ub4 q; /* current position walking through the queue */
- ub4 tail; /* tail of the queue. 0 is the head of the queue. */
- ub4 limit=UB1MAXVAL+1;
- ub4 highhash = smax;
-
- /* initialize the root of the spanning tree */
- tabq[0].b_q = item;
- tail = 1;
-
- /* construct the spanning tree by walking the queue, add children to tail */
- for (q=0; q<tail; ++q)
- {
- bstuff *myb = tabq[q].b_q; /* the b for this node */
- ub4 i; /* possible value for myb->val_b */
-
- if (q == 1)
- break; /* don't do transitive closure */
-
- for (i=0; i<limit; ++i)
- {
- bstuff *childb = (bstuff *)0; /* the b that this i maps to */
- key *mykey; /* for walking through myb's keys */
-
- for (mykey = myb->list_b; mykey; mykey=mykey->nextb_k)
- {
- key *childkey;
- ub4 hash = mykey->a_k^scramble[i];
-
- if (hash >= highhash) break; /* out of bounds */
- childkey = tabh[hash].key_h;
-
- if (childkey)
- {
- bstuff *hitb = &tabb[childkey->b_k];
-
- if (childb)
- {
- if (childb != hitb) break; /* hit at most one child b */
- }
- else
- {
- childb = hitb; /* remember this as childb */
- if (childb->water_b == highwater) break; /* already explored */
- }
- }
- }
- if (mykey) continue; /* myb with i has multiple collisions */
-
- /* add childb to the queue of reachable things */
- if (childb) childb->water_b = highwater;
- tabq[tail].b_q = childb;
- tabq[tail].newval_q = i; /* how to make parent (myb) use this hash */
- tabq[tail].oldval_q = myb->val_b; /* need this for rollback */
- tabq[tail].parent_q = q;
- ++tail;
-
- if (!childb)
- { /* found an *i* with no collisions? */
- /* try to apply the augmenting path */
- if (apply(tabb, tabh, tabq, blen, scramble, tail, FALSE))
- return TRUE; /* success, item was added to the perfect hash */
-
- --tail; /* don't know how to handle such a child! */
- }
- }
- }
- return FALSE;
+ ub4 q; /* current position walking through the queue */
+ ub4 tail; /* tail of the queue. 0 is the head of the queue. */
+ ub4 limit=UB1MAXVAL+1;
+ ub4 highhash = smax;
+
+ /* initialize the root of the spanning tree */
+ tabq[0].b_q = item;
+ tail = 1;
+
+ /* construct the spanning tree by walking the queue, add children to tail */
+ for (q=0; q<tail; ++q)
+ {
+ bstuff *myb = tabq[q].b_q; /* the b for this node */
+ ub4 i; /* possible value for myb->val_b */
+
+ if (q == 1)
+ break; /* don't do transitive closure */
+
+ for (i=0; i<limit; ++i)
+ {
+ bstuff *childb = (bstuff *)0; /* the b that this i maps to */
+ key *mykey; /* for walking through myb's keys */
+
+ for (mykey = myb->list_b; mykey; mykey=mykey->nextb_k)
+ {
+ key *childkey;
+ ub4 hash = mykey->a_k^scramble[i];
+
+ if (hash >= highhash) break; /* out of bounds */
+ childkey = tabh[hash].key_h;
+
+ if (childkey)
+ {
+ bstuff *hitb = &tabb[childkey->b_k];
+
+ if (childb)
+ {
+ if (childb != hitb) break; /* hit at most one child b */
+ }
+ else
+ {
+ childb = hitb; /* remember this as childb */
+ if (childb->water_b == highwater) break; /* already explored */
+ }
+ }
+ }
+ if (mykey) continue; /* myb with i has multiple collisions */
+
+ /* add childb to the queue of reachable things */
+ if (childb) childb->water_b = highwater;
+ tabq[tail].b_q = childb;
+ tabq[tail].newval_q = i; /* how to make parent (myb) use this hash */
+ tabq[tail].oldval_q = myb->val_b; /* need this for rollback */
+ tabq[tail].parent_q = q;
+ ++tail;
+
+ if (!childb)
+ { /* found an *i* with no collisions? */
+ /* try to apply the augmenting path */
+ if (apply(tabb, tabh, tabq, scramble, tail, FALSE))
+ return TRUE; /* success, item was added to the perfect hash */
+
+ --tail; /* don't know how to handle such a child! */
+ }
+ }
+ }
+ return FALSE;
}
/* find a mapping that makes this a perfect hash */
-static int perfect(bstuff *tabb, hstuff *tabh, qstuff *tabq, ub4 blen, ub4 smax, ub4 *scramble, ub4 nkeys)
-{
- ub4 maxkeys; /* maximum number of keys for any b */
- ub4 i, j;
+static int perfect(dyld3::OverflowSafeArray<bstuff>& tabb,
+ dyld3::OverflowSafeArray<hstuff>& tabh,
+ dyld3::OverflowSafeArray<qstuff>& tabq,
+ ub4 smax, ub4 *scramble, ub4 nkeys)
+{
+ ub4 maxkeys; /* maximum number of keys for any b */
+ ub4 i, j;
+
+ const ub4 blen = (ub4)tabb.count();
#if SELOPT_DEBUG
- fprintf(stderr, " blen %d smax %d nkeys %d\n", blen, smax, nkeys);
+ fprintf(stderr, " blen %d smax %d nkeys %d\n", blen, smax, nkeys);
#endif
- /* clear any state from previous attempts */
- memset((void *)tabh, 0, sizeof(hstuff)*smax);
- memset((void *)tabq, 0, sizeof(qstuff)*(blen+1));
-
- for (maxkeys=0,i=0; i<blen; ++i)
- if (tabb[i].listlen_b > maxkeys)
- maxkeys = tabb[i].listlen_b;
-
- /* In descending order by number of keys, map all *b*s */
- for (j=maxkeys; j>0; --j)
- for (i=0; i<blen; ++i)
- if (tabb[i].listlen_b == j)
- if (!augment(tabb, tabh, tabq, blen, scramble, smax, &tabb[i], nkeys,
- i+1))
- {
- return FALSE;
- }
-
- /* Success! We found a perfect hash of all keys into 0..nkeys-1. */
- return TRUE;
+ /* clear any state from previous attempts */
+ memset((void *)tabh.begin(), 0, sizeof(hstuff)*smax);
+ memset((void *)tabq.begin(), 0, sizeof(qstuff)*(blen+1));
+
+ for (maxkeys=0,i=0; i<blen; ++i)
+ if (tabb[i].listlen_b > maxkeys)
+ maxkeys = tabb[i].listlen_b;
+
+ /* In descending order by number of keys, map all *b*s */
+ for (j=maxkeys; j>0; --j)
+ for (i=0; i<blen; ++i)
+ if (tabb[i].listlen_b == j)
+ if (!augment(tabb, tabh, tabq, scramble, smax, &tabb[i], nkeys,
+ i+1))
+ {
+ return FALSE;
+ }
+
+ /* Success! We found a perfect hash of all keys into 0..nkeys-1. */
+ return TRUE;
}
@@ -1296,8 +1426,9 @@
** Return the successful initializer for the initial hash.
** Return 0 if no perfect hash could be found.
*/
-static int findhash(bstuff **tabb, ub4 *alen, ub4 *blen, ub8 *salt,
- ub4 *scramble, ub4 smax, key *keys, ub4 nkeys)
+static int findhash(dyld3::OverflowSafeArray<bstuff>& tabb,
+ ub4 *alen, ub8 *salt,
+ ub4 *scramble, ub4 smax, dyld3::OverflowSafeArray<key>& keys)
// bstuff **tabb; /* output, tab[] of the perfect hash, length *blen */
// ub4 *alen; /* output, 0..alen-1 is range for a of (a,b) */
// ub4 *blen; /* output, 0..blen-1 is range for b of (a,b) */
@@ -1307,91 +1438,84 @@
// key *keys; /* input, keys to hash */
// ub4 nkeys; /* input, number of keys being hashed */
{
- ub4 bad_initkey; /* how many times did initkey fail? */
- ub4 bad_perfect; /* how many times did perfect fail? */
- ub4 si; /* trial initializer for initial hash */
- ub4 maxalen;
- hstuff *tabh; /* table of keys indexed by hash value */
- qstuff *tabq; /* table of stuff indexed by queue value, used by augment */
-
- /* guess initial values for alen and blen */
- initalen(alen, blen, smax, nkeys);
-
- scrambleinit(scramble, smax);
-
- maxalen = smax;
-
- /* allocate working memory */
- *tabb = new bstuff[*blen];
- tabq = new qstuff[*blen+1];
- tabh = new hstuff[smax];
-
- /* Actually find the perfect hash */
- *salt = 0;
- bad_initkey = 0;
- bad_perfect = 0;
- for (si=1; ; ++si)
- {
- ub4 rslinit;
- /* Try to find distinct (A,B) for all keys */
- *salt = si * 0x9e3779b97f4a7c13LL; /* golden ratio (arbitrary value) */
- initnorm(keys, nkeys, *alen, *blen, smax, *salt);
- rslinit = inittab(*tabb, *blen, keys, nkeys, FALSE);
- if (rslinit == 0)
- {
- /* didn't find distinct (a,b) */
- if (++bad_initkey >= RETRY_INITKEY)
- {
- /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
- if (*alen < maxalen)
- {
- *alen *= 2;
- }
- else if (*blen < smax)
- {
- *blen *= 2;
- delete[] tabq;
- delete[] *tabb;
- *tabb = new bstuff[*blen];
- tabq = new qstuff[*blen+1];
- }
- bad_initkey = 0;
- bad_perfect = 0;
- }
- continue; /* two keys have same (a,b) pair */
- }
-
- /* Given distinct (A,B) for all keys, build a perfect hash */
- if (!perfect(*tabb, tabh, tabq, *blen, smax, scramble, nkeys))
- {
- if (++bad_perfect >= RETRY_PERFECT)
- {
- if (*blen < smax)
- {
- *blen *= 2;
- delete[] *tabb;
- delete[] tabq;
- *tabb = new bstuff[*blen];
- tabq = new qstuff[*blen+1];
- --si; /* we know this salt got distinct (A,B) */
- }
- else
- {
- return 0;
- }
- bad_perfect = 0;
- }
- continue;
- }
-
- break;
- }
-
- /* free working memory */
- delete[] tabh;
- delete[] tabq;
-
- return 1;
+ ub4 bad_initkey; /* how many times did initkey fail? */
+ ub4 bad_perfect; /* how many times did perfect fail? */
+ ub4 si; /* trial initializer for initial hash */
+ ub4 maxalen;
+ dyld3::OverflowSafeArray<hstuff>tabh; /* table of keys indexed by hash value */
+ dyld3::OverflowSafeArray<qstuff>tabq; /* table of stuff indexed by queue value, used by augment */
+
+ /* guess initial values for alen and blen */
+ ub4 blen = 0;
+ initalen(alen, &blen, smax, (ub4)keys.count());
+
+ scrambleinit(scramble, smax);
+
+ maxalen = smax;
+
+ /* allocate working memory */
+ tabb.resize(blen);
+ tabq.resize(blen+1);
+ tabh.resize(smax);
+
+ /* Actually find the perfect hash */
+ *salt = 0;
+ bad_initkey = 0;
+ bad_perfect = 0;
+ for (si=1; ; ++si)
+ {
+ ub4 rslinit;
+ /* 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);
+ if (rslinit == 0)
+ {
+ /* didn't find distinct (a,b) */
+ if (++bad_initkey >= RETRY_INITKEY)
+ {
+ /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
+ if (*alen < maxalen)
+ {
+ *alen *= 2;
+ }
+ else if (blen < smax)
+ {
+ blen *= 2;
+ tabb.resize(blen);
+ tabq.resize(blen+1);
+ }
+ bad_initkey = 0;
+ bad_perfect = 0;
+ }
+ continue; /* two keys have same (a,b) pair */
+ }
+
+ /* Given distinct (A,B) for all keys, build a perfect hash */
+ if (!perfect(tabb, tabh, tabq, smax, scramble, (ub4)keys.count()))
+ {
+ if (++bad_perfect >= RETRY_PERFECT)
+ {
+ if (blen < smax)
+ {
+ blen *= 2;
+ tabb.resize(blen);
+ tabq.resize(blen+1);
+ --si; /* we know this salt got distinct (A,B) */
+ }
+ else
+ {
+ return 0;
+ }
+ bad_perfect = 0;
+ }
+ continue;
+ }
+
+ break;
+ }
+
+ return 1;
}
/*
@@ -1400,77 +1524,96 @@
------------------------------------------------------------------------------
*/
-/* get the list of keys */
-static void getkeys(key **keys, ub4 *nkeys, const string_map& strings)
-{
- key *buf = new key[strings.size()];
- size_t i;
- string_map::const_iterator s;
- for (i = 0, s = strings.begin(); s != strings.end(); ++s, ++i) {
- key *mykey = buf+i;
- mykey->name_k = (ub1 *)s->first;
- mykey->len_k = (ub4)strlen(s->first);
- }
- *keys = buf;
- *nkeys = strings.size();
+
+static void
+make_perfect(dyld3::OverflowSafeArray<key>& keys, perfect_hash& result)
+{
+ dyld3::OverflowSafeArray<bstuff> tab; /* table indexed by b */
+ ub4 smax; /* scramble[] values in 0..smax-1, a power of 2 */
+ ub4 alen; /* a in 0..alen-1, a power of 2 */
+ ub8 salt; /* a parameter to the hash function */
+ ub4 scramble[SCRAMBLE_LEN]; /* used in final hash function */
+ int ok;
+ uint32_t i;
+
+ /* find the hash */
+ smax = ((ub4)1<<log2u((ub4)keys.count()));
+ ok = findhash(tab, &alen, &salt,
+ scramble, smax, keys);
+ if (!ok) {
+ smax = 2 * ((ub4)1<<log2u((ub4)keys.count()));
+ ok = findhash(tab, &alen, &salt,
+ scramble, smax, keys);
+ }
+ if (!ok) {
+ bzero(&result, sizeof(result));
+ } else {
+ /* build the tables */
+ result.capacity = smax;
+ result.occupied = (ub4)keys.count();
+ result.shift = UB8BITS - log2u(alen);
+ result.mask = (ub4)tab.count() - 1;
+ result.salt = salt;
+
+ result.tab.resize(tab.count());
+ for (i = 0; i < tab.count(); i++) {
+ result.tab[i] = tab[i].val_b;
+ }
+ for (i = 0; i < 256; i++) {
+ result.scramble[i] = scramble[i];
+ }
+ }
}
-
-static perfect_hash
-make_perfect(const string_map& strings)
-{
- ub4 nkeys; /* number of keys */
- key *keys; /* head of list of keys */
- bstuff *tab; /* table indexed by b */
- ub4 smax; /* scramble[] values in 0..smax-1, a power of 2 */
- ub4 alen; /* a in 0..alen-1, a power of 2 */
- ub4 blen; /* b in 0..blen-1, a power of 2 */
- ub8 salt; /* a parameter to the hash function */
- ub4 scramble[SCRAMBLE_LEN]; /* used in final hash function */
- int ok;
- int i;
- perfect_hash result;
-
- /* read in the list of keywords */
- getkeys(&keys, &nkeys, strings);
-
- /* find the hash */
- smax = ((ub4)1<<log2u(nkeys));
- ok = findhash(&tab, &alen, &blen, &salt,
- scramble, smax, keys, nkeys);
- if (!ok) {
- smax = 2 * ((ub4)1<<log2u(nkeys));
- ok = findhash(&tab, &alen, &blen, &salt,
- scramble, smax, keys, nkeys);
- }
- if (!ok) {
- bzero(&result, sizeof(result));
- } else {
- /* build the tables */
- result.capacity = smax;
- result.occupied = nkeys;
- result.shift = UB8BITS - log2u(alen);
- result.mask = blen - 1;
- result.salt = salt;
-
- result.tab = new uint8_t[blen];
- for (i = 0; i < blen; i++) {
- result.tab[i] = tab[i].val_b;
- }
- for (i = 0; i < 256; i++) {
- result.scramble[i] = scramble[i];
- }
- }
-
- delete[] keys;
- delete[] tab;
-
- return result;
+// SELOPT_WRITE || CLOSURE_SELOPT_WRITE
+#endif
+
+#ifdef SELOPT_WRITE
+
+static void
+make_perfect(const string_map& strings, perfect_hash& 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) {
+ key mykey;
+ mykey.name_k = (ub1 *)s->first;
+ mykey.len_k = (ub4)strlen(s->first);
+ keys.push_back(mykey);
+ }
+
+ make_perfect(keys, phash);
}
// SELOPT_WRITE
#endif
+#ifdef CLOSURE_SELOPT_WRITE
+
+static void
+make_perfect(const dyld3::OverflowSafeArray<const char*>& strings, perfect_hash& phash)
+{
+ dyld3::OverflowSafeArray<key> keys;
+
+ /* read in the list of keywords */
+ keys.reserve(strings.count());
+ for (const char* s : strings) {
+ key mykey;
+ mykey.name_k = (ub1 *)s;
+ mykey.len_k = (ub4)strlen(s);
+ keys.push_back(mykey);
+ }
+
+ make_perfect(keys, phash);
+}
+
+// CLOSURE_SELOPT_WRITE
+#endif
+
// namespace objc_selopt
};