<commit_before>#include "extendibleHashing.h"

Hash* createHash() {
	Hash *hash = malloc(sizeof(Hash));
	ALLOCATION_ERROR(hash);
	hash->global_depth = GLOBAL_DEPTH_INIT;
	hash->size = 1 << GLOBAL_DEPTH_INIT;
	hash->index = malloc(hash->size * sizeof(Bucket *));
	ALLOCATION_ERROR(hash->index);
	uint64_t i;
	for (i = 0 ; i < hash->size ; i++)
		hash->index[i] = createNewBucket(GLOBAL_DEPTH_INIT, B);
	return hash;
}

int insertHashRecord(Hash* hash, Key key, RangeArray* rangeArray) {
	uint64_t bucket_num = hashFunction(hash->size, key);
	Bucket *bucket = hash->index[bucket_num];
	uint32_t i;
	for (i = 0 ; i < bucket->current_subBuckets; i++) {			/* for all subbuckets */
		if (bucket->key_buckets[i].key == key) {				/* if there is a subBucket with this key */
			uint64_t current_entries = bucket->key_buckets[i].current_entries;
			if (current_entries == bucket->key_buckets[i].limit) { 	/* if there isn't enough free space, realloc */
				bucket->key_buckets[i].transaction_range = realloc(bucket->key_buckets[i].transaction_range, ((bucket->key_buckets[i].current_entries)+C) * sizeof(RangeArray));
				ALLOCATION_ERROR(bucket->key_buckets[i].transaction_range);
				bucket->key_buckets[i].limit += C;
			}
			/* Insert entry */
			bucket->key_buckets[i].transaction_range[current_entries].transaction_id = rangeArray->transaction_id;
			bucket->key_buckets[i].transaction_range[current_entries].rec_offset = rangeArray->rec_offset;
			(bucket->key_buckets[i].current_entries)++;
			return OK_SUCCESS;
		}
	}
	/* If that was the first appearence of this key */
	if (bucket->current_subBuckets < B) {	/* If there is space to insert it on that bucket (there is a free subbucket) */
		bucket->key_buckets[bucket->current_subBuckets].key = key;
		bucket->key_buckets[bucket->current_subBuckets].transaction_range[0].transaction_id = rangeArray->transaction_id;
		bucket->key_buckets[bucket->current_subBuckets].transaction_range[0].rec_offset = rangeArray->rec_offset;
		bucket->key_buckets[bucket->current_subBuckets].current_entries += 1;
		(bucket->current_subBuckets)++;
		return OK_SUCCESS;
	} else {	/* if there is no space for a new key in this bucket */
		/* Doublicate index */
		if (bucket->local_depth >= hash->global_depth) { // one pointer per bucket -> doublicate index
			duplicateIndex(hash);	/* doublicates and increases global depth */
			bucket->local_depth++;
			Bucket *new_bucket = createNewBucket(bucket->local_depth, B);
			Bucket *tmp_bucket = createNewBucket(bucket->local_depth, B);
			copyBucketTransactions(tmp_bucket, bucket);
			cleanBucket(bucket);
			fixHashPointers(hash->index, new_bucket, hash->global_depth, bucket_num);
			uint32_t i;
			uint64_t new_hash, j;
			for (i = 0 ; i < B ; i++) {	/* for all subBuckets in tmpBucket */
				new_hash = hashFunction(1 << hash->global_depth, tmp_bucket->key_buckets[i].key); /* new_hash has a bucket number */
				if (new_hash == bucket_num) {	/* if the new bucket is the previous one and there is available subBucket space */
					uint32_t current_subBuckets = hash->index[new_hash]->current_subBuckets;
					hash->index[new_hash]->key_buckets[current_subBuckets].key = tmp_bucket->key_buckets[i].key;
					hash->index[new_hash]->key_buckets[current_subBuckets].current_entries = tmp_bucket->key_buckets[i].current_entries;
					uint64_t current_entries = hash->index[new_hash]->key_buckets[current_subBuckets].current_entries;
					for (j = 0 ; j < current_entries ; j++) {	/* for j in transactionRange of the bucket to be copied */
						hash->index[new_hash]->key_buckets[current_subBuckets].transaction_range[j].transaction_id = tmp_bucket->key_buckets[i].transaction_range[j].transaction_id;
						hash->index[new_hash]->key_buckets[current_subBuckets].transaction_range[j].rec_offset = tmp_bucket->key_buckets[i].transaction_range[j].rec_offset;
					}
					hash->index[new_hash]->current_subBuckets++;
				} else if (new_hash != bucket_num) {
					uint32_t current_subBuckets = new_bucket->current_subBuckets;
					new_bucket->key_buckets[current_subBuckets].key = tmp_bucket->key_buckets[i].key;
					new_bucket->key_buckets[current_subBuckets].current_entries = tmp_bucket->key_buckets[i].current_entries;
					uint64_t current_entries = new_bucket->key_buckets[current_subBuckets].current_entries;
					for(j = 0 ; j < current_entries ; j++ ) {
						new_bucket->key_buckets[current_subBuckets].transaction_range[j].transaction_id = tmp_bucket->key_buckets[i].transaction_range[j].transaction_id;
						new_bucket->key_buckets[current_subBuckets].transaction_range[j].rec_offset = tmp_bucket->key_buckets[i].transaction_range[j].rec_offset;
					}
					new_bucket->current_subBuckets++;
				}
			}
			destroyBucket(tmp_bucket, B);
			insertHashRecord(hash, key, rangeArray);
		} 
		/* split bucket */
		else if (bucket->local_depth < hash->global_depth) { 
			bucket->local_depth++;
			Bucket *new_bucket = createNewBucket(bucket->local_depth, B);
			Bucket *tmp_bucket = createNewBucket(bucket->local_depth, B);
			copyBucketTransactions(tmp_bucket, bucket);
			cleanBucket(bucket);
			uint32_t i;
			uint64_t new_hash, j;
			// Boolean_t all_in_old = True;
			// Boolean_t all_in_new = True;
			fixSplitPointers(hash, bucket, new_bucket, bucket_num);

			for (i = 0 ; i < B ; i++) {	/* for all subBuckets in tmpBucket */
				SubBucket *subbuckets = tmp_bucket->key_buckets;
				Key key = subbuckets[i].key;
				new_hash = hashFunction(hash->size, key);
				// fprintf(stderr, "New hash for %zu is %zu\n",key,new_hash );
				Bucket* destination = hash->index[new_hash];
				uint32_t current_subBuckets = destination->current_subBuckets;
				copySubbucketTransactions(&destination->key_buckets[current_subBuckets], &subbuckets[i]);
				destination->current_subBuckets++;
			}

			destroyBucket(tmp_bucket, B);
			insertHashRecord(hash, key, rangeArray);
		}
	}
	return OK_SUCCESS;
}  

/*Does whatever it says*/
void duplicateIndex(Hash * hash) {
	hash->global_depth++;
	uint64_t old_size = hash->size;
	hash->size *= 2;
	hash->index = realloc(hash->index, hash->size * sizeof(Bucket *));
	ALLOCATION_ERROR(hash->index);
	uint64_t i;
	for (i = old_size; i < hash->size; i++)
		hash->index[i] = NULL;
}

void destroyBucket(Bucket *bucket,uint32_t b) {
	uint32_t i;
	for (i = 0 ; i < b ; i++) { /*for each subBucket*/
		free(bucket->key_buckets[i].transaction_range);
	}
	free(bucket->key_buckets);
	free(bucket);
	bucket = NULL;
}

/* fix new indexes pointers after index doublicate */
void fixHashPointers(Bucket **index, Bucket *new_bucket, uint32_t global_depth, uint64_t bucket_num) {
	uint64_t i, j;
	uint64_t old_size = 1 << (global_depth-1);
	// fprintf(stderr, "-----------------------------------------------------\n");
	for (i = 0, j = old_size ; i < old_size ; i++, j++) {
		if (i == bucket_num) {
			// fprintf(stderr, "index[%zu] = new_bucket\n",j);
			index[j] = new_bucket;
		} else {
			// fprintf(stderr, "index[%zu] = index[%zu]\n",j,i );
			index[j] = index[i];
		}
	}
	// fprintf(stderr, "-----------------------------------------------------\n");
}

/* fix new indexes pointers after index splits */
void fixSplitPointers(Hash* hash, Bucket* old_bucket, Bucket* new_bucket, uint64_t bucket_num){
	uint64_t prev_local_depth = old_bucket->local_depth-1;
	uint64_t i;
	uint64_t ld_size = 1 << prev_local_depth;
	uint32_t first_pointer = bucket_num % ld_size;
	for (i = first_pointer ; i < hash->size ; i+=(2*ld_size)) { /* i in all old_bucket pointers */
		hash->index[i] = old_bucket;
		hash->index[i+ld_size] = new_bucket;
	}
}

/* copy transactions from one Bucket to another one*/
void copyBucketTransactions(Bucket* dst, Bucket* src) {
	uint64_t i;
	uint64_t j;
	dst->local_depth = src->local_depth;
	dst->current_subBuckets = src->current_subBuckets;

	for (i = 0 ; i < src->current_subBuckets ; i++) {	/* for i in subBuckets */
		copySubbucketTransactions(&dst->key_buckets[i], &src->key_buckets[i]);
		// dst->key_buckets[i].key = src->key_buckets[i].key;
		// dst->key_buckets[i].current_entries = src->key_buckets[i].current_entries;

		// if (dst->key_buckets[i].current_entries > dst->key_buckets[i].limit) {
		// 	dst->key_buckets[i].transaction_range = realloc(dst->key_buckets[i].transaction_range, src->key_buckets[i].limit*sizeof(RangeArray));
		// 	ALLOCATION_ERROR(dst->key_buckets[i].transaction_range);
		// }
		// dst->key_buckets[i].limit = src->key_buckets[i].limit;
		// // printf("dst limit: %zu   src limit: %zu\n",dst->key_buckets[i].limit, src->key_buckets[i].limit );
		// for (j = 0 ; j < src->key_buckets[i].current_entries ; j++) { /* for j in transactionRange */
		// 	// fprintf(stderr, "j = %zu\n",j );
		// 	dst->key_buckets[i].transaction_range[j].transaction_id = src->key_buckets[i].transaction_range[j].transaction_id;			
		// 	dst->key_buckets[i].transaction_range[j].rec_offset = src->key_buckets[i].transaction_range[j].rec_offset;
		// }
	}
}

void copySubbucketTransactions(SubBucket* dst, SubBucket* src){
	uint64_t j;
	dst->key = src->key;
	dst->current_entries = src->current_entries;
<commit_msg>Fixed lots of bugs, Runs without errors and with stable memory<commit_after>#include "extendibleHashing.h"

Hash* createHash() {
	Hash *hash = malloc(sizeof(Hash));
	ALLOCATION_ERROR(hash);
	hash->global_depth = GLOBAL_DEPTH_INIT;
	hash->size = 1 << GLOBAL_DEPTH_INIT;
	hash->index = malloc(hash->size * sizeof(Bucket *));
	ALLOCATION_ERROR(hash->index);
	uint64_t i;
	for (i = 0 ; i < hash->size ; i++)
		hash->index[i] = createNewBucket(GLOBAL_DEPTH_INIT, B);
	return hash;
}

int insertHashRecord(Hash* hash, Key key, RangeArray* rangeArray) {
	uint64_t bucket_num = hashFunction(hash->size, key);
	Bucket *bucket = hash->index[bucket_num];
	uint32_t i;
	for (i = 0 ; i < bucket->current_subBuckets; i++) {			/* for all subbuckets */
		if (bucket->key_buckets[i].key == key) {				/* if there is a subBucket with this key */
			uint64_t current_entries = bucket->key_buckets[i].current_entries;
			if (current_entries == bucket->key_buckets[i].limit) { 	/* if there isn't enough free space, realloc */
				bucket->key_buckets[i].transaction_range = realloc(bucket->key_buckets[i].transaction_range, ((bucket->key_buckets[i].current_entries)+C) * sizeof(RangeArray));
				ALLOCATION_ERROR(bucket->key_buckets[i].transaction_range);
				bucket->key_buckets[i].limit += C;
			}
			/* Insert entry */
			bucket->key_buckets[i].transaction_range[current_entries].transaction_id = rangeArray->transaction_id;
			bucket->key_buckets[i].transaction_range[current_entries].rec_offset = rangeArray->rec_offset;
			(bucket->key_buckets[i].current_entries)++;
			return OK_SUCCESS;
		}
	}
	/* If that was the first appearence of this key */
	if (bucket->current_subBuckets < B) {	/* If there is space to insert it on that bucket (there is a free subbucket) */
		bucket->key_buckets[bucket->current_subBuckets].key = key;
		bucket->key_buckets[bucket->current_subBuckets].transaction_range[0].transaction_id = rangeArray->transaction_id;
		bucket->key_buckets[bucket->current_subBuckets].transaction_range[0].rec_offset = rangeArray->rec_offset;
		bucket->key_buckets[bucket->current_subBuckets].current_entries += 1;
		(bucket->current_subBuckets)++;
		return OK_SUCCESS;
	} else {	/* if there is no space for a new key in this bucket */
		/* Doublicate index */
		if (bucket->local_depth >= hash->global_depth) { // one pointer per bucket -> doublicate index
			duplicateIndex(hash);	/* doublicates and increases global depth */
			bucket->local_depth++;
			Bucket *new_bucket = createNewBucket(bucket->local_depth, B);
			Bucket *tmp_bucket = createNewBucket(bucket->local_depth, B);
			copyBucketTransactions(tmp_bucket, bucket);
			cleanBucket(bucket);
			fixHashPointers(hash->index, new_bucket, hash->global_depth, bucket_num);
			uint32_t i;
			uint64_t new_hash, j;
			for (i = 0 ; i < B ; i++) {	/* for all subBuckets in tmpBucket */
				new_hash = hashFunction(1 << hash->global_depth, tmp_bucket->key_buckets[i].key); /* new_hash has a bucket number */
				if (new_hash == bucket_num) {	/* if the new bucket is the previous one and there is available subBucket space */
					uint32_t current_subBuckets = hash->index[new_hash]->current_subBuckets;
					hash->index[new_hash]->key_buckets[current_subBuckets].key = tmp_bucket->key_buckets[i].key;
					hash->index[new_hash]->key_buckets[current_subBuckets].current_entries = tmp_bucket->key_buckets[i].current_entries;
					uint64_t current_entries = hash->index[new_hash]->key_buckets[current_subBuckets].current_entries;
					for (j = 0 ; j < current_entries ; j++) {	/* for j in transactionRange of the bucket to be copied */
						hash->index[new_hash]->key_buckets[current_subBuckets].transaction_range[j].transaction_id = tmp_bucket->key_buckets[i].transaction_range[j].transaction_id;
						hash->index[new_hash]->key_buckets[current_subBuckets].transaction_range[j].rec_offset = tmp_bucket->key_buckets[i].transaction_range[j].rec_offset;
					}
					hash->index[new_hash]->current_subBuckets++;
				} else if (new_hash != bucket_num) {
					uint32_t current_subBuckets = new_bucket->current_subBuckets;
					new_bucket->key_buckets[current_subBuckets].key = tmp_bucket->key_buckets[i].key;
					new_bucket->key_buckets[current_subBuckets].current_entries = tmp_bucket->key_buckets[i].current_entries;
					uint64_t current_entries = new_bucket->key_buckets[current_subBuckets].current_entries;
					for(j = 0 ; j < current_entries ; j++ ) {
						new_bucket->key_buckets[current_subBuckets].transaction_range[j].transaction_id = tmp_bucket->key_buckets[i].transaction_range[j].transaction_id;
						new_bucket->key_buckets[current_subBuckets].transaction_range[j].rec_offset = tmp_bucket->key_buckets[i].transaction_range[j].rec_offset;
					}
					new_bucket->current_subBuckets++;
				}
			}
			destroyBucket(tmp_bucket, B);
			insertHashRecord(hash, key, rangeArray);
		} 
		/* split bucket */
		else if (bucket->local_depth < hash->global_depth) { 
			bucket->local_depth++;
			Bucket *new_bucket = createNewBucket(bucket->local_depth, B);
			Bucket *tmp_bucket = createNewBucket(bucket->local_depth, B);
			copyBucketTransactions(tmp_bucket, bucket);
			cleanBucket(bucket);
			uint32_t i;
			uint64_t new_hash;
			// Boolean_t all_in_old = True;
			// Boolean_t all_in_new = True;
			fixSplitPointers(hash, bucket, new_bucket, bucket_num);

			for (i = 0 ; i < B ; i++) {	/* for all subBuckets in tmpBucket */
				SubBucket *subbuckets = tmp_bucket->key_buckets;
				Key key = subbuckets[i].key;
				new_hash = hashFunction(hash->size, key);
				// fprintf(stderr, "New hash for %zu is %zu\n",key,new_hash );
				Bucket* destination = hash->index[new_hash];
				uint32_t current_subBuckets = destination->current_subBuckets;
				copySubbucketTransactions(&destination->key_buckets[current_subBuckets], &subbuckets[i]);
				destination->current_subBuckets++;
			}

			destroyBucket(tmp_bucket, B);
			insertHashRecord(hash, key, rangeArray);
		}
	}
	return OK_SUCCESS;
}  

/*Does whatever it says*/
void duplicateIndex(Hash * hash) {
	hash->global_depth++;
	uint64_t old_size = hash->size;
	hash->size *= 2;
	hash->index = realloc(hash->index, hash->size * sizeof(Bucket *));
	ALLOCATION_ERROR(hash->index);
	uint64_t i;
	for (i = old_size; i < hash->size; i++)
		hash->index[i] = NULL;
}

void destroyBucket(Bucket *bucket,uint32_t b) {
	uint32_t i;
	for (i = 0 ; i < b ; i++) { /*for each subBucket*/
		free(bucket->key_buckets[i].transaction_range);
	}
	free(bucket->key_buckets);
	free(bucket);
	bucket = NULL;
}

/* fix new indexes pointers after index doublicate */
void fixHashPointers(Bucket **index, Bucket *new_bucket, uint32_t global_depth, uint64_t bucket_num) {
	uint64_t i, j;
	uint64_t old_size = 1 << (global_depth-1);
	// fprintf(stderr, "-----------------------------------------------------\n");
	for (i = 0, j = old_size ; i < old_size ; i++, j++) {
		if (i == bucket_num) {
			// fprintf(stderr, "index[%zu] = new_bucket\n",j);
			index[j] = new_bucket;
		} else {
			// fprintf(stderr, "index[%zu] = index[%zu]\n",j,i );
			index[j] = index[i];
		}
	}
	// fprintf(stderr, "-----------------------------------------------------\n");
}

/* fix new indexes pointers after index splits */
void fixSplitPointers(Hash* hash, Bucket* old_bucket, Bucket* new_bucket, uint64_t bucket_num){
	uint64_t prev_local_depth = old_bucket->local_depth-1;
	uint64_t i;
	uint64_t ld_size = 1 << prev_local_depth;
	uint32_t first_pointer = bucket_num % ld_size;
	for (i = first_pointer ; i < hash->size ; i+=(2*ld_size)) { /* i in all old_bucket pointers */
		hash->index[i] = old_bucket;
		hash->index[i+ld_size] = new_bucket;
	}
}

/* copy transactions from one Bucket to another one*/
void copyBucketTransactions(Bucket* dst, Bucket* src) {
	uint64_t i;
	dst->local_depth = src->local_depth;
	dst->current_subBuckets = src->current_subBuckets;

	for (i = 0 ; i < src->current_subBuckets ; i++) {	/* for i in subBuckets */
		copySubbucketTransactions(&dst->key_buckets[i], &src->key_buckets[i]);
		// dst->key_buckets[i].key = src->key_buckets[i].key;
		// dst->key_buckets[i].current_entries = src->key_buckets[i].current_entries;

		// if (dst->key_buckets[i].current_entries > dst->key_buckets[i].limit) {
		// 	dst->key_buckets[i].transaction_range = realloc(dst->key_buckets[i].transaction_range, src->key_buckets[i].limit*sizeof(RangeArray));
		// 	ALLOCATION_ERROR(dst->key_buckets[i].transaction_range);
		// }
		// dst->key_buckets[i].limit = src->key_buckets[i].limit;
		// // printf("dst limit: %zu   src limit: %zu\n",dst->key_buckets[i].limit, src->key_buckets[i].limit );
		// for (j = 0 ; j < src->key_buckets[i].current_entries ; j++) { /* for j in transactionRange */
		// 	// fprintf(stderr, "j = %zu\n",j );
		// 	dst->key_buckets[i].transaction_range[j].transaction_id = src->key_buckets[i].transaction_range[j].transaction_id;			
		// 	dst->key_buckets[i].transaction_range[j].rec_offset = src->key_buckets[i].transaction_range[j].rec_offset;
		// }
	}
}

void copySubbucketTransactions(SubBucket* dst, SubBucket* src){
	uint64_t j;
	dst->key = src->key;
	dst->current_entries = src->current_entries;

{'fraction_non_alphanumeric': 0.15633438033834793, 'fraction_numerical': 0.008596462225161184, 'mean_word_length': 4.409239940387481, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 267, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5967839', 'n_tokens_mistral': 7052, 'n_tokens_neox': 6250, 'n_words': 1167}