Lines Matching refs:table
14 static inline ds_htable_bucket_t *ds_htable_reallocate_buckets(ds_htable_t *table, uint32_t capacit… in ds_htable_reallocate_buckets() argument
16 return erealloc(table->buckets, capacity * sizeof(ds_htable_bucket_t)); in ds_htable_reallocate_buckets()
29 static inline void ds_htable_reset_lookup(ds_htable_t *table) in ds_htable_reset_lookup() argument
31 memset(table->lookup, DS_HTABLE_INVALID_INDEX, table->capacity * sizeof(uint32_t)); in ds_htable_reset_lookup()
34 static inline void ds_htable_realloc(ds_htable_t *table, uint32_t capacity) in ds_htable_realloc() argument
36 table->buckets = ds_htable_reallocate_buckets(table, capacity); in ds_htable_realloc()
37 table->lookup = ds_htable_reallocate_lookup(table->lookup, capacity); in ds_htable_realloc()
38 table->capacity = capacity; in ds_htable_realloc()
41 static void ds_htable_rehash(ds_htable_t *table) in ds_htable_rehash() argument
43 const uint32_t mask = table->capacity - 1; in ds_htable_rehash()
45 ds_htable_reset_lookup(table); in ds_htable_rehash()
48 table->min_deleted = table->capacity; in ds_htable_rehash()
51 if (table->size == 0) { in ds_htable_rehash()
52 table->next = 0; in ds_htable_rehash()
57 ds_htable_bucket_t *bucket = table->buckets; in ds_htable_rehash()
59 if (DS_HTABLE_IS_PACKED(table)) { // No deleted buckets in ds_htable_rehash()
61 DS_HTABLE_BUCKET_REHASH(table, bucket, mask, index); in ds_htable_rehash()
63 } while (++index < table->next); in ds_htable_rehash()
72 while (++index < table->next) { in ds_htable_rehash()
76 DS_HTABLE_BUCKET_REHASH(table, q, mask, j); in ds_htable_rehash()
82 table->next = j; in ds_htable_rehash()
85 DS_HTABLE_BUCKET_REHASH(table, bucket, mask, index); in ds_htable_rehash()
88 } while (++index < table->next); in ds_htable_rehash()
93 static void ds_htable_pack(ds_htable_t *table) in ds_htable_pack() argument
95 if ( ! DS_HTABLE_IS_PACKED(table)) { in ds_htable_pack()
96 ds_htable_bucket_t *end = table->buckets + table->next; in ds_htable_pack()
97 ds_htable_bucket_t *src = table->buckets + table->min_deleted; in ds_htable_pack()
107 table->next = table->size; in ds_htable_pack()
108 table->min_deleted = table->capacity; in ds_htable_pack()
112 static inline void ds_htable_auto_truncate(ds_htable_t *table) in ds_htable_auto_truncate() argument
114 const uint32_t capacity = table->capacity; in ds_htable_auto_truncate()
116 if (table->size <= (capacity / 4) && (capacity / 2) >= DS_HTABLE_MIN_CAPACITY) { in ds_htable_auto_truncate()
117 ds_htable_pack(table); in ds_htable_auto_truncate()
118 ds_htable_realloc(table, capacity / 2); in ds_htable_auto_truncate()
119 ds_htable_rehash(table); in ds_htable_auto_truncate()
125 ds_htable_t *table = ecalloc(1, sizeof(ds_htable_t)); in ds_htable_with_capacity() local
127 table->buckets = ds_htable_allocate_buckets(capacity); in ds_htable_with_capacity()
128 table->lookup = ds_htable_allocate_lookup(capacity); in ds_htable_with_capacity()
129 table->capacity = capacity; in ds_htable_with_capacity()
130 table->min_deleted = capacity; in ds_htable_with_capacity()
131 table->size = 0; in ds_htable_with_capacity()
132 table->next = 0; in ds_htable_with_capacity()
134 ds_htable_reset_lookup(table); in ds_htable_with_capacity()
135 return table; in ds_htable_with_capacity()
340 ds_htable_t *table, in ds_htable_lookup_bucket_by_hash() argument
351 index = DS_HTABLE_BUCKET_LOOKUP(table, hash); in ds_htable_lookup_bucket_by_hash()
355 bucket = &table->buckets[index]; in ds_htable_lookup_bucket_by_hash()
367 ds_htable_bucket_t *ds_htable_lookup_by_key(ds_htable_t *table, zval *key) in ds_htable_lookup_by_key() argument
369 return ds_htable_lookup_bucket_by_hash(table, key, get_hash(key)); in ds_htable_lookup_by_key()
372 ds_htable_bucket_t *ds_htable_lookup_by_position(ds_htable_t *table, uint32_t position) in ds_htable_lookup_by_position() argument
374 if (table->size == 0 || position >= table->size) { in ds_htable_lookup_by_position()
378 } else if (DS_HTABLE_IS_PACKED(table) || position < table->min_deleted) { in ds_htable_lookup_by_position()
379 return &table->buckets[position]; in ds_htable_lookup_by_position()
388 if (table->min_deleted <= position) { in ds_htable_lookup_by_position()
389 index = table->min_deleted; in ds_htable_lookup_by_position()
394 bucket = &table->buckets[index]; in ds_htable_lookup_by_position()
395 stop = &table->buckets[table->next]; in ds_htable_lookup_by_position()
415 ds_htable_bucket_t *ds_htable_lookup_by_value(ds_htable_t *table, zval *value) in ds_htable_lookup_by_value() argument
419 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_lookup_by_value()
429 bool ds_htable_isset(ds_htable_t *table, zval *key, bool check_empty) in ds_htable_isset() argument
431 ds_htable_bucket_t *bucket = ds_htable_lookup_by_key(table, key); in ds_htable_isset()
436 zval *ds_htable_get(ds_htable_t *table, zval *key) in ds_htable_get() argument
438 ds_htable_bucket_t *bucket = ds_htable_lookup_by_key(table, key); in ds_htable_get()
443 bool ds_htable_has_key(ds_htable_t *table, zval *key) in ds_htable_has_key() argument
445 return ds_htable_lookup_by_key(table, key) != NULL; in ds_htable_has_key()
448 bool ds_htable_has_keys(ds_htable_t *table, VA_PARAMS) in ds_htable_has_keys() argument
451 if ( ! ds_htable_has_key(table, argv++)) { in ds_htable_has_keys()
459 bool ds_htable_has_value(ds_htable_t *table, zval *value) in ds_htable_has_value() argument
461 return ds_htable_lookup_by_value(table, value) != NULL; in ds_htable_has_value()
464 bool ds_htable_has_values(ds_htable_t *table, VA_PARAMS) in ds_htable_has_values() argument
467 if ( ! ds_htable_lookup_by_value(table, argv++)) { in ds_htable_has_values()
475 static void ds_htable_clear_buffer(ds_htable_t *table) in ds_htable_clear_buffer() argument
479 if (table->size == 0) { in ds_htable_clear_buffer()
483 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_clear_buffer()
488 table->size = 0; in ds_htable_clear_buffer()
489 table->next = 0; in ds_htable_clear_buffer()
490 table->min_deleted = table->capacity; in ds_htable_clear_buffer()
493 void ds_htable_clear(ds_htable_t *table) in ds_htable_clear() argument
495 ds_htable_clear_buffer(table); in ds_htable_clear()
497 if (table->capacity > DS_HTABLE_MIN_CAPACITY) { in ds_htable_clear()
498 ds_htable_realloc(table, DS_HTABLE_MIN_CAPACITY); in ds_htable_clear()
501 ds_htable_reset_lookup(table); in ds_htable_clear()
503 table->min_deleted = table->capacity; in ds_htable_clear()
506 void ds_htable_free(ds_htable_t *table) in ds_htable_free() argument
508 ds_htable_clear_buffer(table); in ds_htable_free()
510 efree(table->buckets); in ds_htable_free()
511 efree(table->lookup); in ds_htable_free()
512 efree(table); in ds_htable_free()
515 static inline void ds_htable_sort_ex(ds_htable_t *table, compare_func_t compare_func) in ds_htable_sort_ex() argument
517 ds_htable_pack(table); in ds_htable_sort_ex()
518 qsort(table->buckets, table->size, sizeof(ds_htable_bucket_t), compare_func); in ds_htable_sort_ex()
519 ds_htable_rehash(table); in ds_htable_sort_ex()
522 void ds_htable_sort(ds_htable_t *table, compare_func_t compare_func) in ds_htable_sort() argument
524 ds_htable_sort_ex(table, compare_func); in ds_htable_sort()
592 void ds_htable_sort_by_key(ds_htable_t *table) in ds_htable_sort_by_key() argument
594 ds_htable_sort(table, compare_by_key); in ds_htable_sort_by_key()
597 void ds_htable_sort_by_value(ds_htable_t *table) in ds_htable_sort_by_value() argument
599 ds_htable_sort(table, compare_by_value); in ds_htable_sort_by_value()
602 void ds_htable_sort_callback_by_key(ds_htable_t *table) in ds_htable_sort_callback_by_key() argument
604 ds_htable_sort(table, user_compare_by_key); in ds_htable_sort_callback_by_key()
607 void ds_htable_sort_callback_by_value(ds_htable_t *table) in ds_htable_sort_callback_by_value() argument
609 ds_htable_sort(table, user_compare_by_value); in ds_htable_sort_callback_by_value()
612 static inline void ds_htable_increase_capacity(ds_htable_t *table) in ds_htable_increase_capacity() argument
614 if (table->next > table->size + (table->size >> 5)) { in ds_htable_increase_capacity()
615 ds_htable_rehash(table); in ds_htable_increase_capacity()
619 ds_htable_realloc(table, table->capacity << 1); in ds_htable_increase_capacity()
620 ds_htable_rehash(table); in ds_htable_increase_capacity()
628 void ds_htable_ensure_capacity(ds_htable_t *table, uint32_t capacity) in ds_htable_ensure_capacity() argument
632 if (capacity > table->capacity) { in ds_htable_ensure_capacity()
633 ds_htable_realloc(table, capacity); in ds_htable_ensure_capacity()
634 ds_htable_rehash(table); in ds_htable_ensure_capacity()
641 static void ds_htable_put_distinct_bucket(ds_htable_t *table, ds_htable_bucket_t *bucket) in ds_htable_put_distinct_bucket() argument
643 ds_htable_bucket_t *next = &table->buckets[table->next]; in ds_htable_put_distinct_bucket()
646 DS_HTABLE_BUCKET_REHASH(table, next, table->capacity - 1, table->next); in ds_htable_put_distinct_bucket()
648 table->next++; in ds_htable_put_distinct_bucket()
649 table->size++; in ds_htable_put_distinct_bucket()
651 if (table->next == table->capacity) { in ds_htable_put_distinct_bucket()
652 ds_htable_increase_capacity(table); in ds_htable_put_distinct_bucket()
657 ds_htable_t *table, in ds_htable_init_next_bucket() argument
662 ds_htable_bucket_t *bucket = &table->buckets[table->next]; in ds_htable_init_next_bucket()
665 DS_HTABLE_BUCKET_REHASH(table, bucket, table->capacity - 1, table->next); in ds_htable_init_next_bucket()
675 table->next++; in ds_htable_init_next_bucket()
676 table->size++; in ds_htable_init_next_bucket()
680 bool ds_htable_lookup_or_next(ds_htable_t *table, zval *key, ds_htable_bucket_t **bucket) in ds_htable_lookup_or_next() argument
685 if ((*bucket = ds_htable_lookup_bucket_by_hash(table, key, hash))) { in ds_htable_lookup_or_next()
689 if (table->next == table->capacity) { in ds_htable_lookup_or_next()
690 ds_htable_increase_capacity(table); in ds_htable_lookup_or_next()
694 *bucket = ds_htable_init_next_bucket(table, key, NULL, hash); in ds_htable_lookup_or_next()
698 void ds_htable_put(ds_htable_t *table, zval *key, zval *value) in ds_htable_put() argument
703 bool found = ds_htable_lookup_or_next(table, key, &bucket); in ds_htable_put()
714 zval *ds_htable_values(ds_htable_t *table) in ds_htable_values() argument
716 zval *buffer = ds_allocate_zval_buffer(table->size); in ds_htable_values()
720 DS_HTABLE_FOREACH_VALUE(table, value) { in ds_htable_values()
728 ds_htable_bucket_t *ds_htable_last(ds_htable_t *table) in ds_htable_last() argument
730 if (table->size == 0) { in ds_htable_last()
734 ds_htable_bucket_t *bucket = &table->buckets[table->next - 1]; in ds_htable_last()
743 ds_htable_bucket_t *ds_htable_first(ds_htable_t *table) in ds_htable_first() argument
745 if (table->size == 0) { in ds_htable_first()
749 ds_htable_bucket_t *bucket = table->buckets; in ds_htable_first()
758 zend_string *ds_htable_join_keys(ds_htable_t *table, const char* glue, const size_t len) in ds_htable_join_keys() argument
762 if (table->size == 0) { in ds_htable_join_keys()
766 if (table->size == 1) { in ds_htable_join_keys()
767 return zval_get_string(&ds_htable_last(table)->key); in ds_htable_join_keys()
771 ds_htable_bucket_t *pos = table->buckets; in ds_htable_join_keys()
772 ds_htable_bucket_t *end = ds_htable_last(table); in ds_htable_join_keys()
786 DS_HTABLE_FOREACH_KEY(table, key) { in ds_htable_join_keys()
796 int ds_htable_remove(ds_htable_t *table, zval *key, zval *return_value) in ds_htable_remove() argument
799 uint32_t index = DS_HTABLE_BUCKET_LOOKUP(table, hash); in ds_htable_remove()
805 bucket = &table->buckets[index]; in ds_htable_remove()
819 DS_HTABLE_BUCKET_LOOKUP(table, hash) = DS_HTABLE_BUCKET_NEXT(bucket); in ds_htable_remove()
828 if (index == table->next - 1 && table->size > 1) { in ds_htable_remove()
830 table->next--; in ds_htable_remove()
837 if (index < table->min_deleted) { in ds_htable_remove()
838 table->min_deleted = index; in ds_htable_remove()
841 table->size--; in ds_htable_remove()
844 ds_htable_auto_truncate(table); in ds_htable_remove()
856 ds_htable_t *ds_htable_slice(ds_htable_t *table, zend_long index, zend_long length) in ds_htable_slice() argument
858 ds_normalize_slice_args(&index, &length, table->size); in ds_htable_slice()
871 if (DS_HTABLE_IS_PACKED(table) || in ds_htable_slice()
872 ((uint32_t) (index + length)) <= table->min_deleted) { in ds_htable_slice()
874 ds_htable_bucket_t *src = &table->buckets[index]; in ds_htable_slice()
885 } else if ((uint32_t) index < table->min_deleted) { in ds_htable_slice()
886 ds_htable_bucket_t *src = &table->buckets[index]; in ds_htable_slice()
906 ds_htable_bucket_t *src = table->buckets; in ds_htable_slice()
932 void ds_htable_apply(ds_htable_t *table, FCI_PARAMS) in ds_htable_apply() argument
937 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_apply()
952 ds_htable_t *ds_htable_map(ds_htable_t *table, FCI_PARAMS) in ds_htable_map() argument
957 ds_htable_t *mapped = ds_htable_with_capacity(table->capacity); in ds_htable_map()
959 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_map()
980 ds_htable_t *ds_htable_filter(ds_htable_t *table) in ds_htable_filter() argument
983 ds_htable_t *filtered = ds_htable_with_capacity(table->capacity); in ds_htable_filter()
985 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_filter()
999 ds_htable_t *ds_htable_filter_callback(ds_htable_t *table, FCI_PARAMS) in ds_htable_filter_callback() argument
1004 ds_htable_t *filtered = ds_htable_with_capacity(table->capacity); in ds_htable_filter_callback()
1006 DS_HTABLE_FOREACH_BUCKET(table, src) { in ds_htable_filter_callback()
1030 void ds_htable_reduce(ds_htable_t *table, FCI_PARAMS, zval *initial, zval *return_value) in ds_htable_reduce() argument
1042 DS_HTABLE_FOREACH_KEY_VALUE(table, key, value) { in ds_htable_reduce()
1062 ds_htable_t *ds_htable_xor(ds_htable_t *table, ds_htable_t *other) in ds_htable_xor() argument
1067 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_xor()
1075 if ( ! ds_htable_has_key(table, &bucket->key)) { in ds_htable_xor()
1084 ds_htable_t *ds_htable_diff(ds_htable_t *table, ds_htable_t *other) in ds_htable_diff() argument
1089 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_diff()
1099 ds_htable_t *ds_htable_intersect(ds_htable_t *table, ds_htable_t *other) in ds_htable_intersect() argument
1105 DS_HTABLE_FOREACH_BUCKET(table, bucket) { in ds_htable_intersect()
1115 ds_htable_t *ds_htable_merge(ds_htable_t *table, ds_htable_t *other) in ds_htable_merge() argument
1118 ds_htable_t *merged = ds_htable_clone(table); in ds_htable_merge()
1128 void ds_htable_reverse(ds_htable_t *table) in ds_htable_reverse() argument
1130 ds_htable_pack(table); in ds_htable_reverse()
1132 ds_htable_bucket_t *a = table->buckets; in ds_htable_reverse()
1133 ds_htable_bucket_t *b = table->buckets + table->size - 1; in ds_htable_reverse()
1141 ds_htable_rehash(table); in ds_htable_reverse()
1144 ds_htable_t *ds_htable_reversed(ds_htable_t *table) in ds_htable_reversed() argument
1146 ds_htable_t *reversed = ds_htable_with_capacity(table->capacity); in ds_htable_reversed()
1153 DS_HTABLE_FOREACH_BUCKET_REVERSED(table, src) { in ds_htable_reversed()
1163 reversed->size = table->size; in ds_htable_reversed()
1167 void ds_htable_to_array(ds_htable_t *table, zval *return_value) in ds_htable_to_array() argument
1173 array_init_size(return_value, table->size); in ds_htable_to_array()
1176 DS_HTABLE_FOREACH_KEY_VALUE(table, key, val) { in ds_htable_to_array()
1182 int ds_htable_serialize(ds_htable_t *table, unsigned char **buffer, size_t *length, zend_serialize_… in ds_htable_serialize() argument
1187 if (table->size == 0) { in ds_htable_serialize()
1195 DS_HTABLE_FOREACH_KEY_VALUE(table, key, value) { in ds_htable_serialize()
1211 int ds_htable_unserialize(ds_htable_t *table, const unsigned char *buffer, size_t length, zend_unse… in ds_htable_unserialize() argument
1237 ds_htable_put(table, key, value); in ds_htable_unserialize()
