user hash / IoT Database

주어진 name과 같은 name을 갖는 student를 찾아 해당 Student를 hash table 에서 삭제

void dell(const char name[Max_NAME+1)

name 이 키가 되도록 할 것

해당 student 를 hash table에 삽입

주어진 name 과 score 를 갖는 student 를 생성(전역변수에 저장)하고,

 

void insert(const char name[MAX_NAME+1], const int score){}

 

해당 하는 Student 가 hash table에 없을 경우 nullptr 을 return

주어진 name 과 같은 네임을 같는 학생을 찾아 스투던트를 리턴

 

50개 3초
Global 변수, Static 변수
해당 변수 사용 금지

비휘발성 메모리 가진 IoT 단말의 데이터를 관리하는 데이터베이스 AIP 구현

구현 함수
Bool init 초기화 함수, 각 TC별 처음 1회 호출도미
void put(unsigned char key_in[], unsigned char value_in[]): 주어진 키와 밸류를 데이터베이스에 저장함
void del(unsigned char key_in[]) : key 값으로 주어진 문자열을 데이터베이스에서 삭제함
void get(unsigned char key_in[], unsigned char value_out[]): key 값을 input으로 value 를 찾아서 value_out에 기록함
void get_key(unsigned char value_in[]. unsinged char key_out[]):value 값을 인풋으로 value를 찾아서 key_out에 기록함

메인에서 주어지는 API
void memread(unsigned char str[]. int pos, int len) : pos 위치에서 len 만큼 memory를 읽어 str에 저장함
void memwrite(unsigned char str[], int pos, int len) : pos 위치에서 len 만큼 str에 저장된 값을 emmory에 저장함

ㅈ제약 사항
1. 주어진 키값과 밸류 값은 유니크한 값이다. 밸류가 AAA 입력으로 들어온 경우, 동일한 AAA 를 가진 값은 입력을 ㅗ주어지지 않는다
2. 입력 데이터 수 엔은 최소 10에서 최대 2400까지 주어진다. 
3. 명령어 수행은 풀, 델, 겟, 겟 키를 모두 합쳐서 최대 50,000번 호출될 수 있음
4. 비휘발성 메모리 사이즈는 65536바이트입니다.
5. 글로벌 변수 또는 스태틱 변수는 사용할 수 없음 100점이 나오더라도 패일로 간주함

 

#include <stdio.h> // 헤더파일 파일 메인에서. 

#define MAXN 2400 //  데이터의 수 앤은 10~2400
#define SIZE 65536 // 비휘발성 메모리 사이즈 65536 임
#define LEN  12 // 왜 길이가 12가 저장되어 있는거지? 픽스되어 있는 이유

unsigned char mem[SIZE]; // 양수쪽으로의 범위를 더 받을 수 있음

typedef enum COMMAND // 커맨드 enum 열거함 풋, 델, 겟, 겟키, 엔드
{
    PUT = 100,
    DEL = 200,
    GET = 300,
    GET_KEY = 400,
    END = 900,
};

int N, M; // 
int ret = 100; // 

// 만들어야 하는 API 함수 종류
extern bool init(int N); // 초기화 함수, 각 TC별 처음 1회 호출됨
extern void put(unsigned char key_in[], unsigned char value_in[]); // 주어진 키와 값을 데이터 베이스에 저장함
extern void del(unsigned char key_in[]); // 키값으로 주어진 문자열을 데이터베이스에서 삭제함
extern void get(unsigned char key_in[], unsigned char value_out[]); // 키값을 인풋으로 밸류를 찾아서 value_out 에 기록함
extern void get_key(unsigned char value_in[], unsigned char key_out[]); // 밸류값을 인풋으로 밸류를 찾아서 키 아웃에 기록함

int mstrcmp(unsigned char arr[], unsigned char arr2[])
{
    register int i = 0; // 메모리 대신 CPU의 레지스터를 사용함 일반 변수보다 속도가 빠름. 개수가 한정되어 있음
    while (arr[i])
    {
        if (arr[i] != arr2[i++]) return 0; // 앞과 뒤의 단어가 같으면 리턴 0
    }
    if (arr2[i]) return 0; // 숫자가 있으면 리턴 90
    return 1;
}

void memread(unsigned char str[], int pos, int len) // pos 에서 len만큼 momery를 읽어 str 에 저장함
{
    for (register int i = 0; i < len; i++)
    {
        str[i] = mem[pos + i];
    }
}

void memwrite(unsigned char str[], int pos, int len) // pos 위치에서 len 만큼 str에 저장된 값을 memory에 저장함
{
    for (register int i = 0; i < len; i++)
    {
        mem[pos + i] = str[i];
    }
}

void run()
{
    unsigned char key[LEN + 1]; // 인덱스가 0부터 시작해서 +1 을 하는건가
    unsigned char value[LEN + 1]; // 밸류 저장
    int cmd; // 명령어
    for (register int i = 0; i < M; i++) // 아 명령어 갯수가 엠이구나.
    {
        scanf("%d", &cmd); // 명령어 개수

        switch (cmd)
        {
        case PUT:
        {
            scanf("%s %s", key, value); // 키와 밸류를 받음
            put(key, value);
            break;
        }
        case DEL:
        {
            scanf("%s", key);
            del(key);
            break;
        }
        case GET:
        {
            unsigned char out[LEN + 1];
            scanf("%s %s", key, out);
            get(key, value);
            if (mstrcmp(value, out) == 0) ret = 0;
            break;
        }
        case GET_KEY:
        {
            unsigned char out[LEN + 1];
            scanf("%s %s", value, out);
            get_key(value, key);
            if (mstrcmp(key, out) == 0) ret = 0;
            break;
        }
        case END:
        default: return;
        }
    }
}

int main() // 메인 함수 실행됨
{
    int T; //테케를 받음

//    freopen("input.txt", "r", stdin);

    scanf("%d", &T); // 받음
    for (register int testcase = 1; testcase <= T; testcase++)
    {
        scanf("%d %d", &N, &M); // 10, 10을 받음
        if (init(N)) run(); //초기화를 하고, 런을 돌림
        printf("#%d %d\n", testcase, ret); // 테케와 결과를 출력함
    }

    return 0;
}

- 유저 코드를 보고 해석
- 주석 달지 못한 부분
- 감으로는 알겠으나, 아직 모름 ㅎㅎ
- 다른 코드를 보고 해석해보도록 하겠음 

 

//#include <stdio.h>
extern int mstrcmp(unsigned char arr[], unsigned char arr2[]); // 메인 에서 가져오기
extern void memread(unsigned char str[], int pos, int len);
extern void memwrite(unsigned char str[], int pos, int len);

#define SIZE 65536 
//? SIZE는 어떻게 가져오지????????????????????
extern unsigned char mem[SIZE];

// 자체 제작 hash
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    unsigned long namuzi;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c) % SIZE;
    }

    hash = hash % SIZE;
    namuzi = hash % 27;  // 처음이 27의 배수가 되도록 수정!!!!!

    return hash - namuzi;
}


bool init(int N)
{
    return true;
}

void put(unsigned char key_in[], unsigned char value_in[])
{
    // database에 필드를 저장.
    //mem[h]에 1 넣어줘! -> what?

    unsigned char str_key[13]; // 선언
    unsigned char str_value[13]; // 선언
    unsigned long h = hash(key_in);
    int cnt = SIZE / 27; // (65536 / 27)

    while (cnt--) {
        if (mem[h] == 1) {
            h = (h + 27) % SIZE;
            continue;
        }
        memwrite(key_in, h + 1, 13); // 12하면 '\0'까지 cpy가 안되는듯!!!!!
        memwrite(value_in, h + 14, 13); // 12하면 '\0'까지 cpy가 안되는듯!!!!!
        memread(str_key, h + 1, 13); //ex
        memread(str_value, h + 14, 13); //ex
        mem[h] = 1;
        mem[65535]++;
        //printf(" put done : %s %s \n", key_in, value_in);
        //printf(" put done : %s %s \n", str_key, str_value);
        return;
    }
}

void del(unsigned char key_in[])
{
    // key 값으로 주어진 문자열을 통해 database에서 삭제.
    // mem[h]에 0 넣어줘!
    unsigned char a1[3], a2[3]; //key[2] 저장
    unsigned long h = hash(key_in);
    int cnt = SIZE / 27; // (65536 / 27)
    unsigned char stored_key[13];
    unsigned char stored_value[13];

    for (int i = 0; i < 2; i++)
        a1[i] = key_in[i];
    a1[2] = '\0'; // 안하면 data 출력시 에러
                  //printf(" a1 : %s \n", a1);

    while (cnt--) {
        if (mem[h] == 0) {
            h = (h + 27) % SIZE;
            continue;
        }

        memread(a2, h + 1, 2);
        a2[2] = '\0'; // 안하면 data 출력시 에러

                      //printf("   -> a2 : %s \n", a2);
                      //printf("start mstrcmp \n");
        if (mstrcmp(a1, a2)) {
            //printf("finish mstrcmp \n");
            memread(stored_key, h + 1, 13);
            //printf(" stored key : %s \n", stored_key);
            //printf(" original key : %s \n", key_in);
            //stored_key뒤에 \0 넣어줘야하는거 아님????? 안그럼 mstrcmp가 안됨 
            // ㅠㅠㅠㅠㅠㅠㅠㅠㅠ어케해 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
            //stored_key[12] = '\0';

            if (mstrcmp(stored_key, key_in)) {
                //printf("in \n");
                //memwrite("00000000000000000000000000", h + 1, 26); //?????초기화맞음????? "0" 이 안되는거 같은디!!!!!
                //printf("write done \n");
                memwrite(stored_value, h + 14, 13); // ex
                                                    //stored_value[12] = '\0';
                mem[h] = 0;
                mem[65535]--;
                //printf(" del done : %s %s \n", key_in, stored_value);
                return;
            }
        }
        h = (h + 27) % SIZE;
    }
}

// memread해줄 때 끝에 '\0'넣어서 반환해줘야하는거같은데!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

/*
void get(unsigned char key_in[], unsigned char value_out[])
{
// key값을 input으로 value를 찾아서 value_out에 기록.
}
*/

void get_key(unsigned char value_in[], unsigned char key_out[])
{
    unsigned char a1[3], a2[3]; // value[2] 저장
    int total_num = mem[65535];
    // value값을 input으로 value를 찾아서 key_out에 기록.
    unsigned char stored_value[13];

    for (int i = 0; i < 2; i++)
        a1[i] = value_in[i];
    a1[2] = '\0'; // 안하면 data 출력시 에러

                  //while(total_num--){
    for (int i = 0; i < 2427; i++) {
        if (mem[27 * i] == 0) continue;
        memread(a2, 27 * i + 14, 2);
        a2[2] = '\0'; // 안하면 data 출력시 에러
        if (mstrcmp(a1, a2)) {
            memread(stored_value, 27 * i + 14, 13);
            if (mstrcmp(stored_value, value_in)) {
                memread(key_out, 27 * i + 1, 13);
                //printf(" get_key done : %s %s \n", key_out, value_in);
                return;
            }
        }
    }
    //}

}

//int find(const char *key, char *data)
//int get_value(unsigned char *key, unsigned char *data)
void get(unsigned char key_in[], unsigned char value_out[])
{
    unsigned char a1[3], a2[3]; // key[2]저장
    unsigned long h = hash(key_in);
    int cnt = SIZE / 27; // (65536 / 27)
    unsigned char stored_key[13];

    for (int i = 0; i < 2; i++)
        a1[i] = key_in[i];
    a1[2] = '\0'; // 안하면 data 출력시 에러

                  // 1. key가 같으면
                  // 2. value를 반환한다.

                  //while (mem[h] != 0 && cnt--)
                  //while (mem[h] != 0 && cnt-- && h < SIZE){
    while (cnt--) {
        if (mem[h] == 0) {
            h = (h + 27) % SIZE;
            continue;
        }

        memread(a2, h + 1, 2);
        a2[2] = '\0'; // 안하면 data 출력시 에러
        if (mstrcmp(a1, a2)) {
            memread(stored_key, h + 1, 13);
            if (mstrcmp(stored_key, key_in)) {
                memread(value_out, h + 14, 13);
                //printf(" get_value done : %s %s \n", key_in, value_out);
                return;
            }
        }
        h = (h + 27) % SIZE;
        //memread(a2, 0, 0);
    }
}

- 오케이 
- 해시 관련한 코드가 있음
- 그럼 해시 관련 코드 어떻게 짜는지 살펴볼 필요가 있음
- 쉬운 코드부터 ㄱ