Created
January 25, 2020 15:00
-
-
Save toravir/859f988e91f16241ce8f6a0273ac3b5f to your computer and use it in GitHub Desktop.
Finding Dela from different snapshots..
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
typedef struct hentry_st_ { | |
struct hentry_st_ *next; | |
int data; | |
} hentry; | |
typedef struct htable_st_ { | |
hentry **arr; | |
int size; | |
hentry *head; | |
} htable; | |
htable *newHashTable (int size) | |
{ | |
htable *tbl = calloc(sizeof(htable), 1); | |
if (tbl) { | |
tbl->arr = (hentry**)calloc(sizeof(hentry*), size); | |
if (!tbl->arr) { | |
free(tbl); | |
tbl = NULL; | |
} else { | |
tbl->size = size; | |
tbl->head = NULL; | |
} | |
} | |
return tbl; | |
} | |
int insertHT(htable *tbl, int key) | |
{ | |
if (!tbl) { | |
return -1; | |
} | |
int idx = key % tbl->size; | |
if (tbl->arr[idx] != NULL) { | |
printf("\n COLLISION !! NOT HANDLED !!"); | |
return -1; | |
} | |
hentry *ent = calloc(sizeof(hentry), 1); | |
if (!ent) { | |
return -1; | |
} | |
ent->data = key; | |
tbl->arr[idx] = ent; | |
ent->next = tbl->head; | |
tbl->head = ent; | |
} | |
int deleteHT (htable *tbl, int key) | |
{ | |
if (!tbl) { | |
return -1; | |
} | |
int idx = key % tbl->size; | |
if (tbl->arr[idx] == NULL || tbl->arr[idx]->data != key) { | |
//Not found | |
return 1; | |
} | |
hentry *ent = tbl->arr[idx]; | |
tbl->arr[idx] = NULL; | |
if (ent->next != NULL) { | |
//Middle Node | |
hentry *next = ent->next; | |
*ent = *next; //structure copy | |
free(next); | |
} else { | |
hentry *nextNode = tbl->head; | |
while (nextNode->next != NULL && nextNode->next->next != NULL) { | |
nextNode = nextNode->next; | |
} | |
if (nextNode->next != NULL) { | |
free(nextNode->next->next); | |
nextNode->next = NULL; | |
} else { | |
free(nextNode); | |
tbl->head = NULL; | |
} | |
} | |
return 0; | |
} | |
int printDiff (int *a, int lena, int *b, int lenb) | |
{ | |
htable *tbl = newHashTable(10); | |
for (int i = 0; i < lena; i++) { | |
insertHT(tbl, a[i]); | |
} | |
for (int i = 0; i < lenb; i++) { | |
int res = deleteHT(tbl, b[i]); | |
if (res == 1) { | |
printf("Add: %d\n", b[i]); | |
} | |
} | |
hentry *ent = tbl->head; | |
while (ent) { | |
printf("Del: %d\n", ent->data); | |
ent = ent->next; | |
} | |
return 0; | |
} | |
htable *processUpdate (htable *tbl, int *a, int lena) | |
{ | |
printf("\n !! PROCESSING UPDATE !! \n"); | |
if (tbl == NULL) { | |
tbl = newHashTable(10); | |
for (int i = 0; i < lena; i++) { | |
insertHT(tbl, a[i]); | |
} | |
return tbl; | |
} | |
htable *newTbl = newHashTable(10); | |
for (int i = 0; i < lena; i++) { | |
int res = deleteHT(tbl, a[i]); | |
if (res == 1) { | |
printf("Add: %d\n", a[i]); | |
insertHT(newTbl, a[i]); | |
} else if (res == 0) { | |
printf("Nop: %d\n", a[i]); | |
insertHT(newTbl, a[i]); | |
} | |
} | |
hentry *ent = tbl->head; | |
while (ent) { | |
printf("Del: %d\n", ent->data); | |
hentry *toFree = ent; | |
ent = ent->next; | |
free(toFree); | |
} | |
free(tbl); | |
return newTbl; | |
} | |
int main (void) | |
{ | |
int a[] = {11, 20, 33, 44}; | |
int b[] = {11, 22, 33, 55, 66}; | |
int c[] = {66, 77, 88}; | |
htable *tbl = NULL; | |
tbl = processUpdate(tbl, a, 4); | |
tbl = processUpdate(tbl, b, 5); | |
tbl = processUpdate(tbl, c, 3); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
!! PROCESSING UPDATE !! | |
!! PROCESSING UPDATE !! | |
Nop: 11 | |
Add: 22 | |
Nop: 33 | |
Add: 55 | |
Add: 66 | |
Del: 44 | |
Del: 20 | |
!! PROCESSING UPDATE !! | |
Nop: 66 | |
Add: 77 | |
Add: 88 | |
Del: 55 | |
Del: 33 | |
Del: 22 | |
Del: 11 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment