Потокобезопасная хеш-таблица, написанная на C - PullRequest
Новая
       22

Потокобезопасная хеш-таблица, написанная на C

0 голосов
/ 20 марта 2019

Я пытаюсь создать настраиваемую многопоточную хеш-таблицу в C, используя std::atomic. Вот мой код:

ts_hash_table.hpp: 

#ifndef TS_HASH_TABLE_H
#define TS_HASH_TABLE_H

#include <iostream>
#include <thread>
#include <atomic>
#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10
#define THREAD_NUM 10

typedef struct element{
       int data;
       int key;
       struct element* next;
}ELEMENT;

typedef struct {
    int size;
    std::atomic<ELEMENT*>* buckets;
}HASH_TABLE;

extern HASH_TABLE* hash_table;

HASH_TABLE* createHashTable(int);
ELEMENT* createElement(int,int);
ELEMENT* get(int);

int calculateHash(int);
void insert(int, int);
void printList(ELEMENT*);
void printTable();  


#endif // TS_HASH_TABLE_H

ts_hash_table.cpp: 

#include "ts_hash_table.hpp"

HASH_TABLE* createHashTable(int size){

    HASH_TABLE* hash_table = (HASH_TABLE*)malloc(sizeof(HASH_TABLE));

    if (hash_table == NULL)
        return NULL;

    hash_table->buckets = (std::atomic<ELEMENT*>*)malloc(sizeof(ELEMENT*)*size);

    if (hash_table->buckets == NULL)
        return NULL;

    for (int i = 0; i < size; i++)
        hash_table->buckets[i] = NULL;

    hash_table->size = size;

    return hash_table;
}

void insert(int key,int data) {
   printf("INSERTING INTO HASH TABLE");

   ELEMENT* new_element = NULL;  

   int hashIndex = calculateHash(key);

   new_element->next = hash_table -> buckets[hashIndex].load();
   while(!hash_table -> buckets[hashIndex].compare_exchange_weak(new_element->next, new_element));

}   


ELEMENT* get(int key) {

   int hashIndex = calculateHash(key);  

   ELEMENT* element = hash_table->buckets[hashIndex];
   while(element != NULL) {

      if(element->key == key)
         return element; 

      element = element -> next;

      hashIndex %= TABLE_SIZE;
   }        

   return NULL;        
}

ELEMENT* createElement(int key, int data){

   ELEMENT* element = (ELEMENT*) malloc(sizeof(ELEMENT));

   element->data = data;  
   element->key = key;
   element->next = NULL;

   return element;
}

int calculateHash(int key) {
   return key % TABLE_SIZE;
}

void printTable() {

   for(int i = 0; i < TABLE_SIZE; i++) {

      printf("[BUCKET %d]: ", i);

      if(hash_table -> buckets[i].load() != NULL)
         printList(hash_table ->buckets[i].load());
      else
         printf("EMPTY");

      printf("\n");
   }

}

void printList(ELEMENT* head){

    while (head != NULL){
        printf(" (%d, %d)", head->key, head->data);
        head = head->next;
    }

}

main.cpp: 

#include "ts_hash_table.hpp"

HASH_TABLE* hash_table = createHashTable(TABLE_SIZE);

int main() {

   /*FILL IN THE TABLE*/

   printf("MAIN");
   insert(2,43);

   /*DISPLAY TABLE CONTENT*/

   printTable();

   return 0;
}

Внутри ts_hash_table.cpp вы можете видеть, что я пытался осуществить вставку в хеш-таблицу с помощью функции compare_excahnge_weak. По какой-то причине я получаю ошибка сегментации . Что мне не ясно, так это то, что даже когда я пытаюсь что-то напечатать при запуске функции insert, я не вижу этого. Не только это, но когда я компилирую и запускаю программу (используя g++ *.cpp -o main), печать, которую я поместил в основную функцию, не показывает даже то, что я звоню printf до insert. Но когда я закомментирую звонки, чтобы вставить все работает нормально.

Есть предложения? Я неправильно использую атомарную функцию?

EDIT:

Я использовал gdb для отладки кода, и похоже, что segfault происходит, когда я пытаюсь использовать load() функцию

enter image description here

...