#include #include /*--- anwendungsspezifischer Datentyp, Beispiel ---*/ typedef struct { int pers_num; /*--- eindeutiger Schluessel ---*/ char name[50]; unsigned int salary; } my_data_t; /*--- doppelt verzeigerte Liste mit Einträgen des o.g. Datentyps ---*/ struct list_entry_t { my_data_t data; struct list_entry_t *next; struct list_entry_t *prev; }; /*--- list handle ---*/ typedef struct { struct list_entry_t *headMarker; struct list_entry_t *lastMarker; /*--- currentEntry wird so verwendet, dass das nächste zu lesende Datenelement immer unter currentEntry->next zu suchen ist ---*/ struct list_entry_t *currentEntry; unsigned int length; } list_handle_t; /*--- einfach verkettete Listenstruktur fuer Hash Tables ---*/ struct hash_t { my_data_t *dataPtr; struct hash_t *next; }; /*---- Hash Array fuer die Suche nach pers_num (int-Hashing) ---* // Die Groesse sollte eine Primzahl sein // zB 1009, 5021, 9973 ----*/ #define HASIZE 37 struct hash_t *ha_int[HASIZE]; /*---- Hash Array fuer die Suche nach name (string-Hashing) ---*/ struct hash_t *ha_string[HASIZE]; /*********************************************************** * Funktionen fuer das Hashing - fuer Suche nach pers_num * in Einträgen der Liste 1 ***********************************************************/ int hashInt(unsigned int key) { return key%HASIZE; } void insertIntoHashtableInt(unsigned int key, my_data_t *d) { struct hash_t *newH = (struct hash_t *)malloc(sizeof(struct hash_t)); unsigned int index = hashInt(key); newH->dataPtr = d; newH->next = ha_int[index]; ha_int[index] = newH; // printf("Put (%d,%s,%d) to hash table ha_int at index %d\n", // d->pers_num, d->name, d->salary,index); } my_data_t *findInHashTableInt(unsigned int key) { my_data_t *retval = NULL; struct hash_t *h = ha_int[hashInt(key)]; while (h && h->dataPtr && h->dataPtr->pers_num != key) h = h->next; if ( h && h->dataPtr && h->dataPtr->pers_num == key ) retval = h->dataPtr; return retval; } int deleteInHashTableInt(unsigned int key) { int retcode = -1; struct hash_t *h = ha_int[hashInt(key)]; struct hash_t *prev = h; while (h && h->dataPtr && h->dataPtr->pers_num != key) { prev = h; h = h->next; } if ( h && h->dataPtr && h->dataPtr->pers_num == key ) { if ( prev == h ) { // gleich das erste Hashbucket ist zu loeschen ha_int[hashInt(key)] = h->next; } else { prev->next = h->next; } free(h); retcode = 0; } } /*********************************************************** * Funktionen fuer das Hashing - fuer Suche nach name * in Einträgen der Liste 1 ***********************************************************/ int hashString(char *key) { unsigned int iChar; unsigned int index = 0; for (iChar = 0; iChar < strlen(key); iChar++) { index = (256*index + key[iChar]) % HASIZE; } return index; } void insertIntoHashtableString(char *key, my_data_t *d) { struct hash_t *newH = (struct hash_t *)malloc(sizeof(struct hash_t)); unsigned int index = hashString(key); newH->dataPtr = d; newH->next = ha_string[index]; ha_string[index] = newH; printf("Put (%d,%s,%d) to hash table ha_string at index %d\n", d->pers_num, d->name, d->salary,index); } my_data_t *findInHashTableString(char *key) { my_data_t *retval = NULL; struct hash_t *h = ha_string[hashString(key)]; while (h && h->dataPtr && strcmp(h->dataPtr->name,key) ) h = h->next; if ( h && h->dataPtr && !strcmp(h->dataPtr->name,key) ) retval = h->dataPtr; return retval; } int deleteInHashTableString(char *key) { int retcode = -1; struct hash_t *h = ha_string[hashString(key)]; struct hash_t *prev = h; while (h && h->dataPtr && strcmp(h->dataPtr->name,key)) { prev = h; h = h->next; } if ( h && h->dataPtr && !strcmp(h->dataPtr->name,key) ) { if ( prev == h ) { // gleich das erste Hashbucket ist zu loeschen ha_string[hashString(key)] = h->next; } else { prev->next = h->next; } free(h); retcode = 0; } } /*********************************************************** * Funktionen des Listenpakets wie im vorigen Beispiel (list1.c) ***********************************************************/ list_handle_t *createList(void) { list_handle_t *handle = (list_handle_t *) calloc(1,sizeof(list_handle_t)); handle->headMarker = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); handle->lastMarker = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); handle->headMarker->next = handle->lastMarker; handle->headMarker->prev = handle->headMarker; handle->lastMarker->prev = handle->headMarker; handle->lastMarker->next = handle->lastMarker; handle->currentEntry = handle->headMarker; handle->length = 0; return handle; } /*-------------------------------------------------------*/ int appendToList(list_handle_t *handle, my_data_t *d) { int retval = -1; if ( handle && d ) { struct list_entry_t *entry = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); memcpy(&(entry->data),d,sizeof(my_data_t)); entry->prev = handle->lastMarker->prev; entry->next = handle->lastMarker; handle->lastMarker->prev->next = entry; handle->lastMarker->prev = entry; handle->length++; retval = handle->length; insertIntoHashtableInt(d->pers_num,&(entry->data)); insertIntoHashtableString(d->name,&(entry->data)); } return retval; } /*--------------------------------------------------------------------*/ int insertToList(list_handle_t *handle, my_data_t *d) { int retval = -1; if ( handle && d ) { struct list_entry_t *entry = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); memcpy(&(entry->data),d,sizeof(my_data_t)); entry->prev = handle->headMarker; entry->next = handle->headMarker->next; handle->headMarker->next->prev = entry; handle->headMarker->next = entry; handle->length++; retval = handle->length; insertIntoHashtableInt(d->pers_num,&(entry->data)); insertIntoHashtableString(d->name,&(entry->data)); } return retval; } /*------------------------------------------------------------ * Nachfolger-/Vorgaengerelemente der Liste lesen *-----------------------------------------------------------*/ my_data_t* readNextFromList(list_handle_t *handle) { my_data_t *d = NULL; if ( handle && handle->currentEntry->next != handle->lastMarker ) { /* Designentscheidung: Nutzer bekommt einen ZEIGER auf die Nutzdaten des Eintrags. Wenn dieser Eintrag später verändert oder gelöscht wird, findet der Benutzer danach NICHT mehr die ursprünglichen Daten. VORTEIL: Schnelle Operation, unabhängig von der Größe von my_data_t. */ d = &(handle->currentEntry->next->data); handle->currentEntry = handle->currentEntry->next; } return d; } my_data_t* readPrevFromList(list_handle_t *handle) { my_data_t *d = NULL; if ( handle && handle->currentEntry != handle->headMarker ) { d = &(handle->currentEntry->data); handle->currentEntry = handle->currentEntry->prev; } return d; } /*--------------------------------------------------------- * Bereits traversierte Liste erneut vom Anfang/vom Ende * an lesen *--------------------------------------------------------*/ int rereadList(list_handle_t *l) { int retcode = -1; if ( l ) { l->currentEntry = l->headMarker; retcode = l->length; } return retcode; } int rereadListReversed(list_handle_t *l) { int retcode = -1; if ( l ) { l->currentEntry = l->lastMarker->prev; retcode = l->length; } return retcode; } /*----------------------------------------------------- * Loesche das zuletzt gelesene Element in der Liste. *----------------------------------------------------*/ int deleteEntry(list_handle_t *l) { int retcode = -1; /*-- currentEntry zeigt auf das zuletzt gelesene Elemement der Liste, oder auf headMarker, wenn noch nichts gelesen wurde. Bedingung "currentEntry zeigt auf Nutzdaten" (und nicht etwa auf den Head Marker) kann durch l->currentEntry != l->headMarker abgefragt werden ---*/ if ( l->currentEntry != l->headMarker ) { struct list_entry_t *p = l->currentEntry; /*--- aus den Hash Tables loeschen ---*/ deleteInHashTableInt(l->currentEntry->data.pers_num); deleteInHashTableString(l->currentEntry->data.name); /* loesche currentEntry - currentEntry soll auf den Vorgänger des zu loeschenden Eintrags zeigen */ p->prev->next = p->next; p->next->prev = p->prev; l->currentEntry = p->prev; free(p); retcode = --(l->length); } else printf("cannot delete this entry!\n"); return retcode; } /*---------------------------------------------------------- * Liste vom naechsten zu lesenden Element an kopieren *---------------------------------------------------------*/ list_handle_t *copyList(list_handle_t *handle) { list_handle_t *newHandle = NULL; my_data_t *d; if ( handle ) { newHandle = createList(); while( d = readNextFromList(handle) ) appendToList(newHandle,d); } return newHandle; } /*--------------------------------------------------------*/ int getLength(list_handle_t *l) { return ( l ) ? l->length : -1 ; } /******************************************************** * Hauptprogramm *******************************************************/ int main() { int iCnt; list_handle_t *list1, *list2; my_data_t d1, *d2, *d3; list1 = createList(); d1.pers_num = 12341234; strcpy(d1.name,"name1"); d1.salary = 1000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); d1.pers_num = 12341235; strcpy(d1.name,"name2"); d1.salary = 2000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); d1.pers_num = 12341236; strcpy(d1.name,"name3"); d1.salary = 3000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); d1.pers_num = 12341237; strcpy(d1.name,"name4"); d1.salary = 4000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); d1.pers_num = 12341238; strcpy(d1.name,"name5"); d1.salary = 5000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); d1.pers_num = 12341239; strcpy(d1.name,"name0"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); d1.pers_num = 12341240; strcpy(d1.name,"nam0e"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); d1.pers_num = 12341241; strcpy(d1.name,"na0em"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); d1.pers_num = 12341242; strcpy(d1.name,"n0mea"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); d1.pers_num = 12341243; strcpy(d1.name,"0amen"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); d1.pers_num = 12341244; strcpy(d1.name,"anme0"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); d1.pers_num = 12341245; strcpy(d1.name,"mane0"); d1.salary = 121212; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); /*--- liste traversieren und Inhalt ausgeben ---*/ printf("*** 1. Listentraversion ***\n"); iCnt = 0; /*--- ACHTUNG: hier ist bewusst eine ZUWEISUNG in der Schleifenbedingung - Abbruch wenn Nullpointer von readNextFromList() zuerueckgegeben wird. ---*/ while ( d2 = readNextFromList(list1) ) printf("GOT ENTRY %d: PERS_NUM %d NAME %s SALARY %d - LIST LENGTH IS %d\n", ++iCnt,d2->pers_num,d2->name,d2->salary,getLength(list1)); /*--- Suche mittels Hash Table ---*/ printf("*** Suche in Hash Table nach Personalnummer ***\n"); if ( d2 = findInHashTableInt(12341239) ) { printf("FOUND PERS_NUM %d NAME %s SALARY %d BY HASHING\n", d2->pers_num,d2->name,d2->salary); } else printf("key 12341239 not found in hash table\n"); printf("*** Suche in Hash Table nach Name ***\n"); if ( d2 = findInHashTableString("name0") ) { printf("FOUND PERS_NUM %d NAME %s SALARY %d BY HASHING\n", d2->pers_num,d2->name,d2->salary); } else printf("Name name0 not found in hash table\n"); /*--- loesche erstes Listenelement ---*/ rereadList(list1); d2 = readNextFromList(list1); deleteEntry(list1); printf("*** Suche in Hash Table nach nicht mehr vorhandenem Namen ***\n"); if ( d2 = findInHashTableString("mane0") ) { printf("FOUND PERS_NUM %d NAME %s SALARY %d BY HASHING\n", d2->pers_num,d2->name,d2->salary); } else printf("Name mane0 not found in hash table\n"); }