radix-hash-join/Index.c at master · GeorgeMitrakis/radix-hash-join · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <stdlib.h>

#include "Index.h"


int hash2(int32_t payload)
{
    int n =( payload >> RADIX_N ) % HASH2_RANGE;
    return n;
}

void index_create(hash_index **indx_addr, int bucket_array_sz)
{
    (*indx_addr) = malloc(sizeof(hash_index));
    hash_index * indx = *indx_addr;

    indx -> bucket_array = malloc(bucket_array_sz * sizeof(int));
    indx -> bucket_array_sz = bucket_array_sz;

    indx -> chain = NULL;
    indx -> chain_sz = -1;
}

void index_fill(hash_index *indx, relation *rel, int tuple_amount, int bucket_end)
{//tuple amount: histogram[i] ; bucket_end : psum[i]

    //initialize bucket array
    for (int j = 0; j < indx-> bucket_array_sz; j++)
    {
        indx->bucket_array[j] = -1;
    }

    //now the bucket i of the relation y is the one that will be hashed
    //create the chain array
    indx -> chain = realloc(indx -> chain, tuple_amount * sizeof(int));
    for (int j = 0; j < tuple_amount; j++)
    {
        indx -> chain[j] = -1;
    }
    indx -> chain_sz = tuple_amount;

    //assign boundaries of the bucket i of relation y
    int first_pos = bucket_end - tuple_amount; //starting position of bucket i within relation y
    int last_pos = bucket_end -1;  //ending position of bucket i within relation y
    int pos = last_pos;     //variable for current position

    while(pos >= first_pos)
    {//accessing bucket elements from last to first; insert their position to the index chain
        int n = hash2(rel->tuples[pos].payload);
        if (indx -> bucket_array[n]== -1)
        {
            indx -> bucket_array[n] = pos - first_pos;
        }
        else
        {
            int temp_pos = indx -> bucket_array[n];
            while(indx -> chain[temp_pos] != -1)
            {
                temp_pos = indx -> chain[temp_pos];
            }
            indx -> chain[temp_pos] = pos - first_pos;
        }
        pos--;
    }

}

void index_destroy(hash_index **indx)
{
    free((*indx) -> bucket_array);
    (*indx) -> bucket_array = NULL;
    (*indx) -> bucket_array_sz = -1;

    free((*indx) -> chain);
    (*indx) -> chain = NULL;
    (*indx) -> chain_sz = -1;

    free(*indx);
    *indx = NULL;
}

void search_val(relation *rel, int bucket_start, hash_index *indx, int32_t key, int32_t payload, int column_id, resultsWithNum* res)
{//search all instances equal to payload in the current index bucket of rel
    //rel is the relation whose bucket is currently indexed
    //bucket_start is the first index of the current bucket in rel
    //the key and payload arguments belong to the other relation and will be compared to the contents of rel

    int n = hash2(payload);

    if(indx->bucket_array[n] != -1)
    {
        int curr_pos = indx->bucket_array[n];
        int real_pos = curr_pos + bucket_start;
        if (payload == rel->tuples[real_pos].payload)
        {
            if(column_id == 1)//relation R tuple (key, payload) is compared to bucket of relation S
                add_result(res, key, rel->tuples[real_pos].key);
            else if(column_id==2)//relation S tuple (key, payload) is compared to bucket of relation R
                add_result(res, rel->tuples[real_pos].key, key);
        }
        while(indx -> chain[curr_pos] != -1)
        {
            curr_pos = indx->chain[curr_pos];
            real_pos = curr_pos + bucket_start;

            if (payload == rel->tuples[real_pos].payload)
            {
                if(column_id == 1)//relation R tuple (key, payload) is compared to bucket of relation S
                    add_result(res, key, rel->tuples[real_pos].key);
                else if(column_id==2)//relation S tuple (key, payload) is compared to bucket of relation R
                    add_result(res, rel->tuples[real_pos].key, key);
            }
        }
    }
}