From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Subject: Re: [tarantool-patches] Re: [PATCH v1 1/1] lib/bitset: rename bitset structs References: <20180703103753.o3isk2wymm73ab6f@esperanza> From: Kirill Shcherbatov Message-ID: <2a09bc5d-8b80-d387-7ff2-2ccb4b14d2d8@tarantool.org> Date: Tue, 3 Jul 2018 15:24:29 +0300 MIME-Version: 1.0 In-Reply-To: <20180703103753.o3isk2wymm73ab6f@esperanza> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit To: tarantool-patches@freelists.org Cc: Vladimir Davydov List-ID: > If you're renaming struct bitset to struct tt_bitset, you should also > rename all its methods (bitset_create => tt_bitset_create and so forth). Ok, I've renamed all bitset structures and methods ====================================== --- src/box/memtx_bitset.c | 108 ++++++++------- src/box/memtx_bitset.h | 2 +- src/lib/bitset/bitset.c | 84 ++++++------ src/lib/bitset/bitset.h | 29 ++-- src/lib/bitset/expr.c | 28 ++-- src/lib/bitset/expr.h | 19 +-- src/lib/bitset/index.c | 122 ++++++++--------- src/lib/bitset/index.h | 54 ++++---- src/lib/bitset/iterator.c | 115 ++++++++-------- src/lib/bitset/iterator.h | 25 ++-- src/lib/bitset/page.c | 27 ++-- src/lib/bitset/page.h | 71 +++++----- test/unit/bitset_basic.c | 66 ++++----- test/unit/bitset_index.c | 158 +++++++++++----------- test/unit/bitset_iterator.c | 316 ++++++++++++++++++++++---------------------- 15 files changed, 630 insertions(+), 594 deletions(-) diff --git a/src/box/memtx_bitset.c b/src/box/memtx_bitset.c index 9216ed8..33c4b47 100644 --- a/src/box/memtx_bitset.c +++ b/src/box/memtx_bitset.c @@ -43,7 +43,7 @@ #ifndef OLD_GOOD_BITSET #include "small/matras.h" -struct bitset_hash_entry { +struct tt_bitset_hash_entry { struct tuple *tuple; uint32_t id; }; @@ -59,7 +59,7 @@ struct bitset_hash_entry { #define mh_cmp(a, b, arg) ((a)->tuple != (b)->tuple) #define mh_cmp_key(a, b, arg) ((a) != (b)->tuple) -#define mh_node_t struct bitset_hash_entry +#define mh_node_t struct tt_bitset_hash_entry #define mh_key_t struct tuple * #define mh_name _bitset_index #define MH_SOURCE 1 @@ -85,7 +85,7 @@ memtx_bitset_index_register_tuple(struct memtx_bitset_index *index, } *place = tuple; - struct bitset_hash_entry entry; + struct tt_bitset_hash_entry entry; entry.id = id; entry.tuple = tuple; uint32_t pos = mh_bitset_index_put(index->tuple_to_id, &entry, 0, 0); @@ -104,7 +104,8 @@ memtx_bitset_index_unregister_tuple(struct memtx_bitset_index *index, { uint32_t k = mh_bitset_index_find(index->tuple_to_id, tuple, 0); - struct bitset_hash_entry *e = mh_bitset_index_node(index->tuple_to_id, k); + struct tt_bitset_hash_entry *e = + mh_bitset_index_node(index->tuple_to_id, k); void *mem = matras_get(index->id_to_tuple, e->id); *(uint32_t *)mem = index->spare_id; index->spare_id = e->id; @@ -116,7 +117,8 @@ memtx_bitset_index_tuple_to_value(struct memtx_bitset_index *index, struct tuple *tuple) { uint32_t k = mh_bitset_index_find(index->tuple_to_id, tuple, 0); - struct bitset_hash_entry *e = mh_bitset_index_node(index->tuple_to_id, k); + struct tt_bitset_hash_entry *e = + mh_bitset_index_node(index->tuple_to_id, k); return e->id; } @@ -152,9 +154,9 @@ value_to_tuple(size_t value) } #endif /* #ifndef OLD_GOOD_BITSET */ -struct bitset_index_iterator { +struct tt_bitset_index_iterator { struct iterator base; /* Must be the first member. */ - struct bitset_iterator bitset_it; + struct tt_bitset_iterator bitset_it; #ifndef OLD_GOOD_BITSET struct memtx_bitset_index *bitset_index; #endif /* #ifndef OLD_GOOD_BITSET */ @@ -162,29 +164,31 @@ struct bitset_index_iterator { struct mempool *pool; }; -static struct bitset_index_iterator * -bitset_index_iterator(struct iterator *it) +static struct tt_bitset_index_iterator * +tt_bitset_index_iterator(struct iterator *it) { - return (struct bitset_index_iterator *) it; + return (struct tt_bitset_index_iterator *) it; } static void -bitset_index_iterator_free(struct iterator *iterator) +tt_bitset_index_iterator_free(struct iterator *iterator) { - assert(iterator->free == bitset_index_iterator_free); - struct bitset_index_iterator *it = bitset_index_iterator(iterator); + assert(iterator->free == tt_bitset_index_iterator_free); + struct tt_bitset_index_iterator *it = + tt_bitset_index_iterator(iterator); - bitset_iterator_destroy(&it->bitset_it); + tt_bitset_iterator_destroy(&it->bitset_it); mempool_free(it->pool, it); } static int -bitset_index_iterator_next(struct iterator *iterator, struct tuple **ret) +tt_bitset_index_iterator_next(struct iterator *iterator, struct tuple **ret) { - assert(iterator->free == bitset_index_iterator_free); - struct bitset_index_iterator *it = bitset_index_iterator(iterator); + assert(iterator->free == tt_bitset_index_iterator_free); + struct tt_bitset_index_iterator *it = + tt_bitset_index_iterator(iterator); - size_t value = bitset_iterator_next(&it->bitset_it); + size_t value = tt_bitset_iterator_next(&it->bitset_it); if (value == SIZE_MAX) { *ret = NULL; return 0; @@ -202,7 +206,7 @@ static void memtx_bitset_index_destroy(struct index *base) { struct memtx_bitset_index *index = (struct memtx_bitset_index *)base; - bitset_index_destroy(&index->index); + tt_bitset_index_destroy(&index->index); #ifndef OLD_GOOD_BITSET mh_bitset_index_delete(index->tuple_to_id); matras_destroy(index->id_to_tuple); @@ -215,7 +219,7 @@ static ssize_t memtx_bitset_index_size(struct index *base) { struct memtx_bitset_index *index = (struct memtx_bitset_index *)base; - return bitset_index_size(&index->index); + return tt_bitset_index_size(&index->index); } static ssize_t @@ -223,7 +227,7 @@ memtx_bitset_index_bsize(struct index *base) { struct memtx_bitset_index *index = (struct memtx_bitset_index *)base; size_t result = 0; - result += bitset_index_bsize(&index->index); + result += tt_bitset_index_bsize(&index->index); #ifndef OLD_GOOD_BITSET result += matras_extent_count(index->id_to_tuple) * MEMTX_EXTENT_SIZE; result += mh_bitset_index_memsize(index->tuple_to_id); @@ -270,11 +274,12 @@ memtx_bitset_index_replace(struct index *base, struct tuple *old_tuple, #else /* #ifndef OLD_GOOD_BITSET */ size_t value = tuple_to_value(old_tuple); #endif /* #ifndef OLD_GOOD_BITSET */ - if (bitset_index_contains_value(&index->index, (size_t)value)) { + if (tt_bitset_index_contains_value(&index->index, + (size_t) value)) { *result = old_tuple; assert(old_tuple != new_tuple); - bitset_index_remove_value(&index->index, value); + tt_bitset_index_remove_value(&index->index, value); #ifndef OLD_GOOD_BITSET memtx_bitset_index_unregister_tuple(index, old_tuple); #endif /* #ifndef OLD_GOOD_BITSET */ @@ -293,7 +298,8 @@ memtx_bitset_index_replace(struct index *base, struct tuple *old_tuple, #else /* #ifndef OLD_GOOD_BITSET */ uint32_t value = tuple_to_value(new_tuple); #endif /* #ifndef OLD_GOOD_BITSET */ - if (bitset_index_insert(&index->index, key, key_len, value) < 0) { + if (tt_bitset_index_insert(&index->index, key, key_len, + value) < 0) { #ifndef OLD_GOOD_BITSET memtx_bitset_index_unregister_tuple(index, new_tuple); #endif /* #ifndef OLD_GOOD_BITSET */ @@ -314,7 +320,7 @@ memtx_bitset_index_create_iterator(struct index *base, enum iterator_type type, assert(part_count == 0 || key != NULL); (void) part_count; - struct bitset_index_iterator *it; + struct tt_bitset_index_iterator *it; it = mempool_alloc(&memtx->bitset_iterator_pool); if (!it) { diag_set(OutOfMemory, sizeof(*it), @@ -324,10 +330,10 @@ memtx_bitset_index_create_iterator(struct index *base, enum iterator_type type, iterator_create(&it->base, base); it->pool = &memtx->bitset_iterator_pool; - it->base.next = bitset_index_iterator_next; - it->base.free = bitset_index_iterator_free; + it->base.next = tt_bitset_index_iterator_next; + it->base.free = tt_bitset_index_iterator_free; - bitset_iterator_create(&it->bitset_it, realloc); + tt_bitset_iterator_create(&it->bitset_it, realloc); #ifndef OLD_GOOD_BITSET it->bitset_index = index; #endif @@ -339,29 +345,29 @@ memtx_bitset_index_create_iterator(struct index *base, enum iterator_type type, bitset_key = make_key(key, &bitset_key_size); } - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); int rc = 0; switch (type) { case ITER_ALL: - rc = bitset_index_expr_all(&expr); + rc = tt_bitset_index_expr_all(&expr); break; case ITER_EQ: - rc = bitset_index_expr_equals(&expr, bitset_key, - bitset_key_size); + rc = tt_bitset_index_expr_equals(&expr, bitset_key, + bitset_key_size); break; case ITER_BITS_ALL_SET: - rc = bitset_index_expr_all_set(&expr, bitset_key, - bitset_key_size); + rc = tt_bitset_index_expr_all_set(&expr, bitset_key, + bitset_key_size); break; case ITER_BITS_ALL_NOT_SET: - rc = bitset_index_expr_all_not_set(&expr, bitset_key, - bitset_key_size); + rc = tt_bitset_index_expr_all_not_set(&expr, bitset_key, + bitset_key_size); break; case ITER_BITS_ANY_SET: - rc = bitset_index_expr_any_set(&expr, bitset_key, - bitset_key_size); + rc = tt_bitset_index_expr_any_set(&expr, bitset_key, + bitset_key_size); break; default: diag_set(UnsupportedIndexFeature, base->def, @@ -375,17 +381,17 @@ memtx_bitset_index_create_iterator(struct index *base, enum iterator_type type, goto fail; } - if (bitset_index_init_iterator(&index->index, &it->bitset_it, - &expr) != 0) { + if (tt_bitset_index_init_iterator(&index->index, &it->bitset_it, + &expr) != 0) { diag_set(OutOfMemory, 0, "memtx_bitset_index", "iterator state"); goto fail; } - bitset_expr_destroy(&expr); + tt_bitset_expr_destroy(&expr); return (struct iterator *)it; fail: - bitset_expr_destroy(&expr); + tt_bitset_expr_destroy(&expr); mempool_free(&memtx->bitset_iterator_pool, it); return NULL; } @@ -397,7 +403,7 @@ memtx_bitset_index_count(struct index *base, enum iterator_type type, struct memtx_bitset_index *index = (struct memtx_bitset_index *)base; if (type == ITER_ALL) - return bitset_index_size(&index->index); + return tt_bitset_index_size(&index->index); assert(part_count == 1); /* checked by key_validate() */ uint32_t bitset_key_size = 0; @@ -417,7 +423,7 @@ memtx_bitset_index_count(struct index *base, enum iterator_type type, * bitset_index_count(). */ if (bit_iterator_next(&bit_it) == SIZE_MAX) - return bitset_index_count(&index->index, bit); + return tt_bitset_index_count(&index->index, bit); } else if (type == ITER_BITS_ALL_SET) { /** * Optimization: for an empty key return 0. @@ -431,7 +437,7 @@ memtx_bitset_index_count(struct index *base, enum iterator_type type, * bitset_index_count(). */ if (bit_iterator_next(&bit_it) == SIZE_MAX) - return bitset_index_count(&index->index, bit); + return tt_bitset_index_count(&index->index, bit); } else if (type == ITER_BITS_ALL_NOT_SET) { /** * Optimization: for an empty key return the number of items @@ -440,14 +446,14 @@ memtx_bitset_index_count(struct index *base, enum iterator_type type, bit_iterator_init(&bit_it, bitset_key, bitset_key_size, true); bit = bit_iterator_next(&bit_it); if (bit == SIZE_MAX) - return bitset_index_size(&index->index); + return tt_bitset_index_size(&index->index); /** * Optimiation: for the single bit key use * bitset_index_count(). */ if (bit_iterator_next(&bit_it) == SIZE_MAX) - return bitset_index_size(&index->index) - - bitset_index_count(&index->index, bit); + return tt_bitset_index_size(&index->index) - + tt_bitset_index_count(&index->index, bit); } /* Call generic method */ @@ -486,7 +492,7 @@ memtx_bitset_index_new(struct memtx_engine *memtx, struct index_def *def) if (!mempool_is_initialized(&memtx->bitset_iterator_pool)) { mempool_create(&memtx->bitset_iterator_pool, cord_slab_cache(), - sizeof(struct bitset_index_iterator)); + sizeof(struct tt_bitset_index_iterator)); } struct memtx_bitset_index *index = @@ -515,6 +521,6 @@ memtx_bitset_index_new(struct memtx_engine *memtx, struct index_def *def) panic("failed to allocate memtx bitset index"); #endif /* #ifndef OLD_GOOD_BITSET */ - bitset_index_create(&index->index, realloc); + tt_bitset_index_create(&index->index, realloc); return index; } diff --git a/src/box/memtx_bitset.h b/src/box/memtx_bitset.h index 0b8f48a..62971dd 100644 --- a/src/box/memtx_bitset.h +++ b/src/box/memtx_bitset.h @@ -51,7 +51,7 @@ struct mh_bitset_index_t; struct memtx_bitset_index { struct index base; - struct bitset_index index; + struct tt_bitset_index index; #ifndef OLD_GOOD_BITSET struct matras *id_to_tuple; struct mh_bitset_index_t *tuple_to_id; diff --git a/src/lib/bitset/bitset.c b/src/lib/bitset/bitset.c index ae2a033..f785adf 100644 --- a/src/lib/bitset/bitset.c +++ b/src/lib/bitset/bitset.c @@ -37,73 +37,78 @@ #include void -bitset_create(struct bitset *bitset, void *(*realloc)(void *ptr, size_t size)) +tt_bitset_create(struct tt_bitset *bitset, + void *(*realloc)(void *ptr, size_t size)) { memset(bitset, 0, sizeof(*bitset)); bitset->realloc = realloc; /* Initialize pages tree */ - bitset_pages_new(&bitset->pages); + tt_bitset_pages_new(&bitset->pages); } -static struct bitset_page * -bitset_destroy_iter_cb(bitset_pages_t *t, struct bitset_page *page, void *arg) +static struct tt_bitset_page * +tt_bitset_destroy_iter_cb(tt_bitset_pages_t *t, struct tt_bitset_page *page, + void *arg) { (void) t; - struct bitset *bitset = (struct bitset *) arg; - bitset_page_destroy(page); + struct tt_bitset *bitset = (struct tt_bitset *) arg; + tt_bitset_page_destroy(page); bitset->realloc(page, 0); return NULL; } void -bitset_destroy(struct bitset *bitset) +tt_bitset_destroy(struct tt_bitset *bitset) { - bitset_pages_iter(&bitset->pages, NULL, bitset_destroy_iter_cb, bitset); + tt_bitset_pages_iter(&bitset->pages, NULL, tt_bitset_destroy_iter_cb, + bitset); memset(&bitset->pages, 0, sizeof(bitset->pages)); } bool -bitset_test(struct bitset *bitset, size_t pos) +tt_bitset_test(struct tt_bitset *bitset, size_t pos) { - struct bitset_page key; - key.first_pos = bitset_page_first_pos(pos); + struct tt_bitset_page key; + key.first_pos = tt_bitset_page_first_pos(pos); /* Find a page in pages tree */ - struct bitset_page *page = bitset_pages_search(&bitset->pages, &key); + struct tt_bitset_page *page = + tt_bitset_pages_search(&bitset->pages, &key); if (page == NULL) return false; assert(page->first_pos <= pos && pos < page->first_pos + BITSET_PAGE_DATA_SIZE * CHAR_BIT); - return bit_test(bitset_page_data(page), pos - page->first_pos); + return bit_test(tt_bitset_page_data(page), pos - page->first_pos); } int -bitset_set(struct bitset *bitset, size_t pos) +tt_bitset_set(struct tt_bitset *bitset, size_t pos) { - struct bitset_page key; - key.first_pos = bitset_page_first_pos(pos); + struct tt_bitset_page key; + key.first_pos = tt_bitset_page_first_pos(pos); /* Find a page in pages tree */ - struct bitset_page *page = bitset_pages_search(&bitset->pages, &key); + struct tt_bitset_page *page = + tt_bitset_pages_search(&bitset->pages, &key); if (page == NULL) { /* Allocate a new page */ - size_t size = bitset_page_alloc_size(bitset->realloc); + size_t size = tt_bitset_page_alloc_size(bitset->realloc); page = bitset->realloc(NULL, size); if (page == NULL) return -1; - bitset_page_create(page); + tt_bitset_page_create(page); page->first_pos = key.first_pos; /* Insert the page into pages tree */ - bitset_pages_insert(&bitset->pages, page); + tt_bitset_pages_insert(&bitset->pages, page); } assert(page->first_pos <= pos && pos < page->first_pos + BITSET_PAGE_DATA_SIZE * CHAR_BIT); - bool prev = bit_set(bitset_page_data(page), pos - page->first_pos); + bool prev = bit_set(tt_bitset_page_data(page), pos - page->first_pos); if (prev) { /* Value has not changed */ return 1; @@ -116,19 +121,20 @@ bitset_set(struct bitset *bitset, size_t pos) } int -bitset_clear(struct bitset *bitset, size_t pos) +tt_bitset_clear(struct tt_bitset *bitset, size_t pos) { - struct bitset_page key; - key.first_pos = bitset_page_first_pos(pos); + struct tt_bitset_page key; + key.first_pos = tt_bitset_page_first_pos(pos); /* Find a page in the pages tree */ - struct bitset_page *page = bitset_pages_search(&bitset->pages, &key); + struct tt_bitset_page *page = + tt_bitset_pages_search(&bitset->pages, &key); if (page == NULL) return 0; assert(page->first_pos <= pos && pos < page->first_pos + BITSET_PAGE_DATA_SIZE * CHAR_BIT); - bool prev = bit_clear(bitset_page_data(page), pos - page->first_pos); + bool prev = bit_clear(tt_bitset_page_data(page), pos - page->first_pos); if (!prev) { return 0; } @@ -140,9 +146,9 @@ bitset_clear(struct bitset *bitset, size_t pos) if (page->cardinality == 0) { /* Remove the page from the pages tree */ - bitset_pages_remove(&bitset->pages, page); + tt_bitset_pages_remove(&bitset->pages, page); /* Free the page */ - bitset_page_destroy(page); + tt_bitset_page_destroy(page); bitset->realloc(page, 0); } @@ -150,33 +156,33 @@ bitset_clear(struct bitset *bitset, size_t pos) } extern inline size_t -bitset_cardinality(const struct bitset *bitset); +tt_bitset_cardinality(const struct tt_bitset *bitset); void -bitset_info(struct bitset *bitset, struct bitset_info *info) +tt_bitset_info(struct tt_bitset *bitset, struct tt_bitset_info *info) { memset(info, 0, sizeof(*info)); info->page_data_size = BITSET_PAGE_DATA_SIZE; - info->page_total_size = bitset_page_alloc_size(bitset->realloc); + info->page_total_size = tt_bitset_page_alloc_size(bitset->realloc); info->page_data_alignment = BITSET_PAGE_DATA_ALIGNMENT; size_t cardinality_check = 0; - struct bitset_page *page = bitset_pages_first(&bitset->pages); + struct tt_bitset_page *page = tt_bitset_pages_first(&bitset->pages); while (page != NULL) { info->pages++; cardinality_check += page->cardinality; - page = bitset_pages_next(&bitset->pages, page); + page = tt_bitset_pages_next(&bitset->pages, page); } - assert(bitset_cardinality(bitset) == cardinality_check); + assert(tt_bitset_cardinality(bitset) == cardinality_check); } #if defined(DEBUG) void -bitset_dump(struct bitset *bitset, int verbose, FILE *stream) +tt_bitset_dump(struct tt_bitset *bitset, int verbose, FILE *stream) { - struct bitset_info info; - bitset_info(bitset, &info); + struct tt_bitset_info info; + tt_bitset_info(bitset, &info); size_t PAGE_BIT = (info.page_data_size * CHAR_BIT); @@ -225,8 +231,8 @@ bitset_dump(struct bitset *bitset, int verbose, FILE *stream) fprintf(stream, " " "pages = {\n"); - for (struct bitset_page *page = bitset_pages_first(&bitset->pages); - page != NULL; page = bitset_pages_next(&bitset->pages, page)) { + for (struct tt_bitset_page *page = tt_bitset_pages_first(&bitset->pages); + page != NULL; page = tt_bitset_pages_next(&bitset->pages, page)) { size_t page_last_pos = page->first_pos + BITSET_PAGE_DATA_SIZE * CHAR_BIT; diff --git a/src/lib/bitset/bitset.h b/src/lib/bitset/bitset.h index 87bcd26..45fd18b 100644 --- a/src/lib/bitset/bitset.h +++ b/src/lib/bitset/bitset.h @@ -66,22 +66,22 @@ extern "C" { #endif /* defined(__cplusplus) */ /** @cond false */ -struct bitset_page { +struct tt_bitset_page { size_t first_pos; - rb_node(struct bitset_page) node; + rb_node(struct tt_bitset_page) node; size_t cardinality; uint8_t data[0]; }; -typedef rb_tree(struct bitset_page) bitset_pages_t; +typedef rb_tree(struct tt_bitset_page) tt_bitset_pages_t; /** @endcond */ /** * Bitset */ -struct bitset { +struct tt_bitset { /** @cond false */ - bitset_pages_t pages; + tt_bitset_pages_t pages; size_t cardinality; void *(*realloc)(void *ptr, size_t size); /** @endcond */ @@ -93,14 +93,15 @@ struct bitset { * @param realloc memory allocator to use */ void -bitset_create(struct bitset *bitset, void *(*realloc)(void *ptr, size_t size)); +tt_bitset_create(struct tt_bitset *bitset, void *(*realloc)(void *ptr, + size_t size)); /** * @brief Destruct \a bitset * @param bitset bitset */ void -bitset_destroy(struct bitset *bitset); +tt_bitset_destroy(struct tt_bitset *bitset); /** * @brief Test bit \a pos in \a bitset @@ -110,7 +111,7 @@ bitset_destroy(struct bitset *bitset); * @retval false if \a pos is not set in \a bitset */ bool -bitset_test(struct bitset *bitset, size_t pos); +tt_bitset_test(struct tt_bitset *bitset, size_t pos); /** * @brief Set bit \a pos in \a bitset @@ -121,7 +122,7 @@ bitset_test(struct bitset *bitset, size_t pos); * @retval -1 on memory error */ int -bitset_set(struct bitset *bitset, size_t pos); +tt_bitset_set(struct tt_bitset *bitset, size_t pos); /** * @brief Clear bit \a pos in \a bitset @@ -132,7 +133,7 @@ bitset_set(struct bitset *bitset, size_t pos); * @retval -1 on memory error */ int -bitset_clear(struct bitset *bitset, size_t pos); +tt_bitset_clear(struct tt_bitset *bitset, size_t pos); /** * @brief Return the number of bits set to \a true in \a bitset. @@ -140,7 +141,7 @@ bitset_clear(struct bitset *bitset, size_t pos); * @return returns the number of bits set to \a true in \a bitset. */ inline size_t -bitset_cardinality(const struct bitset *bitset) { +tt_bitset_cardinality(const struct tt_bitset *bitset) { return bitset->cardinality; } @@ -148,7 +149,7 @@ bitset_cardinality(const struct bitset *bitset) { * @brief Bitset Information structure * @see bitset_info */ -struct bitset_info { +struct tt_bitset_info { /** Number of allocated pages */ size_t pages; /** Data (payload) size of one page (in bytes) */ @@ -165,11 +166,11 @@ struct bitset_info { * @param stat structure to fill */ void -bitset_info(struct bitset *bitset, struct bitset_info *info); +tt_bitset_info(struct tt_bitset *bitset, struct tt_bitset_info *info); #if defined(DEBUG) void -bitset_dump(struct bitset *bitset, int verbose, FILE *stream); +tt_bitset_dump(struct tt_bitset *bitset, int verbose, FILE *stream); #endif /* defined(DEBUG) */ #if defined(__cplusplus) diff --git a/src/lib/bitset/expr.c b/src/lib/bitset/expr.c index f40fa73..cd32bc7 100644 --- a/src/lib/bitset/expr.c +++ b/src/lib/bitset/expr.c @@ -39,15 +39,15 @@ const size_t EXPR_DEFAULT_CAPACITY = 2; const size_t EXPR_CONJ_DEFAULT_CAPACITY = 32; void -bitset_expr_create(struct bitset_expr *expr, - void *(*realloc)(void *ptr, size_t size)) +tt_bitset_expr_create(struct tt_bitset_expr *expr, + void *(*realloc)(void *ptr, size_t size)) { memset(expr, 0, sizeof(*expr)); expr->realloc = realloc; } void -bitset_expr_destroy(struct bitset_expr *expr) +tt_bitset_expr_destroy(struct tt_bitset_expr *expr) { for (size_t c = 0; c < expr->size; c++) { if (expr->conjs[c].capacity == 0) @@ -65,7 +65,7 @@ bitset_expr_destroy(struct bitset_expr *expr) } void -bitset_expr_clear(struct bitset_expr *expr) +tt_bitset_expr_clear(struct tt_bitset_expr *expr) { for (size_t c = 0; c < expr->size; c++) { memset(expr->conjs[c].bitset_ids, 0, expr->conjs[c].size * @@ -79,7 +79,7 @@ bitset_expr_clear(struct bitset_expr *expr) } static int -bitset_expr_reserve(struct bitset_expr *expr, size_t size) +tt_bitset_expr_reserve(struct tt_bitset_expr *expr, size_t size) { if (size <= expr->capacity) return 0; @@ -92,7 +92,7 @@ bitset_expr_reserve(struct bitset_expr *expr, size_t size) capacity *= 2; } - struct bitset_expr_conj *conjs = + struct tt_bitset_expr_conj *conjs = expr->realloc(expr->conjs, capacity * sizeof(*expr->conjs)); if (conjs == NULL) @@ -107,9 +107,9 @@ bitset_expr_reserve(struct bitset_expr *expr, size_t size) } int -bitset_expr_add_conj(struct bitset_expr *expr) +tt_bitset_expr_add_conj(struct tt_bitset_expr *expr) { - if (bitset_expr_reserve(expr, expr->size + 1) != 0) + if (tt_bitset_expr_reserve(expr, expr->size + 1) != 0) return -1; expr->size++; @@ -118,8 +118,8 @@ bitset_expr_add_conj(struct bitset_expr *expr) } static int -bitset_expr_conj_reserve(struct bitset_expr *expr, - struct bitset_expr_conj *conj, size_t size) +tt_bitset_expr_conj_reserve(struct tt_bitset_expr *expr, + struct tt_bitset_expr_conj *conj, size_t size) { if (size <= conj->capacity) return 0; @@ -159,13 +159,13 @@ error_1: } int -bitset_expr_add_param(struct bitset_expr *expr, size_t bitset_id, - bool pre_not) +tt_bitset_expr_add_param(struct tt_bitset_expr *expr, size_t bitset_id, + bool pre_not) { assert(expr->size > 0); - struct bitset_expr_conj *conj = &expr->conjs[expr->size - 1]; + struct tt_bitset_expr_conj *conj = &expr->conjs[expr->size - 1]; - if (bitset_expr_conj_reserve(expr, conj, conj->size + 1) != 0) + if (tt_bitset_expr_conj_reserve(expr, conj, conj->size + 1) != 0) return -1; conj->bitset_ids[conj->size] = bitset_id; diff --git a/src/lib/bitset/expr.h b/src/lib/bitset/expr.h index 712d408..18668b2 100644 --- a/src/lib/bitset/expr.h +++ b/src/lib/bitset/expr.h @@ -69,7 +69,7 @@ extern "C" { #endif /* defined(__cplusplus) */ /** @cond false **/ -struct bitset_expr_conj { +struct tt_bitset_expr_conj { size_t size; size_t capacity; size_t *bitset_ids; @@ -80,14 +80,14 @@ struct bitset_expr_conj { /** * @brief Bitset Expression */ -struct bitset_expr { +struct tt_bitset_expr { /** @cond false **/ /** Size of \a conjs array **/ size_t size; /** Capacity of \a conjs array **/ size_t capacity; /** Array of conjunctions **/ - struct bitset_expr_conj *conjs; + struct tt_bitset_expr_conj *conjs; /** Memory allocator **/ void *(*realloc)(void *ptr, size_t size); /** @endcond **/ @@ -99,15 +99,15 @@ struct bitset_expr { * @param realloc memory allocator to use */ void -bitset_expr_create(struct bitset_expr *expr, - void *(*realloc)(void *ptr, size_t size)); +tt_bitset_expr_create(struct tt_bitset_expr *expr, + void *(*realloc)(void *ptr, size_t size)); /** * @brief Destruct bitset expression \a expr * @param expr bitset expression */ void -bitset_expr_destroy(struct bitset_expr *expr); +tt_bitset_expr_destroy(struct tt_bitset_expr *expr); /** * @brief Clear @a expr (remove all conjunctions from it) @@ -117,7 +117,7 @@ bitset_expr_destroy(struct bitset_expr *expr); * the object completely. */ void -bitset_expr_clear(struct bitset_expr *expr); +tt_bitset_expr_clear(struct tt_bitset_expr *expr); /** * @brief Add a new conjunction to \a expr. @@ -126,7 +126,7 @@ bitset_expr_clear(struct bitset_expr *expr); * @retval -1 on memory error */ int -bitset_expr_add_conj(struct bitset_expr *expr); +tt_bitset_expr_add_conj(struct tt_bitset_expr *expr); /** * @brief Add a new placeholder for a bitset to the current conjunction. @@ -138,7 +138,8 @@ bitset_expr_add_conj(struct bitset_expr *expr); * @retval -1 on memory error */ int -bitset_expr_add_param(struct bitset_expr *expr, size_t bitset_id, bool pre_not); +tt_bitset_expr_add_param(struct tt_bitset_expr *expr, size_t bitset_id, + bool pre_not); #if defined(__cplusplus) } /* extern "C" */ diff --git a/src/lib/bitset/index.c b/src/lib/bitset/index.c index 4a5bad8..7905feb 100644 --- a/src/lib/bitset/index.c +++ b/src/lib/bitset/index.c @@ -39,8 +39,8 @@ const size_t INDEX_DEFAULT_CAPACITY = 32; void -bitset_index_create(struct bitset_index *index, - void *(*realloc)(void *ptr, size_t size)) +tt_bitset_index_create(struct tt_bitset_index *index, + void *(*realloc)(void *ptr, size_t size)) { assert(index != NULL); memset(index, 0, sizeof(*index)); @@ -48,7 +48,7 @@ bitset_index_create(struct bitset_index *index, } void -bitset_index_destroy(struct bitset_index *index) +tt_bitset_index_destroy(struct tt_bitset_index *index) { assert(index != NULL); @@ -56,7 +56,7 @@ bitset_index_destroy(struct bitset_index *index) if (index->bitsets[b] == NULL) break; - bitset_destroy(index->bitsets[b]); + tt_bitset_destroy(index->bitsets[b]); index->realloc(index->bitsets[b], 0); index->bitsets[b] = NULL; } @@ -69,7 +69,7 @@ bitset_index_destroy(struct bitset_index *index) } static int -bitset_index_reserve(struct bitset_index *index, size_t size) +tt_bitset_index_reserve(struct tt_bitset_index *index, size_t size) { if (size <= index->capacity) return 0; @@ -82,7 +82,7 @@ bitset_index_reserve(struct bitset_index *index, size_t size) capacity *= 2; } - struct bitset **bitsets = index->realloc(index->bitsets, + struct tt_bitset **bitsets = index->realloc(index->bitsets, capacity * sizeof(*index->bitsets)); if (bitsets == NULL) goto error_1; @@ -108,7 +108,7 @@ bitset_index_reserve(struct bitset_index *index, size_t size) if (index->bitsets[b] == NULL) goto error_2; - bitset_create(index->bitsets[b], index->realloc); + tt_bitset_create(index->bitsets[b], index->realloc); } index->capacity = capacity; @@ -120,7 +120,7 @@ error_2: if (index->bitsets[b] == NULL) break; - bitset_destroy(index->bitsets[b]); + tt_bitset_destroy(index->bitsets[b]); index->realloc(index->bitsets[b], 0); index->bitsets[b] = NULL; } @@ -129,8 +129,8 @@ error_1: } int -bitset_index_insert(struct bitset_index *index, const void *key, - size_t key_size, size_t value) +tt_bitset_index_insert(struct tt_bitset_index *index, const void *key, + size_t key_size, size_t value) { assert(index != NULL); assert(key != NULL); @@ -138,20 +138,20 @@ bitset_index_insert(struct bitset_index *index, const void *key, /* * Step 0: allocate enough number of bitsets * - * bitset_index_reserve could fail on realloc and return -1. + * tt_bitset_index_reserve could fail on realloc and return -1. * Do not change anything and return the error to the caller. */ const size_t size = 1 + key_size * CHAR_BIT; - if (bitset_index_reserve(index, size) != 0) + if (tt_bitset_index_reserve(index, size) != 0) return -1; /* * Step 1: set the 'flag' bitset * - * bitset_set for 'falg' bitset could fail on realloc. + * tt_bitset_set for 'falg' bitset could fail on realloc. * Do not change anything. Do not shrink buffers allocated on step 1. */ - int rc = bitset_set(index->bitsets[0], value); + int rc = tt_bitset_set(index->bitsets[0], value); if (rc < 0) return -1; @@ -167,7 +167,7 @@ bitset_index_insert(struct bitset_index *index, const void *key, * A bitset_set somewhere in the middle also could fail on realloc. * If this happens, we stop processing and jump to the rollback code. * Rollback uses index->rollback_buf buffer to restore previous values - * of all bitsets on given position. Remember, that bitset_set + * of all bitsets on given position. Remember, that tt_bitset_set * returns 1 if a previous value was 'true' and 0 if it was 'false'. * The buffer is indexed by bytes (char *) instead of bits (bit_set) * because it is a little bit faster here. @@ -177,7 +177,7 @@ bitset_index_insert(struct bitset_index *index, const void *key, size_t pos = 0; while ((pos = bit_iterator_next(&bit_it)) != SIZE_MAX) { size_t b = pos + 1; - rc = bitset_set(index->bitsets[b], value); + rc = tt_bitset_set(index->bitsets[b], value); if (rc < 0) goto rollback; @@ -196,9 +196,9 @@ rollback: size_t b = rpos + 1; if (index->rollback_buf[b] == 1) { - bitset_set(index->bitsets[b], value); + tt_bitset_set(index->bitsets[b], value); } else { - bitset_clear(index->bitsets[b], value); + tt_bitset_clear(index->bitsets[b], value); } } @@ -206,16 +206,16 @@ rollback: * Rollback changes done by Step 1. */ if (index->rollback_buf[0] == 1) { - bitset_set(index->bitsets[0], value); + tt_bitset_set(index->bitsets[0], value); } else { - bitset_clear(index->bitsets[0], value); + tt_bitset_clear(index->bitsets[0], value); } return -1; } void -bitset_index_remove_value(struct bitset_index *index, size_t value) +tt_bitset_index_remove_value(struct tt_bitset_index *index, size_t value) { assert(index != NULL); @@ -227,51 +227,51 @@ bitset_index_remove_value(struct bitset_index *index, size_t value) continue; /* Ignore all errors here */ - bitset_clear(index->bitsets[b], value); + tt_bitset_clear(index->bitsets[b], value); } - bitset_clear(index->bitsets[0], value); + tt_bitset_clear(index->bitsets[0], value); } bool -bitset_index_contains_value(struct bitset_index *index, size_t value) +tt_bitset_index_contains_value(struct tt_bitset_index *index, size_t value) { assert(index != NULL); - return bitset_test(index->bitsets[0], value); + return tt_bitset_test(index->bitsets[0], value); } int -bitset_index_expr_all(struct bitset_expr *expr) +tt_bitset_index_expr_all(struct tt_bitset_expr *expr) { (void) index; - bitset_expr_clear(expr); - if (bitset_expr_add_conj(expr) != 0) + tt_bitset_expr_clear(expr); + if (tt_bitset_expr_add_conj(expr) != 0) return -1; - if (bitset_expr_add_param(expr, 0, false) != 0) + if (tt_bitset_expr_add_param(expr, 0, false) != 0) return -1; return 0; } int -bitset_index_expr_equals(struct bitset_expr *expr, const void *key, - size_t key_size) +tt_bitset_index_expr_equals(struct tt_bitset_expr *expr, const void *key, + size_t key_size) { - bitset_expr_clear(expr); + tt_bitset_expr_clear(expr); - if (bitset_expr_add_conj(expr) != 0) + if (tt_bitset_expr_add_conj(expr) != 0) return -1; for (size_t pos = 0; pos < key_size * CHAR_BIT; pos++) { size_t b = pos + 1; bool bit_exist = bit_test(key, pos); - if (bitset_expr_add_param(expr, b, !bit_exist) != 0) + if (tt_bitset_expr_add_param(expr, b, !bit_exist) != 0) return -1; } - if (bitset_expr_add_param(expr, 0, false) != 0) { + if (tt_bitset_expr_add_param(expr, 0, false) != 0) { return -1; } @@ -279,12 +279,12 @@ bitset_index_expr_equals(struct bitset_expr *expr, const void *key, } int -bitset_index_expr_all_set(struct bitset_expr *expr, const void *key, - size_t key_size) +tt_bitset_index_expr_all_set(struct tt_bitset_expr *expr, const void *key, + size_t key_size) { - bitset_expr_clear(expr); + tt_bitset_expr_clear(expr); - if (bitset_expr_add_conj(expr) != 0) + if (tt_bitset_expr_add_conj(expr) != 0) return -1; if (key_size == 0) @@ -295,7 +295,7 @@ bitset_index_expr_all_set(struct bitset_expr *expr, const void *key, size_t pos; while ( (pos = bit_iterator_next(&bit_it)) != SIZE_MAX ) { size_t b = pos + 1; - if (bitset_expr_add_param(expr, b, false) != 0) + if (tt_bitset_expr_add_param(expr, b, false) != 0) return -1; } @@ -303,10 +303,10 @@ bitset_index_expr_all_set(struct bitset_expr *expr, const void *key, } int -bitset_index_expr_any_set(struct bitset_expr *expr, const void *key, - size_t key_size) +tt_bitset_index_expr_any_set(struct tt_bitset_expr *expr, const void *key, + size_t key_size) { - bitset_expr_clear(expr); + tt_bitset_expr_clear(expr); if (key_size == 0) return 0; /* optimization for empty key */ @@ -316,9 +316,9 @@ bitset_index_expr_any_set(struct bitset_expr *expr, const void *key, size_t pos; while ( (pos = bit_iterator_next(&bit_it)) != SIZE_MAX) { size_t b = pos + 1; - if (bitset_expr_add_conj(expr) != 0) + if (tt_bitset_expr_add_conj(expr) != 0) return -1; - if (bitset_expr_add_param(expr, b, false) != 0) + if (tt_bitset_expr_add_param(expr, b, false) != 0) return -1; } @@ -326,14 +326,14 @@ bitset_index_expr_any_set(struct bitset_expr *expr, const void *key, } int -bitset_index_expr_all_not_set(struct bitset_expr *expr, const void *key, - size_t key_size) { - bitset_expr_clear(expr); +tt_bitset_index_expr_all_not_set(struct tt_bitset_expr *expr, const void *key, + size_t key_size) { + tt_bitset_expr_clear(expr); - if (bitset_expr_add_conj(expr) != 0) + if (tt_bitset_expr_add_conj(expr) != 0) return -1; - if (bitset_expr_add_param(expr, 0, false) != 0) + if (tt_bitset_expr_add_param(expr, 0, false) != 0) return -1; if (key_size == 0) @@ -344,7 +344,7 @@ bitset_index_expr_all_not_set(struct bitset_expr *expr, const void *key, size_t pos; while ( (pos = bit_iterator_next(&bit_it)) != SIZE_MAX) { size_t b = pos + 1; - if (bitset_expr_add_param(expr, b, true) != 0) + if (tt_bitset_expr_add_param(expr, b, true) != 0) return -1; } @@ -352,8 +352,9 @@ bitset_index_expr_all_not_set(struct bitset_expr *expr, const void *key, } int -bitset_index_init_iterator(struct bitset_index *index, - struct bitset_iterator *it, struct bitset_expr *expr) +tt_bitset_index_init_iterator(struct tt_bitset_index *index, + struct tt_bitset_iterator *it, + struct tt_bitset_expr *expr) { assert(index != NULL); assert(it != NULL); @@ -369,28 +370,29 @@ bitset_index_init_iterator(struct bitset_index *index, } /* Resize the index with empty bitsets */ - if (bitset_index_reserve(index, max + 1) != 0) + if (tt_bitset_index_reserve(index, max + 1) != 0) return -1; - return bitset_iterator_init(it, expr, index->bitsets, index->capacity); + return tt_bitset_iterator_init(it, expr, index->bitsets, + index->capacity); } size_t -bitset_index_bsize(const struct bitset_index *index) +tt_bitset_index_bsize(const struct tt_bitset_index *index) { size_t result = 0; for (size_t b = 0; b < index->capacity; b++) { if (index->bitsets[b] == NULL) continue; - struct bitset_info info; - bitset_info(index->bitsets[b], &info); + struct tt_bitset_info info; + tt_bitset_info(index->bitsets[b], &info); result += info.page_total_size * info.pages; } return result; } extern inline size_t -bitset_index_size(const struct bitset_index *index); +tt_bitset_index_size(const struct tt_bitset_index *index); extern inline size_t -bitset_index_count(const struct bitset_index *index, size_t bit); +tt_bitset_index_count(const struct tt_bitset_index *index, size_t bit); diff --git a/src/lib/bitset/index.h b/src/lib/bitset/index.h index 20b3319..e9922dd 100644 --- a/src/lib/bitset/index.h +++ b/src/lib/bitset/index.h @@ -123,10 +123,10 @@ extern "C" { /** * @brief BitsetIndex */ -struct bitset_index { +struct tt_bitset_index { /** @cond false **/ /* Used bitsets */ - struct bitset **bitsets; + struct tt_bitset **bitsets; /* Capacity of bitsets array */ size_t capacity; /* Memory allocator to use */ @@ -142,15 +142,15 @@ struct bitset_index { * @param realloc memory allocator to use */ void -bitset_index_create(struct bitset_index *index, - void *(*realloc)(void *ptr, size_t size)); +tt_bitset_index_create(struct tt_bitset_index *index, + void *(*realloc)(void *ptr, size_t size)); /** * @brief Destruct \a index * @param index bitset index */ void -bitset_index_destroy(struct bitset_index *index); +tt_bitset_index_destroy(struct tt_bitset_index *index); /** * @brief Insert (\a key, \a value) pair into \a index. @@ -166,8 +166,8 @@ bitset_index_destroy(struct bitset_index *index); * @retval -1 on memory error */ int -bitset_index_insert(struct bitset_index *index, const void *key, size_t key_size, - size_t value); +tt_bitset_index_insert(struct tt_bitset_index *index, const void *key, + size_t key_size, size_t value); /** * @brief Remove a pair with \a value (*, \a value) from \a index. @@ -175,7 +175,7 @@ bitset_index_insert(struct bitset_index *index, const void *key, size_t key_size * @param value value */ void -bitset_index_remove_value(struct bitset_index *index, size_t value); +tt_bitset_index_remove_value(struct tt_bitset_index *index, size_t value); /** * @brief Initialize \a expr to iterate over a bitset index. @@ -190,7 +190,7 @@ bitset_index_remove_value(struct bitset_index *index, size_t value); * @see expr.h */ int -bitset_index_expr_all(struct bitset_expr *expr); +tt_bitset_index_expr_all(struct tt_bitset_expr *expr); /** * @brief Initialize \a expr to iterate over a bitset index. @@ -208,8 +208,8 @@ bitset_index_expr_all(struct bitset_expr *expr); * @see expr.h */ int -bitset_index_expr_equals(struct bitset_expr *expr, const void *key, - size_t key_size); +tt_bitset_index_expr_equals(struct tt_bitset_expr *expr, const void *key, + size_t key_size); /** * @brief Initialize \a expr to iterate over a bitset index. @@ -225,8 +225,8 @@ bitset_index_expr_equals(struct bitset_expr *expr, const void *key, * @see expr.h */ int -bitset_index_expr_all_set(struct bitset_expr *expr, const void *key, - size_t key_size); +tt_bitset_index_expr_all_set(struct tt_bitset_expr *expr, const void *key, + size_t key_size); /** * @brief Initialize \a expr to iterate over a bitset index. @@ -242,8 +242,8 @@ bitset_index_expr_all_set(struct bitset_expr *expr, const void *key, * @see expr.h */ int -bitset_index_expr_any_set(struct bitset_expr *expr, const void *key, - size_t key_size); +tt_bitset_index_expr_any_set(struct tt_bitset_expr *expr, const void *key, + size_t key_size); /** * @brief Initialize \a expr to iterate over a bitset index. @@ -259,8 +259,8 @@ bitset_index_expr_any_set(struct bitset_expr *expr, const void *key, * @see expr.h */ int -bitset_index_expr_all_not_set(struct bitset_expr *expr, const void *key, - size_t key_size); +tt_bitset_index_expr_all_not_set(struct tt_bitset_expr *expr, const void *key, + size_t key_size); /** * @brief Initialize \a it using \a expr and bitsets used in \a index. @@ -272,9 +272,9 @@ bitset_index_expr_all_not_set(struct bitset_expr *expr, const void *key, * @retval 1 on memory error */ int -bitset_index_init_iterator(struct bitset_index *index, - struct bitset_iterator *it, - struct bitset_expr *expr); +tt_bitset_index_init_iterator(struct tt_bitset_index *index, + struct tt_bitset_iterator *it, + struct tt_bitset_expr *expr); /** * @brief Checks if a (*, \a value) pair exists in \a index @@ -284,7 +284,7 @@ bitset_index_init_iterator(struct bitset_index *index, * @retval false otherwise */ bool -bitset_index_contains_value(struct bitset_index *index, size_t value); +tt_bitset_index_contains_value(struct tt_bitset_index *index, size_t value); /** * @brief Return the number of pairs in \a index. @@ -292,9 +292,9 @@ bitset_index_contains_value(struct bitset_index *index, size_t value); * @return number of pairs in \a index */ inline size_t -bitset_index_size(const struct bitset_index *index) +tt_bitset_index_size(const struct tt_bitset_index *index) { - return bitset_cardinality(index->bitsets[0]); + return tt_bitset_cardinality(index->bitsets[0]); } /** @@ -304,11 +304,11 @@ bitset_index_size(const struct bitset_index *index) * @retval the number of (key, value ) pairs where (@a bit & key) != 0 */ inline size_t -bitset_index_count(const struct bitset_index *index, size_t bit) +tt_bitset_index_count(const struct tt_bitset_index *index, size_t bit) { if (bit + 1 >= index->capacity) return 0; - return bitset_cardinality(index->bitsets[bit + 1]); + return tt_bitset_cardinality(index->bitsets[bit + 1]); } /** @@ -318,11 +318,11 @@ bitset_index_count(const struct bitset_index *index, size_t bit) * @return number of bytes used by index. */ size_t -bitset_index_bsize(const struct bitset_index *index); +tt_bitset_index_bsize(const struct tt_bitset_index *index); #if defined(DEBUG) void -bitset_index_dump(struct bitset_index *index, int verbose, FILE *stream); +tt_bitset_index_dump(struct tt_bitset_index *index, int verbose, FILE *stream); #endif /* defined(DEBUG) */ #if defined(__cplusplus) diff --git a/src/lib/bitset/iterator.c b/src/lib/bitset/iterator.c index 97f5ab0..226c852 100644 --- a/src/lib/bitset/iterator.c +++ b/src/lib/bitset/iterator.c @@ -38,13 +38,13 @@ const size_t ITERATOR_DEFAULT_CAPACITY = 2; const size_t ITERATOR_CONJ_DEFAULT_CAPACITY = 32; -struct bitset_iterator_conj { +struct tt_bitset_iterator_conj { size_t page_first_pos; size_t size; size_t capacity; - struct bitset **bitsets; + struct tt_bitset **bitsets; bool *pre_nots; - struct bitset_page **pages; + struct tt_bitset_page **pages; }; /** @@ -53,8 +53,8 @@ struct bitset_iterator_conj { * @param realloc memory allocator to use */ void -bitset_iterator_create(struct bitset_iterator *it, - void *(*realloc)(void *ptr, size_t size)) +tt_bitset_iterator_create(struct tt_bitset_iterator *it, + void *(*realloc)(void *ptr, size_t size)) { memset(it, 0, sizeof(*it)); it->realloc = realloc; @@ -66,7 +66,7 @@ bitset_iterator_create(struct bitset_iterator *it, * @see bitset_iterator_new */ void -bitset_iterator_destroy(struct bitset_iterator *it) +tt_bitset_iterator_destroy(struct tt_bitset_iterator *it) { for (size_t c = 0; c < it->size; c++) { if (it->conjs[c].capacity == 0) @@ -82,12 +82,12 @@ bitset_iterator_destroy(struct bitset_iterator *it) } if (it->page != NULL) { - bitset_page_destroy(it->page); + tt_bitset_page_destroy(it->page); it->realloc(it->page, 0); } if (it->page_tmp != NULL) { - bitset_page_destroy(it->page_tmp); + tt_bitset_page_destroy(it->page_tmp); it->realloc(it->page_tmp, 0); } @@ -96,7 +96,7 @@ bitset_iterator_destroy(struct bitset_iterator *it) static int -bitset_iterator_reserve(struct bitset_iterator *it, size_t size) +tt_bitset_iterator_reserve(struct tt_bitset_iterator *it, size_t size) { if (size <= it->capacity) return 0; @@ -109,7 +109,7 @@ bitset_iterator_reserve(struct bitset_iterator *it, size_t size) capacity *= 2; } - struct bitset_iterator_conj *conjs = + struct tt_bitset_iterator_conj *conjs = it->realloc(it->conjs, capacity * sizeof(*it->conjs)); if (conjs == NULL) return -1; @@ -124,8 +124,9 @@ bitset_iterator_reserve(struct bitset_iterator *it, size_t size) } static int -bitset_iterator_conj_reserve(struct bitset_iterator *it, - struct bitset_iterator_conj *conj, size_t size) +tt_bitset_iterator_conj_reserve(struct tt_bitset_iterator *it, + struct tt_bitset_iterator_conj *conj, + size_t size) { if (size <= conj->capacity) return 0; @@ -138,7 +139,7 @@ bitset_iterator_conj_reserve(struct bitset_iterator *it, capacity *= 2; } - struct bitset **bitsets = it->realloc(conj->bitsets, + struct tt_bitset **bitsets = it->realloc(conj->bitsets, capacity * sizeof(*conj->bitsets)); if (bitsets == NULL) goto error_1; @@ -146,7 +147,7 @@ bitset_iterator_conj_reserve(struct bitset_iterator *it, capacity * sizeof(*conj->pre_nots)); if (pre_nots == NULL) goto error_2; - struct bitset_page **pages = it->realloc(conj->pages, + struct tt_bitset_page **pages = it->realloc(conj->pages, capacity * sizeof(*conj->pages)); if (pages == NULL) goto error_3; @@ -174,8 +175,9 @@ error_1: } int -bitset_iterator_init(struct bitset_iterator *it, struct bitset_expr *expr, - struct bitset **p_bitsets, size_t bitsets_size) +tt_bitset_iterator_init(struct tt_bitset_iterator *it, + struct tt_bitset_expr *expr, + struct tt_bitset **p_bitsets, size_t bitsets_size) { assert(it != NULL); assert(expr != NULL); @@ -183,34 +185,35 @@ bitset_iterator_init(struct bitset_iterator *it, struct bitset_expr *expr, assert(p_bitsets != NULL); } - size_t page_alloc_size = bitset_page_alloc_size(it->realloc); + size_t page_alloc_size = tt_bitset_page_alloc_size(it->realloc); if (it->page != NULL) { - bitset_page_destroy(it->page); + tt_bitset_page_destroy(it->page); } else { it->page = it->realloc(NULL, page_alloc_size); } - bitset_page_create(it->page); + tt_bitset_page_create(it->page); if (it->page_tmp != NULL) { - bitset_page_destroy(it->page_tmp); + tt_bitset_page_destroy(it->page_tmp); } else { it->page_tmp = it->realloc(NULL, page_alloc_size); if (it->page_tmp == NULL) return -1; } - bitset_page_create(it->page_tmp); + tt_bitset_page_create(it->page_tmp); - if (bitset_iterator_reserve(it, expr->size) != 0) + if (tt_bitset_iterator_reserve(it, expr->size) != 0) return -1; for (size_t c = 0; c < expr->size; c++) { - struct bitset_expr_conj *exconj = &expr->conjs[c]; - struct bitset_iterator_conj *itconj = &it->conjs[c]; + struct tt_bitset_expr_conj *exconj = &expr->conjs[c]; + struct tt_bitset_iterator_conj *itconj = &it->conjs[c]; itconj->page_first_pos = 0; - if (bitset_iterator_conj_reserve(it, itconj, exconj->size) != 0) + if (tt_bitset_iterator_conj_reserve(it, itconj, + exconj->size) != 0) return -1; for (size_t b = 0; b < exconj->size; b++) { @@ -226,13 +229,14 @@ bitset_iterator_init(struct bitset_iterator *it, struct bitset_expr *expr, it->size = expr->size; - bitset_iterator_rewind(it); + tt_bitset_iterator_rewind(it); return 0; } static void -bitset_iterator_conj_rewind(struct bitset_iterator_conj *conj, size_t pos) +tt_bitset_iterator_conj_rewind(struct tt_bitset_iterator_conj *conj, + size_t pos) { assert(conj != NULL); assert(pos % (BITSET_PAGE_DATA_SIZE * CHAR_BIT) == 0); @@ -243,13 +247,13 @@ bitset_iterator_conj_rewind(struct bitset_iterator_conj *conj, size_t pos) return; } - struct bitset_page key; + struct tt_bitset_page key; key.first_pos = pos; restart: for (size_t b = 0; b < conj->size; b++) { - conj->pages[b] = bitset_pages_nsearch(&conj->bitsets[b]->pages, - &key); + conj->pages[b] = + tt_bitset_pages_nsearch(&conj->bitsets[b]->pages, &key); #if 0 if (conj->pages[b] != NULL) { fprintf(stderr, "rewind [%zu] => %zu (%p)\n", b, @@ -280,12 +284,14 @@ bitset_iterator_conj_rewind(struct bitset_iterator_conj *conj, size_t pos) } static int -bitset_iterator_conj_cmp(const void *p1, const void *p2) +tt_bitset_iterator_conj_cmp(const void *p1, const void *p2) { assert(p1 != NULL && p2 != NULL); - struct bitset_iterator_conj *conj1 = (struct bitset_iterator_conj *) p1; - struct bitset_iterator_conj *conj2 = (struct bitset_iterator_conj *) p2; + struct tt_bitset_iterator_conj *conj1 = + (struct tt_bitset_iterator_conj *) p1; + struct tt_bitset_iterator_conj *conj2 = + (struct tt_bitset_iterator_conj *) p2; if (conj1->page_first_pos < conj2->page_first_pos) { return -1; @@ -297,20 +303,20 @@ bitset_iterator_conj_cmp(const void *p1, const void *p2) } static void -bitset_iterator_conj_prepare_page(struct bitset_iterator_conj *conj, - struct bitset_page *dst) +tt_bitset_iterator_conj_prepare_page(struct tt_bitset_iterator_conj *conj, + struct tt_bitset_page *dst) { assert(conj != NULL); assert(dst != NULL); assert(conj->size > 0); assert(conj->page_first_pos != SIZE_MAX); - bitset_page_set_ones(dst); + tt_bitset_page_set_ones(dst); for (size_t b = 0; b < conj->size; b++) { if (!conj->pre_nots[b]) { /* conj->pages[b] is rewinded to conj->page_first_pos */ assert(conj->pages[b]->first_pos == conj->page_first_pos); - bitset_page_and(dst, conj->pages[b]); + tt_bitset_page_and(dst, conj->pages[b]); } else { /* * If page is NULL or its position is not equal @@ -324,18 +330,18 @@ bitset_iterator_conj_prepare_page(struct bitset_iterator_conj *conj, conj->pages[b]->first_pos != conj->page_first_pos) continue; - bitset_page_nand(dst, conj->pages[b]); + tt_bitset_page_nand(dst, conj->pages[b]); } } } static void -bitset_iterator_prepare_page(struct bitset_iterator *it) +tt_bitset_iterator_prepare_page(struct tt_bitset_iterator *it) { qsort(it->conjs, it->size, sizeof(*it->conjs), - bitset_iterator_conj_cmp); + tt_bitset_iterator_conj_cmp); - bitset_page_set_zeros(it->page); + tt_bitset_page_set_zeros(it->page); if (it->size > 0) { it->page->first_pos = it->conjs[0].page_first_pos; } else { @@ -352,32 +358,33 @@ bitset_iterator_prepare_page(struct bitset_iterator *it) break; /* Get result from conj */ - bitset_iterator_conj_prepare_page(&it->conjs[c], it->page_tmp); + tt_bitset_iterator_conj_prepare_page(&it->conjs[c], + it->page_tmp); /* OR page from conjunction with it->page */ - bitset_page_or(it->page, it->page_tmp); + tt_bitset_page_or(it->page, it->page_tmp); } /* Init the bit iterator on it->page */ - bit_iterator_init(&it->page_it, bitset_page_data(it->page), + bit_iterator_init(&it->page_it, tt_bitset_page_data(it->page), BITSET_PAGE_DATA_SIZE, true); } static void -bitset_iterator_first_page(struct bitset_iterator *it) +tt_bitset_iterator_first_page(struct tt_bitset_iterator *it) { assert(it != NULL); /* Rewind all conjunctions to first positions */ for (size_t c = 0; c < it->size; c++) { - bitset_iterator_conj_rewind(&it->conjs[c], 0); + tt_bitset_iterator_conj_rewind(&it->conjs[c], 0); } /* Prepare the result page */ - bitset_iterator_prepare_page(it); + tt_bitset_iterator_prepare_page(it); } static void -bitset_iterator_next_page(struct bitset_iterator *it) +tt_bitset_iterator_next_page(struct tt_bitset_iterator *it) { assert(it != NULL); @@ -390,26 +397,26 @@ bitset_iterator_next_page(struct bitset_iterator *it) if (it->conjs[c].page_first_pos > pos) break; - bitset_iterator_conj_rewind(&it->conjs[c], pos + PAGE_BIT); + tt_bitset_iterator_conj_rewind(&it->conjs[c], pos + PAGE_BIT); assert(pos + PAGE_BIT <= it->conjs[c].page_first_pos); } /* Prepare the result page */ - bitset_iterator_prepare_page(it); + tt_bitset_iterator_prepare_page(it); } void -bitset_iterator_rewind(struct bitset_iterator *it) +tt_bitset_iterator_rewind(struct tt_bitset_iterator *it) { assert(it != NULL); /* Prepare first page */ - bitset_iterator_first_page(it); + tt_bitset_iterator_first_page(it); } size_t -bitset_iterator_next(struct bitset_iterator *it) +tt_bitset_iterator_next(struct tt_bitset_iterator *it) { assert(it != NULL); @@ -422,6 +429,6 @@ bitset_iterator_next(struct bitset_iterator *it) return it->page->first_pos + pos; } - bitset_iterator_next_page(it); + tt_bitset_iterator_next_page(it); } } diff --git a/src/lib/bitset/iterator.h b/src/lib/bitset/iterator.h index 2e4f37b..8337ebb 100644 --- a/src/lib/bitset/iterator.h +++ b/src/lib/bitset/iterator.h @@ -56,19 +56,19 @@ extern "C" { #endif /* defined(__cplusplus) */ /** @cond false **/ -struct bitset_iterator_conj; +struct tt_bitset_iterator_conj; /** @endcond **/ /** * @brief Bitset Iterator */ -struct bitset_iterator { +struct tt_bitset_iterator { /** @cond false **/ size_t size; size_t capacity; - struct bitset_iterator_conj *conjs; - struct bitset_page *page; - struct bitset_page *page_tmp; + struct tt_bitset_iterator_conj *conjs; + struct tt_bitset_page *page; + struct tt_bitset_page *page_tmp; void *(*realloc)(void *ptr, size_t size); struct bit_iterator page_it; /** @endcond **/ @@ -83,15 +83,15 @@ struct bitset_iterator { * @param realloc memory allocator to use */ void -bitset_iterator_create(struct bitset_iterator *it, - void *(*realloc)(void *ptr, size_t size)); +tt_bitset_iterator_create(struct tt_bitset_iterator *it, + void *(*realloc)(void *ptr, size_t size)); /** * @brief Destruct \a it. * @param it bitset iterator */ void -bitset_iterator_destroy(struct bitset_iterator *it); +tt_bitset_iterator_destroy(struct tt_bitset_iterator *it); /** * @brief Initialize the \a it using \a expr and \a bitsets and rewind the @@ -114,8 +114,9 @@ bitset_iterator_destroy(struct bitset_iterator *it); * @see expr.h */ int -bitset_iterator_init(struct bitset_iterator *it, struct bitset_expr *expr, - struct bitset **bitsets, size_t bitsets_size); +tt_bitset_iterator_init(struct tt_bitset_iterator *it, + struct tt_bitset_expr *expr, struct tt_bitset **bitsets, + size_t bitsets_size); /** * @brief Rewind the \a it to the start position. @@ -123,7 +124,7 @@ bitset_iterator_init(struct bitset_iterator *it, struct bitset_expr *expr, * @see @link bitset_iterator_init @endlink */ void -bitset_iterator_rewind(struct bitset_iterator *it); +tt_bitset_iterator_rewind(struct tt_bitset_iterator *it); /** * @brief Move \a it to a next position @@ -133,7 +134,7 @@ bitset_iterator_rewind(struct bitset_iterator *it); * @see @link bitset_iterator_init @endlink */ size_t -bitset_iterator_next(struct bitset_iterator *it); +tt_bitset_iterator_next(struct tt_bitset_iterator *it); #if defined(__cplusplus) } diff --git a/src/lib/bitset/page.c b/src/lib/bitset/page.c index ff42493..a0bf76f 100644 --- a/src/lib/bitset/page.c +++ b/src/lib/bitset/page.c @@ -33,38 +33,38 @@ #include "bitset/bitset.h" extern inline size_t -bitset_page_alloc_size(void *(*realloc_arg)(void *ptr, size_t size)); +tt_bitset_page_alloc_size(void *(*realloc_arg)(void *ptr, size_t size)); extern inline void * -bitset_page_data(struct bitset_page *page); +tt_bitset_page_data(struct tt_bitset_page *page); extern inline void -bitset_page_create(struct bitset_page *page); +tt_bitset_page_create(struct tt_bitset_page *page); extern inline void -bitset_page_destroy(struct bitset_page *page); +tt_bitset_page_destroy(struct tt_bitset_page *page); extern inline size_t -bitset_page_first_pos(size_t pos); +tt_bitset_page_first_pos(size_t pos); extern inline void -bitset_page_set_zeros(struct bitset_page *page); +tt_bitset_page_set_zeros(struct tt_bitset_page *page); extern inline void -bitset_page_set_ones(struct bitset_page *page); +tt_bitset_page_set_ones(struct tt_bitset_page *page); extern inline void -bitset_page_and(struct bitset_page *dst, struct bitset_page *src); +tt_bitset_page_and(struct tt_bitset_page *dst, struct tt_bitset_page *src); extern inline void -bitset_page_nand(struct bitset_page *dst, struct bitset_page *src); +tt_bitset_page_nand(struct tt_bitset_page *dst, struct tt_bitset_page *src); extern inline void -bitset_page_or(struct bitset_page *dst, struct bitset_page *src); +tt_bitset_page_or(struct tt_bitset_page *dst, struct tt_bitset_page *src); #if defined(DEBUG) void -bitset_page_dump(struct bitset_page *page, FILE *stream) +tt_bitset_page_dump(struct tt_bitset_page *page, FILE *stream) { fprintf(stream, "Page %zu:\n", page->first_pos); char *d = bitset_page_data(page); @@ -77,7 +77,7 @@ bitset_page_dump(struct bitset_page *page, FILE *stream) #endif /* defined(DEBUG) */ static inline int -page_cmp(const struct bitset_page *a, const struct bitset_page *b) +page_cmp(const struct tt_bitset_page *a, const struct tt_bitset_page *b) { if (a->first_pos < b->first_pos) { return -1; @@ -88,4 +88,5 @@ page_cmp(const struct bitset_page *a, const struct bitset_page *b) } } -rb_gen(, bitset_pages_, bitset_pages_t, struct bitset_page, node, page_cmp) +rb_gen(, tt_bitset_pages_, tt_bitset_pages_t, struct tt_bitset_page, node, + page_cmp) diff --git a/src/lib/bitset/page.h b/src/lib/bitset/page.h index b77e37f..aaeea51 100644 --- a/src/lib/bitset/page.h +++ b/src/lib/bitset/page.h @@ -43,7 +43,7 @@ #include #if defined(DEBUG) -#include /* for dumping bitset_page to file */ +#include /* for dumping tt_bitset_page to file */ #endif /* defined(DEBUG) */ #include #include @@ -59,17 +59,17 @@ enum { }; #if defined(ENABLE_AVX) -typedef __m256i bitset_word_t; +typedef __m256i tt_bitset_word_t; #define BITSET_PAGE_DATA_ALIGNMENT 32 #elif defined(ENABLE_SSE2) -typedef __m128i bitset_word_t; +typedef __m128i tt_bitset_word_t; #define BITSET_PAGE_DATA_ALIGNMENT 16 #elif defined(__x86_64__) -typedef uint64_t bitset_word_t; +typedef uint64_t tt_bitset_word_t; #define BITSET_PAGE_DATA_ALIGNMENT 1 #else #define BITSET_PAGE_DATA_ALIGNMENT 1 -typedef uint32_t bitset_word_t; +typedef uint32_t tt_bitset_word_t; #endif #if (defined(__GLIBC__) && (__WORDSIZE == 64) && \ @@ -89,98 +89,99 @@ typedef uint32_t bitset_word_t; #endif /* aligned malloc */ inline size_t -bitset_page_alloc_size(void *(*realloc_arg)(void *ptr, size_t size)) +tt_bitset_page_alloc_size(void *(*realloc_arg)(void *ptr, size_t size)) { if (BITSET_PAGE_DATA_ALIGNMENT <= 1 || ( (MALLOC_ALIGNMENT % BITSET_PAGE_DATA_ALIGNMENT == 0) && - (sizeof(struct bitset_page) % BITSET_PAGE_DATA_ALIGNMENT == 0) && + (sizeof(struct tt_bitset_page) % + BITSET_PAGE_DATA_ALIGNMENT == 0) && (realloc_arg == realloc))) { /* Alignment is not needed */ - return sizeof(struct bitset_page) + BITSET_PAGE_DATA_SIZE; + return sizeof(struct tt_bitset_page) + BITSET_PAGE_DATA_SIZE; } - return sizeof(struct bitset_page) + BITSET_PAGE_DATA_SIZE + + return sizeof(struct tt_bitset_page) + BITSET_PAGE_DATA_SIZE + BITSET_PAGE_DATA_ALIGNMENT; } #undef MALLOC_ALIGNMENT inline void * -bitset_page_data(struct bitset_page *page) +tt_bitset_page_data(struct tt_bitset_page *page) { uintptr_t r = (uintptr_t) (page->data + BITSET_PAGE_DATA_ALIGNMENT - 1); return (void *) (r & ~((uintptr_t) BITSET_PAGE_DATA_ALIGNMENT - 1)); } inline void -bitset_page_create(struct bitset_page *page) +tt_bitset_page_create(struct tt_bitset_page *page) { - size_t size = ((char *) bitset_page_data(page) - (char *) page) + size_t size = ((char *) tt_bitset_page_data(page) - (char *) page) + BITSET_PAGE_DATA_SIZE; memset(page, 0, size); } inline void -bitset_page_destroy(struct bitset_page *page) +tt_bitset_page_destroy(struct tt_bitset_page *page) { (void) page; /* nothing */ } inline size_t -bitset_page_first_pos(size_t pos) { +tt_bitset_page_first_pos(size_t pos) { return pos - (pos % (BITSET_PAGE_DATA_SIZE * CHAR_BIT)); } inline void -bitset_page_set_zeros(struct bitset_page *page) +tt_bitset_page_set_zeros(struct tt_bitset_page *page) { - void *data = bitset_page_data(page); + void *data = tt_bitset_page_data(page); memset(data, 0, BITSET_PAGE_DATA_SIZE); } inline void -bitset_page_set_ones(struct bitset_page *page) +tt_bitset_page_set_ones(struct tt_bitset_page *page) { - void *data = bitset_page_data(page); + void *data = tt_bitset_page_data(page); memset(data, -1, BITSET_PAGE_DATA_SIZE); } inline void -bitset_page_and(struct bitset_page *dst, struct bitset_page *src) +tt_bitset_page_and(struct tt_bitset_page *dst, struct tt_bitset_page *src) { - bitset_word_t *d = (bitset_word_t *) bitset_page_data(dst); - bitset_word_t *s = (bitset_word_t *) bitset_page_data(src); + tt_bitset_word_t *d = (tt_bitset_word_t *) tt_bitset_page_data(dst); + tt_bitset_word_t *s = (tt_bitset_word_t *) tt_bitset_page_data(src); - assert(BITSET_PAGE_DATA_SIZE % sizeof(bitset_word_t) == 0); - int cnt = BITSET_PAGE_DATA_SIZE / sizeof(bitset_word_t); + assert(BITSET_PAGE_DATA_SIZE % sizeof(tt_bitset_word_t) == 0); + int cnt = BITSET_PAGE_DATA_SIZE / sizeof(tt_bitset_word_t); for (int i = 0; i < cnt; i++) { *d++ &= *s++; } } inline void -bitset_page_nand(struct bitset_page *dst, struct bitset_page *src) +tt_bitset_page_nand(struct tt_bitset_page *dst, struct tt_bitset_page *src) { - bitset_word_t *d = (bitset_word_t *) bitset_page_data(dst); - bitset_word_t *s = (bitset_word_t *) bitset_page_data(src); + tt_bitset_word_t *d = (tt_bitset_word_t *) tt_bitset_page_data(dst); + tt_bitset_word_t *s = (tt_bitset_word_t *) tt_bitset_page_data(src); - assert(BITSET_PAGE_DATA_SIZE % sizeof(bitset_word_t) == 0); - int cnt = BITSET_PAGE_DATA_SIZE / sizeof(bitset_word_t); + assert(BITSET_PAGE_DATA_SIZE % sizeof(tt_bitset_word_t) == 0); + int cnt = BITSET_PAGE_DATA_SIZE / sizeof(tt_bitset_word_t); for (int i = 0; i < cnt; i++) { *d++ &= ~*s++; } } inline void -bitset_page_or(struct bitset_page *dst, struct bitset_page *src) +tt_bitset_page_or(struct tt_bitset_page *dst, struct tt_bitset_page *src) { - bitset_word_t *d = (bitset_word_t *) bitset_page_data(dst); - bitset_word_t *s = (bitset_word_t *) bitset_page_data(src); + tt_bitset_word_t *d = (tt_bitset_word_t *) tt_bitset_page_data(dst); + tt_bitset_word_t *s = (tt_bitset_word_t *) tt_bitset_page_data(src); - assert(BITSET_PAGE_DATA_SIZE % sizeof(bitset_word_t) == 0); - int cnt = BITSET_PAGE_DATA_SIZE / sizeof(bitset_word_t); + assert(BITSET_PAGE_DATA_SIZE % sizeof(tt_bitset_word_t) == 0); + int cnt = BITSET_PAGE_DATA_SIZE / sizeof(tt_bitset_word_t); for (int i = 0; i < cnt; i++) { *d++ |= *s++; } @@ -188,10 +189,10 @@ bitset_page_or(struct bitset_page *dst, struct bitset_page *src) #if defined(DEBUG) void -bitset_page_dump(struct bitset_page *page, FILE *stream); +tt_bitset_page_dump(struct tt_bitset_page *page, FILE *stream); #endif /* defined(DEBUG) */ -rb_proto(, bitset_pages_, bitset_pages_t, struct bitset_page) +rb_proto(, tt_bitset_pages_, tt_bitset_pages_t, struct tt_bitset_page) #if defined(__cplusplus) diff --git a/test/unit/bitset_basic.c b/test/unit/bitset_basic.c index cbbbce4..a2cbce4 100644 --- a/test/unit/bitset_basic.c +++ b/test/unit/bitset_basic.c @@ -11,43 +11,43 @@ void test_cardinality() { header(); - struct bitset bm; - bitset_create(&bm, realloc); + struct tt_bitset bm; + tt_bitset_create(&bm, realloc); - fail_unless(bitset_cardinality(&bm) == 0); + fail_unless(tt_bitset_cardinality(&bm) == 0); size_t cnt = 0; - fail_if(bitset_set(&bm, 10) < 0); + fail_if(tt_bitset_set(&bm, 10) < 0); cnt++; - fail_if(bitset_set(&bm, 15) < 0); + fail_if(tt_bitset_set(&bm, 15) < 0); cnt++; - fail_if(bitset_set(&bm, 20) < 0); + fail_if(tt_bitset_set(&bm, 20) < 0); cnt++; - fail_unless(bitset_cardinality(&bm) == cnt); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - fail_if(bitset_set(&bm, 10) < 0); - fail_unless(bitset_cardinality(&bm) == cnt); + fail_if(tt_bitset_set(&bm, 10) < 0); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - fail_if(bitset_clear(&bm, 20) < 0); + fail_if(tt_bitset_clear(&bm, 20) < 0); cnt--; - fail_unless(bitset_cardinality(&bm) == cnt); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - fail_if(bitset_clear(&bm, 20) < 0); - fail_unless(bitset_cardinality(&bm) == cnt); + fail_if(tt_bitset_clear(&bm, 20) < 0); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - fail_if(bitset_clear(&bm, 666) < 0); - fail_unless(bitset_cardinality(&bm) == cnt); + fail_if(tt_bitset_clear(&bm, 666) < 0); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - fail_if(bitset_clear(&bm, 10) < 0); + fail_if(tt_bitset_clear(&bm, 10) < 0); cnt--; - fail_unless(bitset_cardinality(&bm) == cnt); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - fail_if(bitset_clear(&bm, 15) < 0); + fail_if(tt_bitset_clear(&bm, 15) < 0); cnt--; - fail_unless(bitset_cardinality(&bm) == cnt); + fail_unless(tt_bitset_cardinality(&bm) == cnt); - bitset_destroy(&bm); + tt_bitset_destroy(&bm); footer(); } @@ -87,8 +87,8 @@ void test_get_set() { header(); - struct bitset bm; - bitset_create(&bm, realloc); + struct tt_bitset bm; + tt_bitset_create(&bm, realloc); const size_t NUM_SIZE = (size_t) 1 << 14; size_t *nums = malloc(NUM_SIZE * sizeof(size_t)); @@ -114,7 +114,7 @@ void test_get_set() for(size_t i = 0; i < NUM_SIZE; i++) { if (nums[i] == SIZE_MAX) continue; - fail_if(bitset_set(&bm, nums[i]) < 0); + fail_if(tt_bitset_set(&bm, nums[i]) < 0); } printf("ok\n"); @@ -123,7 +123,7 @@ void test_get_set() for(size_t i = 0; i < NUM_SIZE; i++) { if (nums[i] == SIZE_MAX) continue; - fail_unless(bitset_test(&bm, nums[i])); + fail_unless(tt_bitset_test(&bm, nums[i])); } printf("ok\n"); @@ -132,8 +132,8 @@ void test_get_set() size_t i = rand() % NUM_SIZE; if (nums[i] == SIZE_MAX) continue; - fail_if(bitset_clear(&bm, nums[i]) < 0); - fail_if(bitset_test(&bm, nums[i])); + fail_if(tt_bitset_clear(&bm, nums[i]) < 0); + fail_if(tt_bitset_test(&bm, nums[i])); nums[i] = SIZE_MAX; } printf("ok\n"); @@ -145,10 +145,10 @@ void test_get_set() continue; } - if (!bitset_test(&bm, nums[i])) { + if (!tt_bitset_test(&bm, nums[i])) { printf("Fail :%zu\n", nums[i]); } - fail_unless(bitset_test(&bm, nums[i])); + fail_unless(tt_bitset_test(&bm, nums[i])); } printf("ok\n"); @@ -161,10 +161,10 @@ void test_get_set() for(size_t i = 0; i < i_max; i++) { if (*pn < SIZE_MAX && *pn == i) { - fail_unless(bitset_test(&bm, *pn)); + fail_unless(tt_bitset_test(&bm, *pn)); pn++; } else { - fail_if(bitset_test(&bm, i)); + fail_if(tt_bitset_test(&bm, i)); } } printf("ok\n"); @@ -177,20 +177,20 @@ void test_get_set() continue; } - fail_if(bitset_clear(&bm, nums[i]) < 0); + fail_if(tt_bitset_clear(&bm, nums[i]) < 0); } printf("ok\n"); printf("Checking all bits... "); for(size_t i = 0; i < i_max; i++) { - fail_if(bitset_test(&bm, i)); + fail_if(tt_bitset_test(&bm, i)); } printf("ok\n"); free(nums); - bitset_destroy(&bm); + tt_bitset_destroy(&bm); footer(); } diff --git a/test/unit/bitset_index.c b/test/unit/bitset_index.c index 736c897..8343317 100644 --- a/test/unit/bitset_index.c +++ b/test/unit/bitset_index.c @@ -14,27 +14,27 @@ void test_resize(void) { header(); - struct bitset_index index; - bitset_index_create(&index, realloc); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_index index; + tt_bitset_index_create(&index, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); size_t key = 23411111; size_t value = 2321321; - bitset_index_insert(&index, &key, sizeof(key), value); + tt_bitset_index_insert(&index, &key, sizeof(key), value); - fail_unless(bitset_index_expr_equals(&expr, &key, sizeof(key)) == 0); + fail_unless(tt_bitset_index_expr_equals(&expr, &key, sizeof(key)) == 0); - fail_unless(bitset_index_init_iterator(&index, &it, &expr) == 0); - fail_unless(bitset_iterator_next(&it) == value); - fail_unless(bitset_iterator_next(&it) == SIZE_MAX); + fail_unless(tt_bitset_index_init_iterator(&index, &it, &expr) == 0); + fail_unless(tt_bitset_iterator_next(&it) == value); + fail_unless(tt_bitset_iterator_next(&it) == SIZE_MAX); - bitset_expr_destroy(&expr); - bitset_iterator_destroy(&it); - bitset_index_destroy(&index); + tt_bitset_expr_destroy(&expr); + tt_bitset_iterator_destroy(&it); + tt_bitset_index_destroy(&index); footer(); } @@ -44,35 +44,35 @@ void test_size_and_count(void) { header(); - struct bitset_index index; - bitset_index_create(&index, realloc); + struct tt_bitset_index index; + tt_bitset_index_create(&index, realloc); enum { P = 10, SIZE = (1 << P) + 1 }; for(size_t i = 0; i < SIZE; i++) { - bitset_index_insert(&index, &i, sizeof(i), i); + tt_bitset_index_insert(&index, &i, sizeof(i), i); } - fail_unless(bitset_index_size(&index) == SIZE); - fail_unless(bitset_index_count(&index, 0) == SIZE / 2); - fail_unless(bitset_index_count(&index, 1) == SIZE / 2); - fail_unless(bitset_index_count(&index, 4) == SIZE / 2); - fail_unless(bitset_index_count(&index, P) == 1); - fail_unless(bitset_index_count(&index, P + 1) == 0); - fail_unless(bitset_index_count(&index, 2147483648) == 0); + fail_unless(tt_bitset_index_size(&index) == SIZE); + fail_unless(tt_bitset_index_count(&index, 0) == SIZE / 2); + fail_unless(tt_bitset_index_count(&index, 1) == SIZE / 2); + fail_unless(tt_bitset_index_count(&index, 4) == SIZE / 2); + fail_unless(tt_bitset_index_count(&index, P) == 1); + fail_unless(tt_bitset_index_count(&index, P + 1) == 0); + fail_unless(tt_bitset_index_count(&index, 2147483648) == 0); - bitset_index_destroy(&index); + tt_bitset_index_destroy(&index); footer(); } static -void check_keys(struct bitset_index *index, +void check_keys(struct tt_bitset_index *index, size_t *keys, size_t *values, size_t size) { - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); printf("Checking keys... "); for (size_t i = 0; i < size; i++) { @@ -81,15 +81,16 @@ void check_keys(struct bitset_index *index, continue; } - fail_unless(bitset_index_expr_equals(&expr, &keys[i], - sizeof(keys[i])) == 0); + fail_unless(tt_bitset_index_expr_equals(&expr, &keys[i], + sizeof(keys[i])) == 0); - fail_unless(bitset_index_init_iterator(index, &it, &expr) == 0); + fail_unless( + tt_bitset_index_init_iterator(index, &it, &expr) == 0); size_t pos; bool pair_found = false; - while ( (pos = bitset_iterator_next(&it)) != SIZE_MAX) { + while ( (pos = tt_bitset_iterator_next(&it)) != SIZE_MAX) { if (pos == values[i]) { pair_found = true; break; @@ -99,8 +100,8 @@ void check_keys(struct bitset_index *index, } printf("ok\n"); - bitset_iterator_destroy(&it); - bitset_expr_destroy(&expr); + tt_bitset_iterator_destroy(&it); + tt_bitset_expr_destroy(&expr); } static @@ -108,8 +109,8 @@ void test_insert_remove(void) { header(); - struct bitset_index index; - bitset_index_create(&index, realloc); + struct tt_bitset_index index; + tt_bitset_index_create(&index, realloc); size_t NUMS_SIZE = 1 << 11; size_t *keys = malloc(NUMS_SIZE * sizeof(size_t)); @@ -128,21 +129,21 @@ void test_insert_remove(void) printf("Inserting pairs... "); for(size_t i = 0; i < NUMS_SIZE; i++) { - bitset_index_insert(&index, &keys[i], sizeof(keys[i]), - values[i]); + tt_bitset_index_insert(&index, &keys[i], sizeof(keys[i]), + values[i]); } printf("ok\n"); check_keys(&index, keys, values, NUMS_SIZE); - fail_unless(bitset_index_count(&index, 0) == count0); - fail_unless(bitset_index_count(&index, 1) == count1); + fail_unless(tt_bitset_index_count(&index, 0) == count0); + fail_unless(tt_bitset_index_count(&index, 1) == count1); printf("Removing random pairs... "); for(size_t i = 0; i < NUMS_SIZE; i++) { if (rand() % 5 == 0) { - bitset_index_remove_value(&index, values[i]); + tt_bitset_index_remove_value(&index, values[i]); keys[i] = SIZE_MAX; } } @@ -150,7 +151,7 @@ void test_insert_remove(void) check_keys(&index, keys, values, NUMS_SIZE); - bitset_index_destroy(&index); + tt_bitset_index_destroy(&index); free(keys); free(values); @@ -164,16 +165,16 @@ void test_simple(int mode, size_t search_mask) { fail_unless(mode >= 0 && mode < 3); - struct bitset_index index; - bitset_index_create(&index, realloc); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_index index; + tt_bitset_index_create(&index, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); size_t check_count = 0; for (size_t key = 0; key < NUMS_SIZE; key++) { - bitset_index_insert(&index, &key, sizeof(key), key); + tt_bitset_index_insert(&index, &key, sizeof(key), key); if (mode == 0) { check_count++; } else if (mode == 1 && (key & search_mask) == search_mask) { @@ -184,19 +185,23 @@ void test_simple(int mode, size_t search_mask) } if (mode == 0) { - fail_unless(bitset_index_expr_all(&expr) == 0); + fail_unless(tt_bitset_index_expr_all(&expr) == 0); } else if (mode == 1) { - fail_unless(bitset_index_expr_all_set(&expr, - &search_mask, sizeof(search_mask)) == 0); + fail_unless(tt_bitset_index_expr_all_set(&expr, + &search_mask, + sizeof(search_mask)) == + 0); } else if (mode == 2) { - fail_unless(bitset_index_expr_any_set(&expr, - &search_mask, sizeof(search_mask)) == 0); + fail_unless(tt_bitset_index_expr_any_set(&expr, + &search_mask, + sizeof(search_mask)) == + 0); } - fail_unless(bitset_index_init_iterator(&index, &it, &expr) == 0); + fail_unless(tt_bitset_index_init_iterator(&index, &it, &expr) == 0); size_t found_count = 0; for (size_t key = 0; key < NUMS_SIZE; key++) { - size_t r = bitset_iterator_next(&it); + size_t r = tt_bitset_iterator_next(&it); if (mode == 0) { fail_unless(key == r); found_count++; @@ -206,12 +211,12 @@ void test_simple(int mode, size_t search_mask) found_count++; } } - fail_unless(bitset_iterator_next(&it) == SIZE_MAX); + fail_unless(tt_bitset_iterator_next(&it) == SIZE_MAX); fail_unless(found_count == check_count); - bitset_expr_destroy(&expr); - bitset_iterator_destroy(&it); - bitset_index_destroy(&index); + tt_bitset_expr_destroy(&expr); + tt_bitset_iterator_destroy(&it); + tt_bitset_index_destroy(&index); } static void @@ -253,32 +258,33 @@ void test_equals_simple(void) { header(); - struct bitset_index index; - bitset_index_create(&index, realloc); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_index index; + tt_bitset_index_create(&index, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); size_t mask = ~((size_t ) 7); for (size_t i = 0; i < NUMS_SIZE; i++) { size_t key = i & mask; size_t value = i; - bitset_index_insert(&index, &key, sizeof(key), value); + tt_bitset_index_insert(&index, &key, sizeof(key), value); } size_t key1 = (rand() % NUMS_SIZE) & mask; - fail_unless(bitset_index_expr_equals(&expr, &key1, sizeof(key1)) == 0); - fail_unless(bitset_index_init_iterator(&index, &it, &expr) == 0); + fail_unless(tt_bitset_index_expr_equals(&expr, &key1, + sizeof(key1)) == 0); + fail_unless(tt_bitset_index_init_iterator(&index, &it, &expr) == 0); for (size_t i = key1; i <= (key1 + ~mask); i++) { - fail_unless(i == bitset_iterator_next(&it)); + fail_unless(i == tt_bitset_iterator_next(&it)); } - fail_unless(bitset_iterator_next(&it) == SIZE_MAX); + fail_unless(tt_bitset_iterator_next(&it) == SIZE_MAX); - bitset_expr_destroy(&expr); - bitset_iterator_destroy(&it); - bitset_index_destroy(&index); + tt_bitset_expr_destroy(&expr); + tt_bitset_iterator_destroy(&it); + tt_bitset_index_destroy(&index); footer(); } diff --git a/test/unit/bitset_iterator.c b/test/unit/bitset_iterator.c index 5954570..3830fff 100644 --- a/test/unit/bitset_iterator.c +++ b/test/unit/bitset_iterator.c @@ -10,25 +10,25 @@ enum { NUMS_SIZE = 1 << 16 }; static size_t NUMS[NUMS_SIZE]; -static struct bitset ** +static struct tt_bitset ** bitsets_create(size_t count) { - struct bitset **bitsets = malloc(count * sizeof(*bitsets)); + struct tt_bitset **bitsets = malloc(count * sizeof(*bitsets)); fail_if(bitsets == NULL); for (size_t i = 0; i < count; i++) { - bitsets[i] = malloc(sizeof(struct bitset)); + bitsets[i] = malloc(sizeof(struct tt_bitset)); fail_if(bitsets[i] == NULL); - bitset_create(bitsets[i], realloc); + tt_bitset_create(bitsets[i], realloc); } return bitsets; } static void -bitsets_destroy(struct bitset **bitsets, size_t count) +bitsets_destroy(struct tt_bitset **bitsets, size_t count) { for (size_t i = 0; i < count; i++) { - bitset_destroy(bitsets[i]); + tt_bitset_destroy(bitsets[i]); free(bitsets[i]); } @@ -82,18 +82,18 @@ void test_empty_expr(void) { header(); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, NULL, 0) == 0); - bitset_expr_destroy(&expr); + fail_unless(tt_bitset_iterator_init(&it, &expr, NULL, 0) == 0); + tt_bitset_expr_destroy(&expr); - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless(pos == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); footer(); } @@ -103,20 +103,20 @@ void test_empty_expr_conj1(void) { header(); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_iterator_init(&it, &expr, NULL, 0) == 0); - bitset_expr_destroy(&expr); + fail_unless(tt_bitset_iterator_init(&it, &expr, NULL, 0) == 0); + tt_bitset_expr_destroy(&expr); - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless(pos == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); footer(); } @@ -127,32 +127,32 @@ void test_empty_expr_conj2(void) header(); size_t big_i = (size_t) 1 << 15; - struct bitset **bitsets = bitsets_create(2); - bitset_set(bitsets[0], 1); - bitset_set(bitsets[0], big_i); + struct tt_bitset **bitsets = bitsets_create(2); + tt_bitset_set(bitsets[0], 1); + tt_bitset_set(bitsets[0], big_i); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_param(&expr, 0, false) == 0); - fail_unless(bitset_expr_add_param(&expr, 1, true) == 0); - fail_unless(bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 0, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 1, true) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, 2) == 0); - bitset_expr_destroy(&expr); + fail_unless(tt_bitset_iterator_init(&it, &expr, bitsets, 2) == 0); + tt_bitset_expr_destroy(&expr); - fail_unless(bitset_iterator_next(&it) == 1); - fail_unless(bitset_iterator_next(&it) == big_i); - fail_unless(bitset_iterator_next(&it) == SIZE_MAX); + fail_unless(tt_bitset_iterator_next(&it) == 1); + fail_unless(tt_bitset_iterator_next(&it) == big_i); + fail_unless(tt_bitset_iterator_next(&it) == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, 2); footer(); @@ -163,40 +163,40 @@ void test_empty_result(void) { header(); - struct bitset **bitsets = bitsets_create(2); + struct tt_bitset **bitsets = bitsets_create(2); - bitset_set(bitsets[0], 1); - bitset_set(bitsets[0], 2); - bitset_set(bitsets[0], 3); - bitset_set(bitsets[0], 193); - bitset_set(bitsets[0], 1024); + tt_bitset_set(bitsets[0], 1); + tt_bitset_set(bitsets[0], 2); + tt_bitset_set(bitsets[0], 3); + tt_bitset_set(bitsets[0], 193); + tt_bitset_set(bitsets[0], 1024); - bitset_set(bitsets[0], 1025); - bitset_set(bitsets[0], 16384); - bitset_set(bitsets[0], 16385); + tt_bitset_set(bitsets[0], 1025); + tt_bitset_set(bitsets[0], 16384); + tt_bitset_set(bitsets[0], 16385); - bitset_set(bitsets[1], 17); - bitset_set(bitsets[1], 194); - bitset_set(bitsets[1], 1023); + tt_bitset_set(bitsets[1], 17); + tt_bitset_set(bitsets[1], 194); + tt_bitset_set(bitsets[1], 1023); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_param(&expr, 0, false) == 0); - fail_unless(bitset_expr_add_param(&expr, 1, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 0, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 1, false) == 0); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, 2) == 0); - bitset_expr_destroy(&expr); + fail_unless(tt_bitset_iterator_init(&it, &expr, bitsets, 2) == 0); + tt_bitset_expr_destroy(&expr); - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless(pos == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, 2); @@ -208,33 +208,33 @@ void test_first_result(void) { header(); - struct bitset **bitsets = bitsets_create(2); + struct tt_bitset **bitsets = bitsets_create(2); - bitset_set(bitsets[0], 0); - bitset_set(bitsets[0], 1023); + tt_bitset_set(bitsets[0], 0); + tt_bitset_set(bitsets[0], 1023); - bitset_set(bitsets[1], 0); - bitset_set(bitsets[1], 1025); + tt_bitset_set(bitsets[1], 0); + tt_bitset_set(bitsets[1], 1025); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_param(&expr, 0, false) == 0); - fail_unless(bitset_expr_add_param(&expr, 1, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 0, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 1, false) == 0); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, 2) == 0); - bitset_expr_destroy(&expr); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + fail_unless(tt_bitset_iterator_init(&it, &expr, bitsets, 2) == 0); + tt_bitset_expr_destroy(&expr); - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless(pos == 0); - fail_unless(bitset_iterator_next(&it) == SIZE_MAX); + fail_unless(tt_bitset_iterator_next(&it) == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, 2); @@ -248,42 +248,43 @@ void test_simple() enum { BITSETS_SIZE = 32 }; - struct bitset **bitsets = bitsets_create(BITSETS_SIZE); + struct tt_bitset **bitsets = bitsets_create(BITSETS_SIZE); nums_shuffle(NUMS, NUMS_SIZE); size_t NOISE_SIZE = NUMS_SIZE / 3; for (size_t i = 0; i < NOISE_SIZE; i++) { - bitset_set(bitsets[i % BITSETS_SIZE], NUMS[i]); + tt_bitset_set(bitsets[i % BITSETS_SIZE], NUMS[i]); } for (size_t i = NOISE_SIZE; i < NUMS_SIZE; i++) { for (size_t b = 0; b < BITSETS_SIZE; b++) { - bitset_set(bitsets[b], NUMS[i]); + tt_bitset_set(bitsets[b], NUMS[i]); } } - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); for (size_t b = 0; b < BITSETS_SIZE; b++) { - fail_unless(bitset_expr_add_param(&expr, b, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, b, false) == 0); } nums_sort(NUMS + NOISE_SIZE, NUMS_SIZE - NOISE_SIZE); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); - bitset_expr_destroy(&expr); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + fail_unless( + tt_bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); + tt_bitset_expr_destroy(&expr); for (size_t i = NOISE_SIZE; i < NUMS_SIZE; i++) { - fail_unless(bitset_iterator_next(&it) == NUMS[i]); + fail_unless(tt_bitset_iterator_next(&it) == NUMS[i]); } - fail_unless(bitset_iterator_next(&it) == SIZE_MAX); + fail_unless(tt_bitset_iterator_next(&it) == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, BITSETS_SIZE); footer(); @@ -294,38 +295,39 @@ void test_big() { header(); const size_t BITSETS_SIZE = 32; - struct bitset **bitsets = bitsets_create(BITSETS_SIZE); + struct tt_bitset **bitsets = bitsets_create(BITSETS_SIZE); nums_shuffle(NUMS, NUMS_SIZE); printf("Setting bits... "); for (size_t i = 0; i < NUMS_SIZE; i++) { for (size_t b = 0; b < BITSETS_SIZE; b++) { - bitset_set(bitsets[b], NUMS[i]); + tt_bitset_set(bitsets[b], NUMS[i]); if (b % 2 == 0 && i % 2 == 0) continue; } } printf("ok\n"); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); for(size_t b = 0; b < BITSETS_SIZE; b++) { - fail_unless(bitset_expr_add_param(&expr, b, false) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, b, false) == 0); } - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); - bitset_expr_destroy(&expr); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + fail_unless( + tt_bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); + tt_bitset_expr_destroy(&expr); printf("Iterating... "); size_t pos; - while ((pos = bitset_iterator_next(&it)) != SIZE_MAX) { + while ((pos = tt_bitset_iterator_next(&it)) != SIZE_MAX) { size_t b; for(b = 0; b < BITSETS_SIZE; b++) { - if(bitset_test(bitsets[b], pos)) + if(tt_bitset_test(bitsets[b], pos)) continue; } @@ -333,7 +335,7 @@ void test_big() { } printf("ok\n"); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, BITSETS_SIZE); @@ -344,43 +346,43 @@ static void test_not_last() { header(); - struct bitset **bitsets = bitsets_create(2); + struct tt_bitset **bitsets = bitsets_create(2); size_t big_i = (size_t) 1 << 15; - bitset_set(bitsets[0], 0); - bitset_set(bitsets[0], 11); - bitset_set(bitsets[0], 1024); + tt_bitset_set(bitsets[0], 0); + tt_bitset_set(bitsets[0], 11); + tt_bitset_set(bitsets[0], 1024); - bitset_set(bitsets[1], 0); - bitset_set(bitsets[1], 10); - bitset_set(bitsets[1], 11); - bitset_set(bitsets[1], 14); - bitset_set(bitsets[1], big_i); + tt_bitset_set(bitsets[1], 0); + tt_bitset_set(bitsets[1], 10); + tt_bitset_set(bitsets[1], 11); + tt_bitset_set(bitsets[1], 14); + tt_bitset_set(bitsets[1], big_i); - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); - fail_unless(bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_param(&expr, 0, true) == 0); - fail_unless(bitset_expr_add_param(&expr, 1, false) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 0, true) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, 1, false) == 0); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, 2) == 0); - bitset_expr_destroy(&expr); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + fail_unless(tt_bitset_iterator_init(&it, &expr, bitsets, 2) == 0); + tt_bitset_expr_destroy(&expr); size_t result[] = {10, 14, big_i}; size_t result_size = 3; size_t pos; for (size_t i = 0; i < result_size; i++) { - pos = bitset_iterator_next(&it); + pos = tt_bitset_iterator_next(&it); fail_unless (result[i] == pos); } - fail_unless ((pos = bitset_iterator_next(&it)) == SIZE_MAX); + fail_unless ((pos = tt_bitset_iterator_next(&it)) == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, 2); @@ -396,33 +398,34 @@ void test_not_empty() { CHECK_COUNT = (size_t) 1 << 14 }; - struct bitset **bitsets = bitsets_create(BITSETS_SIZE); + struct tt_bitset **bitsets = bitsets_create(BITSETS_SIZE); nums_shuffle(NUMS, NUMS_SIZE); for (size_t i = 0; i < NUMS_SIZE; i++) { - bitset_set(bitsets[i % BITSETS_SIZE], NUMS[i]); + tt_bitset_set(bitsets[i % BITSETS_SIZE], NUMS[i]); } - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); for(size_t b = 0; b < BITSETS_SIZE; b++) { - fail_unless(bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_param(&expr, b, true) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, b, true) == 0); } - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); - bitset_expr_destroy(&expr); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + fail_unless( + tt_bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); + tt_bitset_expr_destroy(&expr); for (size_t i = 0; i < CHECK_COUNT; i++) { - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless (i == pos); } - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, BITSETS_SIZE); @@ -436,38 +439,39 @@ void test_disjunction() enum { BITSETS_SIZE = 32 }; - struct bitset **bitsets = bitsets_create(BITSETS_SIZE); + struct tt_bitset **bitsets = bitsets_create(BITSETS_SIZE); nums_shuffle(NUMS, NUMS_SIZE); for (size_t i = 0; i < NUMS_SIZE; i++) { - bitset_set(bitsets[i % BITSETS_SIZE], NUMS[i]); + tt_bitset_set(bitsets[i % BITSETS_SIZE], NUMS[i]); } - struct bitset_expr expr; - bitset_expr_create(&expr, realloc); + struct tt_bitset_expr expr; + tt_bitset_expr_create(&expr, realloc); for (size_t b = 0; b < BITSETS_SIZE; b++) { - fail_unless(bitset_expr_add_conj(&expr) == 0); - fail_unless(bitset_expr_add_param(&expr, b, false) == 0); + fail_unless(tt_bitset_expr_add_conj(&expr) == 0); + fail_unless(tt_bitset_expr_add_param(&expr, b, false) == 0); } nums_sort(NUMS, NUMS_SIZE); - struct bitset_iterator it; - bitset_iterator_create(&it, realloc); - fail_unless(bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); - bitset_expr_destroy(&expr); + struct tt_bitset_iterator it; + tt_bitset_iterator_create(&it, realloc); + fail_unless( + tt_bitset_iterator_init(&it, &expr, bitsets, BITSETS_SIZE) == 0); + tt_bitset_expr_destroy(&expr); for (size_t i = 0; i < NUMS_SIZE; i++) { - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless(pos == NUMS[i]); } - size_t pos = bitset_iterator_next(&it); + size_t pos = tt_bitset_iterator_next(&it); fail_unless(pos == SIZE_MAX); - bitset_iterator_destroy(&it); + tt_bitset_iterator_destroy(&it); bitsets_destroy(bitsets, BITSETS_SIZE); -- 2.7.4