#include "dstm.h"
-obj_store_t *obj_begin; // points to the first location of the object store linked list
-//unsigned int hash_size; // number of entries in hash table
-
extern int classsize[];
-/* BEGIN - object store */
-// Initializes the pointers...currently invoked inside main()
-void dstm_init(void) {
- obj_begin = NULL;
- return;
-}
-// Create a new object store of a given "size" as a linked list
-void create_objstr(unsigned int size) {
- obj_store_t *tmp, *ptr;
- static int id = 0; // keeps track of which object store is it when there are more than one object store
-
- if ((tmp = (obj_store_t *) malloc(sizeof(obj_store_t))) < 0) {
- printf("DSTM: Malloc error %s %d\n", __FILE__, __LINE__);
- exit(-1);
- }
- if ((tmp->base = (char *) malloc(sizeof(char)*size)) < 0) {
- printf("DSTM: Malloc error %s %d\n", __FILE__, __LINE__);
- exit(-1);
- }
- tmp->size = size;
- printf("The object store size is : %d\n", tmp->size);
- tmp->top = tmp->base;
- tmp->id = id++;
- printf("The object store id is : %d\n", tmp->id);
- tmp->next = obj_begin; //adds new object store to the linked list and updates obj_begin pointer to new object store node
- obj_begin = tmp;
- return;
-}
-
-// Delete the object store numbered "id"
-void delete_objstr(int id) {
- //TODO Implement this along with garbage collector
- return;
-}
-
-obj_store_t *get_objstr_begin(void) {
- return obj_begin;
-}
-
-/* END object store */
-
/* BEGIN object header */
+
// Get a new object id
-int get_newID(void) {
- static int id = 0;
-
+unsigned int getNewOID(void) {
+ static int id = 1;
return ++id;
}
-// Insert the object header and object into the object store
-int insertObject(obj_header_t h) {
- extern obj_addr_table_t mlut; //declared in the main mlut=>machine look up table
- unsigned int left, req; // Keeps track of the space available in the current object store
- obj_header_t *header;
-
- left = obj_begin->size - (obj_begin->top - obj_begin->base);
- req = getObjSize(h) + sizeof(obj_header_t);
- if (req < left) {
- memcpy(obj_begin->top, &h, sizeof(obj_header_t));
- header = (obj_header_t *) obj_begin->top;
- printf("The header points to : %d\n", header);
- obj_begin->top = obj_begin->top + sizeof(obj_header_t) + getObjSize(h); //increment object store top when new object is inserted
- printf("Top now points to :%d\n", obj_begin->top);
- } else {
- return -1;
- }
- printf("header: %d\n", header);
- printf("The oid is : %d\n", h.oid);
- addKey(h.oid, header, &mlut); //Update obj_addr_table
- printf("Object id = %d\n",h.oid);
- return 0;
-}
+
// Get the size of the object for a given type
-int getObjSize(obj_header_t h) {
+unsigned int objSize(objheader_t *object) {
return classsize[h.type];
}
-// Initial object when it is created at first
-void createObject(unsigned short type) {
- obj_header_t h;
- h.oid = get_newID();
- h.type = type;
- h.version = 0;
- h.rcount = 1;
- h.status = CLEAN;
- insertObject(h);
-}
/* END object header */
-/* BEGIN hash*/
-//obj_addr_table is a generic hash table structure
-//hash is an array of pointers that point to the beginning of a obj_listnode_t DS
-// "size" in hash table is the no of indices in the hash table and each index points to a pointer for an object_header
-void createHash(obj_addr_table_t *table, int size, float loadfactor) {
- int i;
-
- if ((table->hash = (obj_listnode_t **) malloc(sizeof(obj_listnode_t *)*size)) == NULL) {
- printf("Malloc error %s %d\n", __FILE__, __LINE__);
- exit(-1);
- }
- for (i = 0; i < size; i++) { // initialize the hash elements
- table->hash[i] = NULL;
- }
-
- table->size = size;
- table->numelements = 0;
- table->loadfactor = loadfactor;
-
- return;
-}
-
-// Hash Resize
-void resize(obj_addr_table_t * table){
- int newCapacity = 2*(table->size) + 1;
- obj_listnode_t **old;
- //if ((table->hash = (obj_listnode_t **) malloc(sizeof(obj_listnode_t *)*size)) == NULL) {
-}
-
-// Hashing for the Key
-int hashKey(unsigned int oid, obj_addr_table_t *table) {
- // hash32shiftmult
- int c2=0x27d4eb2d; // a prime or an odd constant
- oid = (oid ^ 61) ^ (oid >> 16);
- oid = oid + (oid << 3);
- oid = oid ^ (oid >> 4);
- oid = oid * c2;
- oid = oid ^ (oid >> 15);
- printf("The bucket number is %d\n", oid % (table->size));
- return (oid % (table->size));
-}
-
-//Add oid and its address to the new ob_listnode_t
-void addKey(unsigned int oid, obj_header_t *ptr, obj_addr_table_t *table) {
- int index;
- obj_listnode_t *node;
-
- table->numelements++;
- if(table->numelements > (table->loadfactor * table->size)){
- //TODO : check if table is nearly full and then resize
- }
-
- index = hashKey(oid,table);
- if ((node = (obj_listnode_t *) malloc(sizeof(obj_listnode_t))) == NULL) {
- printf("Malloc error %s %d\n", __FILE__, __LINE__);
- exit(-1);
- }
- node->oid = oid;
- node->object = ptr;
- node->next = table->hash[index];
- table->hash[index] = node;
- return;
-}
-// Get the address of the object header for a given oid
-obj_header_t *findKey(unsigned int oid, obj_addr_table_t *table) {
- int index;
- obj_listnode_t *ptr;
-
- index = hashKey(oid,table);
- ptr = table->hash[index];
- while(ptr != NULL) {
- if (ptr->oid == oid) {
- return ptr->object;
- }
- ptr = ptr->next;
- }
- return NULL;
-}
-// Remove the pointer to the object header from a linked list of obj_listnode_t given an oid
-int removeKey(unsigned int oid, obj_addr_table_t *table) {
- int index;
- obj_listnode_t *curr, *prev; // prev points to previous node and curr points to the node to be deleted
-
- index = hashKey(oid,table);
- prev = curr = table->hash[index];
- for (; curr != NULL; curr = curr->next) {
- if (curr->oid == oid) { // Find a match in the hash table
- table->numelements--;
- prev->next = curr->next;
- if (table->hash[index] == curr) { // Special case when there is one element pointed by the hash table
- table->hash[index] = NULL;
- }
- free(curr);
- return 0;
- }
- prev = curr;
- }
- return -1;
-}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
-#include "hashtable.h"
enum status {CLEAN, DIRTY};
+/************************************************************************************************
+ IMP NOTE:
+
+ All llookup hash function prototypes returns 0 or NULL when there is an error or else returns 1
+ llookup hash is an array of lhashlistnode_t
+ oid = mid = 0 in a given lhashlistnode_t for each bin in the hash table ONLY if the entry is empty =>
+ the OID's can be any unsigned int except 0
+***************************************************************************************************/
#include "llookup.h"
+extern lhashtable_t llookup; //Global Hash table
+
// Creates a hash table with default size HASH_SIZE and an array of lhashlistnode_t
-lhashtable_t lhashCreate(unsigned int size, float loadfactor) {
- lhashtable_t newtable;
+unsigned int lhashCreate(unsigned int size, float loadfactor) {
lhashlistnode_t *nodes;
+ int i;
+ // Allocate space for the hash table
if((nodes = calloc(HASH_SIZE, sizeof(lhashlistnode_t))) == NULL) {
printf("Calloc error %s %d\n", __FILE__, __LINE__);
- exit(-1);
+ return 0;
}
+ for (i = 0; i < HASH_SIZE; i++)
+ nodes[i].next = NULL;
- newtable.table = nodes;
- newtable.size = size;
- newtable.numelements = 0; // Initial list of elements in the hash
- newtable.loadfactor = loadfactor;
-
- return newtable;
+ llookup.table = nodes;
+ llookup.size = size;
+ llookup.numelements = 0; // Initial number of elements in the hash
+ llookup.loadfactor = loadfactor;
+ return 1;
}
// Assign to oids to bins inside hash table
-unsigned int lhashFunction(lhashtable_t table, unsigned int oid) {
- return( oid % (table.size));
+unsigned int lhashFunction(unsigned int oid) {
+ return( oid % (llookup.size));
}
// Insert oid and mid mapping into the hash table
-void lhashInsert(lhashtable_t table, unsigned int oid, unsigned int mid) {
+unsigned int lhashInsert(unsigned int oid, unsigned int mid) {
unsigned int newsize;
int index;
lhashlistnode_t *ptr;
lhashlistnode_t *node;
- ptr = table.table;
- table.numelements++;
- if (table.numelements > (table.loadfactor * table.size)) {
+ if (llookup.numelements > (llookup.loadfactor * llookup.size)) {
//Resize Table
- newsize = 2 * table.size + 1;
- lhashResize(table, newsize);
+ newsize = 2 * llookup.size + 1;
+ lhashResize(newsize);
}
+ ptr = llookup.table;
+ llookup.numelements++;
- index = lhashFunction(table, oid);
- if(ptr[index].next == NULL) { // Insert at the first position
+ index = lhashFunction(oid);
+ if(ptr[index].next == NULL && ptr[index].oid == 0) { // Insert at the first position in the hashtable
ptr[index].oid = oid;
ptr[index].mid = mid;
} else { // Insert in the linked list
if ((node = calloc(1, sizeof(lhashlistnode_t))) == NULL) {
printf("Calloc error %s, %d\n", __FILE__, __LINE__);
- exit(-1);
+ return 0;
}
node->oid = oid;
node->mid = mid;
node->next = ptr[index].next;
ptr[index].next = node;
}
+ return 1;
}
// Search for a value in the hash table
-int lhashSearch(lhashtable_t table, unsigned int oid) {
+unsigned int lhashSearch(unsigned int oid) {
int index;
lhashlistnode_t *ptr;
lhashlistnode_t *tmp;
- ptr = table.table; // Address of the beginning of hash table
- index = lhashFunction(table, oid);
- tmp = ptr[index].next;
+ ptr = llookup.table; // Address of the beginning of hash table
+ index = lhashFunction(oid);
+ tmp = &ptr[index];
while(tmp != NULL) {
if(tmp->oid == oid) {
return tmp->mid;
}
tmp = tmp->next;
}
- return -1;
+ return 0;
}
// Remove an entry from the hash table
-int lhashRemove(lhashtable_t table, unsigned int oid) {
+unsigned int lhashRemove(unsigned int oid) {
int index;
- lhashlistnode_t *curr, *prev;
+ lhashlistnode_t *curr, *prev, *tmp;
lhashlistnode_t *ptr;
- ptr = table.table;
- index = lhashFunction(table, oid);
+ ptr = llookup.table;
+ index = lhashFunction(oid);
prev = curr = &ptr[index];
for (; curr != NULL; curr = curr->next) {
if (curr->oid == oid) { // Find a match in the hash table
- table.numelements--;
- prev->next = curr->next;
- if (curr == &ptr[index]) {
- ptr[index].oid = 0;
- ptr[index].mid = 0;
- // TO DO: Delete the first element in the hash table
+ llookup.numelements--; // Decrement the number of elements in the global hashtable
+ if ((curr == &ptr[index]) && (curr->next == NULL)) { // Delete the first item inside the hashtable with no linked list of lhashlistnode_t
+ curr->oid = 0;
+ curr->mid = 0;
+ } else if ((curr == &ptr[index]) && (curr->next != NULL)) { //Delete the first item with a linked list of lhashlistnode_t connected
+ curr->oid = curr->next->oid;
+ curr->mid = curr->next->mid;
+ tmp = curr->next;
+ curr->next = curr->next->next;
+ free(tmp);
+ } else { // Regular delete from linked listed
+ prev->next = curr->next;
+ free(curr);
}
- free(curr);
- return 0;
+ return 1;
}
prev = curr;
}
- return -1;
+ return 0;
}
// Resize table
-void lhashResize(lhashtable_t table, unsigned int newsize) {
- int i;
+unsigned int lhashResize(unsigned int newsize) {
+ lhashlistnode_t *node, *curr, *next; // curr and next keep track of the current and the next lhashlistnodes in a linked list
lhashtable_t oldtable;
- lhashlistnode_t *ptr;
- lhashlistnode_t *node;
- lhashlistnode_t *new;
-
- oldtable.table = table.table;
- oldtable.size = table.size;
- oldtable.numelements = table.numelements;
- oldtable.loadfactor = table.loadfactor;
- ptr = oldtable.table;
+ int i, isfirst; // Keeps track of the first element in the lhashlistnode_t for each bin in hashtable
- //Allocate new space
+ oldtable.table = llookup.table; // copy orginial lhashtable_t type to a new structure
+ oldtable.size = llookup.size;
+ oldtable.numelements = llookup.numelements;
+ oldtable.loadfactor = llookup.loadfactor;
if((node = calloc(newsize, sizeof(lhashlistnode_t))) == NULL) {
printf("Calloc error %s %d\n", __FILE__, __LINE__);
- exit(-1);
+ return 0;
}
-
- table.table = node;
- table.numelements = 0;
- for(i=0; i< oldtable.size ; i++) { //For each entry in the old hashtable insert
- //the element into the new hash table
- new = &ptr[i];
- while ( new != NULL) {
- lhashInsert(table, new->oid, new->mid);
- new = new->next;
+ llookup.table = node; //Update the global hashtable upon resize()
+ llookup.size = newsize;
+ llookup.numelements = 0;
+
+ for(i = 0; i < oldtable.size; i++) {
+ curr = next = &oldtable.table[i];
+ isfirst = 1; //isfirst = true by default
+ while (curr != NULL) {
+ if (curr->oid == 0) { //Exit inner loop if there the first element for a given bin/index is NULL
+ break; //oid = mid =0 for element if not present within the hash table
+ }
+ next = curr->next;
+ lhashInsert(curr->oid, curr->mid); //Call hashInsert into the new resized table
+ if (isfirst != 1) {
+ free(curr); //free the linked list of lhashlistnode_t if not the first element in the hash table
+ }
+ isfirst = 0; //set isFirst = false inside inner loop
+ curr = next;
}
}
- free(oldtable.table); // Free the oldhash table
- table.size = newsize;
+ free(oldtable.table); //free the copied hashtable calloc-ed
+ return 1;
}
-
-
float loadfactor;
} lhashtable_t;
-/* Prototypes for hash*/
-lhashtable_t lhashCreate(unsigned int size, float loadfactor);
-unsigned int lhashFunction(lhashtable_t table, unsigned int oid);
-void lhashInsert(lhashtable_t table, unsigned int oid, unsigned int mid);
-int lhashSearch(lhashtable_t table, unsigned int oid); //returns oid, -1 if not found
-int lhashRemove(lhashtable_t table, unsigned int oid); //returns -1 if not found
-void lhashResize(lhashtable_t table, unsigned int newsize);
-/* end hash */
+unsigned int lhashCreate(unsigned int size, float loadfactor);// returns 1 for success and 0 for failure
+unsigned int lhashFunction(unsigned int oid); // returns 1 for success and 0 for failure
+unsigned int lhashInsert(unsigned int oid, unsigned int mid); // returns 1 for success and 0 for failure
+unsigned int lhashSearch(unsigned int oid); //returns mid, 0 if not found
+unsigned int lhashRemove(unsigned int oid); //returns 0 if not success
+unsigned int lhashResize(unsigned int newsize); // returns 1 for success and 0 for failure
#endif
-
--- /dev/null
+#include <stdio.h>
+#include "llookup.h"
+
+lhashtable_t llookup;
+
+main()
+{
+ int i, mid;
+
+ if (lhashCreate(10, 0.80) == 0) {
+ printf("lhashCreate error\n"); //creates hashtable
+ }
+ for (i = 1; i <= 10; i++) { // Checks the insert() and resize()
+ if (lhashInsert(10*i, i) == 0)
+ printf("lhashInsert error\n");
+ }
+
+ i = lhashRemove(10);//Delete first element in the hashtable
+ if(i == 0)
+ printf("lhashRemove error ");
+
+ for (i = 1; i <=10; i++) { // Check if it can search for all oids in hash table
+ mid = lhashSearch(10*i);
+ if (mid != i)
+ printf("lhashSearch error - mid = %d\n", mid);
+ else
+ printf("lhashSearch oid = %d mid = %d\n",10*i, mid);
+ }
+
+ i = lhashRemove(60);
+ if(i == 0)
+ printf("lhashRemove error ");
+
+ for (i = 1; i <= 10; i++) { //Prints all left over elements inside hash after deletion and prints error if element not found in hash
+ mid = lhashSearch(10*i);
+ if (mid != i)
+ printf("lhashSearch error - mid = %d\n", mid);
+ else
+ printf("lhashSearch oid = %d mid = %d\n",10*i, mid);
+ }
+
+}
projects / IRC.git / commitdiff