Overview
Comment: | Generalize runtime/hashtable.m |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA3-256: |
8d930f2067244ad088ee6958a5f79246 |
User & Date: | js on 2014-03-22 17:56:09 |
Other Links: | manifest | tags |
Context
2014-03-23
| ||
00:15 | Remove -Wno-deprecated-objc-pointer-introspection check-in: f3154a74aa user: js tags: trunk | |
2014-03-22
| ||
17:56 | Generalize runtime/hashtable.m check-in: 8d930f2067 user: js tags: trunk | |
2014-03-19
| ||
18:05 | macros.h: Never define static_assert to assert check-in: 61369b9d26 user: js tags: trunk | |
Changes
Modified src/runtime/category.m from [b9b6c831df] to [cc568b9dbb].
︙ | ︙ | |||
45 46 47 48 49 50 51 | static void register_category(struct objc_abi_category *cat) { struct objc_abi_category **cats; Class cls = objc_classname_to_class(cat->class_name, false); if (categories == NULL) | | > | 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | static void register_category(struct objc_abi_category *cat) { struct objc_abi_category **cats; Class cls = objc_classname_to_class(cat->class_name, false); if (categories == NULL) categories = objc_hashtable_new( objc_hash_string, objc_equal_string, 2); cats = (struct objc_abi_category**)objc_hashtable_get(categories, cat->class_name); if (cats != NULL) { struct objc_abi_category **ncats; size_t i; |
︙ | ︙ | |||
119 120 121 122 123 124 125 | objc_unregister_all_categories(void) { uint32_t i; if (categories == NULL) return; | | | 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | objc_unregister_all_categories(void) { uint32_t i; if (categories == NULL) return; for (i = 0; i < categories->size; i++) if (categories->data[i] != NULL) free((void*)categories->data[i]->obj); objc_hashtable_free(categories); categories = NULL; } |
Modified src/runtime/class.m from [e32de8ba86] to [cb99b9ea3b].
︙ | ︙ | |||
37 38 39 40 41 42 43 | static unsigned lookups_till_fast_path = 128; static struct sparsearray *sparsearray = NULL; static void register_class(struct objc_abi_class *cls) { if (classes == NULL) | | > | 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | static unsigned lookups_till_fast_path = 128; static struct sparsearray *sparsearray = NULL; static void register_class(struct objc_abi_class *cls) { if (classes == NULL) classes = objc_hashtable_new( objc_hash_string, objc_equal_string, 2); objc_hashtable_set(classes, cls->name, cls); if (empty_dtable == NULL) empty_dtable = objc_sparsearray_new(); cls->dtable = empty_dtable; |
︙ | ︙ | |||
520 521 522 523 524 525 526 | if (buf == NULL) return classes_cnt; if (classes_cnt < count) count = classes_cnt; | | | 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 | if (buf == NULL) return classes_cnt; if (classes_cnt < count) count = classes_cnt; for (i = j = 0; i < classes->size; i++) { Class cls; if (j >= count) { objc_global_mutex_unlock(); return j; } |
︙ | ︙ | |||
854 855 856 857 858 859 860 | objc_unregister_all_classes(void) { uint_fast32_t i; if (classes == NULL) return; | | | 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 | objc_unregister_all_classes(void) { uint_fast32_t i; if (classes == NULL) return; for (i = 0; i < classes->size; i++) { if (classes->data[i] != NULL) { Class cls = (Class)classes->data[i]->obj; if (cls == Nil || (uintptr_t)cls & 1) continue; objc_unregister_class(cls); |
︙ | ︙ |
Modified src/runtime/hashtable.m from [7dd989f99f] to [2de01382c7].
︙ | ︙ | |||
21 22 23 24 25 26 27 | #include <stdint.h> #include <string.h> #import "runtime.h" #import "runtime-private.h" uint32_t | | > > > > > > > | > | < | > > > | | | | < < < | | | | | | | | > > > | < | < < < | | | | | > | | | | | | > | | | | | | | | | | | | | > | | | | | | | | | | | | | 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 | #include <stdint.h> #include <string.h> #import "runtime.h" #import "runtime-private.h" uint32_t objc_hash_string(const void *str_) { const char *str = str_; uint32_t hash = 0; while (*str != 0) { hash += *str; hash += (hash << 10); hash ^= (hash >> 6); str++; } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return hash; } bool objc_equal_string(const void *obj1, const void *obj2) { return !strcmp(obj1, obj2); } struct objc_hashtable* objc_hashtable_new(uint32_t (*hash)(const void*), bool (*equal)(const void*, const void*), uint32_t size) { struct objc_hashtable *table; if ((table = malloc(sizeof(struct objc_hashtable))) == NULL) OBJC_ERROR("Not enough memory to allocate hash table!"); table->hash = hash; table->equal = equal; table->count = 0; table->size = size; table->data = calloc(size, sizeof(struct objc_hashtable_bucket*)); if (table->data == NULL) OBJC_ERROR("Not enough memory to allocate hash table!"); return table; } static void insert(struct objc_hashtable *table, const void *key, const void *obj) { uint32_t i, hash, last; struct objc_hashtable_bucket *bucket; hash = table->hash(key); if (table->count + 1 > UINT32_MAX / 4) OBJC_ERROR("Integer overflow!"); if ((table->count + 1) * 4 / table->size >= 3) { struct objc_hashtable_bucket **newData; uint32_t newSize; if (table->size > UINT32_MAX / 2) OBJC_ERROR("Integer overflow!"); newSize = table->size * 2; if ((newData = calloc(newSize, sizeof(struct objc_hashtable_bucket*))) == NULL) OBJC_ERROR("Not enough memory to insert into hash " "table!"); for (i = 0; i < table->size; i++) { if (table->data[i] != NULL) { uint32_t j; last = newSize; for (j = table->data[i]->hash & (newSize - 1); j < last && newData[j] != NULL; j++); if (j >= last) { last = table->data[i]->hash & (newSize - 1); for (j = 0; j < last && newData[j] != NULL; j++); } if (j >= last) OBJC_ERROR("No free bucket!"); newData[j] = table->data[i]; } } free(table->data); table->data = newData; table->size = newSize; } last = table->size; for (i = hash & (table->size - 1); i < last && table->data[i] != NULL; i++); if (i >= last) { last = hash & (table->size - 1); for (i = 0; i < last && table->data[i] != NULL; i++); } if (i >= last) OBJC_ERROR("No free bucket!"); if ((bucket = malloc(sizeof(struct objc_hashtable_bucket))) == NULL) OBJC_ERROR("Not enough memory to allocate hash table bucket!"); bucket->key = key; bucket->hash = hash; bucket->obj = obj; table->data[i] = bucket; table->count++; } static inline int64_t index_for_key(struct objc_hashtable *table, const void *key) { uint32_t i, hash; hash = table->hash(key) & (table->size - 1); for (i = hash; i < table->size && table->data[i] != NULL; i++) if (table->equal(table->data[i]->key, key)) return i; if (i < table->size) return -1; for (i = 0; i < hash && table->data[i] != NULL; i++) if (table->equal(table->data[i]->key, key)) return i; return -1; } void objc_hashtable_set(struct objc_hashtable *table, const void *key, const void *obj) { int64_t idx = index_for_key(table, key); if (idx < 0) { insert(table, key, obj); return; } table->data[idx]->obj = obj; } void* objc_hashtable_get(struct objc_hashtable *table, const void *key) { int64_t idx = index_for_key(table, key); if (idx < 0) return NULL; return (void*)table->data[idx]->obj; } void objc_hashtable_free(struct objc_hashtable *table) { uint32_t i; for (i = 0; i < table->size; i++) if (table->data[i] != NULL) free(table->data[i]); free(table->data); free(table); } |
Modified src/runtime/runtime-private.h from [0e0bd3f946] to [75ef745292].
︙ | ︙ | |||
87 88 89 90 91 92 93 | unsigned long version; /* 9 = non-fragile */ unsigned long size; const char *name; struct objc_abi_symtab *symtab; }; struct objc_hashtable_bucket { | < | | > | | 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | unsigned long version; /* 9 = non-fragile */ unsigned long size; const char *name; struct objc_abi_symtab *symtab; }; struct objc_hashtable_bucket { const void *key, *obj; uint32_t hash; }; struct objc_hashtable { uint32_t (*hash)(const void *key); bool (*equal)(const void *key1, const void *key2); uint32_t count, size; struct objc_hashtable_bucket **data; }; struct objc_sparsearray { struct objc_sparsearray_level2 *buckets[256]; }; |
︙ | ︙ | |||
125 126 127 128 129 130 131 | extern void objc_unregister_all_categories(void); extern void objc_initialize_class(Class); extern void objc_update_dtable(Class); extern void objc_register_all_classes(struct objc_abi_symtab*); extern Class objc_classname_to_class(const char*, bool); extern void objc_unregister_class(Class); extern void objc_unregister_all_classes(void); | | > | > | | | 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | extern void objc_unregister_all_categories(void); extern void objc_initialize_class(Class); extern void objc_update_dtable(Class); extern void objc_register_all_classes(struct objc_abi_symtab*); extern Class objc_classname_to_class(const char*, bool); extern void objc_unregister_class(Class); extern void objc_unregister_all_classes(void); extern uint32_t objc_hash_string(const void*); extern bool objc_equal_string(const void*, const void*); extern struct objc_hashtable* objc_hashtable_new(uint32_t (*)(const void*), bool (*)(const void*, const void*), uint32_t); extern void objc_hashtable_set(struct objc_hashtable*, const void*, const void*); extern void* objc_hashtable_get(struct objc_hashtable*, const void*); extern void objc_hashtable_free(struct objc_hashtable *h); extern void objc_register_selector(struct objc_abi_selector*); extern void objc_register_all_selectors(struct objc_abi_symtab*); extern void objc_unregister_all_selectors(void); extern struct objc_sparsearray* objc_sparsearray_new(void); extern void objc_sparsearray_copy(struct objc_sparsearray*, struct objc_sparsearray*); |
︙ | ︙ |
Modified src/runtime/selector.m from [915bbfe8d7] to [c556b01892].
︙ | ︙ | |||
43 44 45 46 47 48 49 | struct objc_selector *rsel; const char *name; if (selectors_cnt > SEL_MAX) OBJC_ERROR("Out of selector slots!"); if (selectors == NULL) | | > | 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | struct objc_selector *rsel; const char *name; if (selectors_cnt > SEL_MAX) OBJC_ERROR("Out of selector slots!"); if (selectors == NULL) selectors = objc_hashtable_new( objc_hash_string, objc_equal_string, 2); else if ((rsel = objc_hashtable_get(selectors, sel->name)) != NULL) { ((struct objc_selector*)sel)->uid = rsel->uid; return; } if (selector_names == NULL) selector_names = objc_sparsearray_new(); |
︙ | ︙ |