· 7 years ago · Feb 16, 2019, 03:02 PM
1//devi farci per forza la mutua esclusione nella ht
2#include <stdio.h>
3#include <stdlib.h>
4#include <pthread.h>
5#include <sys/types.h>
6#include <stdint.h>
7#include <string.h>
8#include <errno.h>
9
10
11/// La dimensione di una hashtable
12#define MAX_TRABOCCHI 100000
13#define MAX 105
14static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
15
16//Una lista di trabocco di una tabella hash
17
18typedef struct lista_trabocco {
19 char *key; // Chiave del nodo
20
21 struct lista_trabocco *next; // Nodo successivo
22} lista;
23
24
25// Tabella hash
26
27typedef struct hash_table {
28 lista* cella[MAX_TRABOCCHI]; // Tabella dei cella(array di liste)
29 int nkeys; //numero di iscritti
30 pthread_mutex_t mutex[MAX_TRABOCCHI];
31
32}hash;
33
34
35//funzione hash metodo della divisione
36
37 int fhash(const char *string){
38
39
40 int i;
41 int ncelle=50021;//BHO STO NUMERO VEDI
42 int key=0; // valore key
43
44for(i=0;i<strlen(string);i++)
45//printf("il valore di %c è %d",ciao[i],ciao[i]);
46key+=string[i];
47
48
49return key % ncelle;
50}
51
52
53
54
55
56
57void lista_addT(lista ** list,char * el){
58
59lista* new=malloc(sizeof(lista));
60new->key=malloc(1+strlen(el));
61strcpy(new->key,el);
62
63new->next=*list;
64*list=new;
65
66}
67
68
69
70void lista_addC(lista **list, char* x)
71{
72 lista *curr,*new=malloc(sizeof(lista));
73
74 new->key=x;
75 new->next=NULL;
76
77 if(*list==NULL)
78 *list=new;
79 else
80 {
81 curr=*list;
82
83 while(curr->next!=NULL)
84 curr=curr->next;
85
86 curr->next=new;
87 }
88}
89
90
91
92
93
94void hash_print(hash* ht)
95{
96errno=0;
97 int i;
98
99
100/*
101for(i=0;i<MAX_TRABOCCHI;i++){int nodo=0;
102 if(ht->cella[i]){
103 for (curr=ht->cella[i]; curr != NULL; curr=curr->next){
104 if(curr->key!=NULL)
105 printf("cella[%d],nodo[%d]= %s \n",i,nodo,curr->key);nodo++;}
106 }
107 }*/
108
109
110 lista* curr;
111 int hash_val;
112
113//if(pthread_mutex_lock(&mutex)!=0)printf("lock mutex errore");
114
115
116
117
118
119for(i=0;i<MAX_TRABOCCHI;i++){
120int nodo=0;
121 for (curr=ht->cella[i]; curr != NULL; curr=curr->next){
122 //if ( strcmp(curr->key,key)==0 ){
123 printf("cella[%d],nodo[%d]=%s\n",i,nodo,curr->key);
124
125 // return curr->key;
126 nodo++;
127 }
128
129 }
130
131
132}
133
134
135
136
137
138
139
140
141//Create a new hash table.
142
143
144hash * hash_create()
145{
146 errno=0;
147
148 // hash *ht = (hash*) malloc(sizeof(hash)); //se non worka
149
150 //hash *ht = calloc(1, sizeof(hash));
151 hash *ht = calloc(1, sizeof(hash));
152
153 if(!ht) {
154 errno=ENOENT;
155 return NULL;
156 }
157
158
159 if(!ht->cella){
160 errno=ENOENT;
161 return NULL;
162 }
163
164 return ht;
165}
166
167
168//cerca la chiave nella ht
169
170char * hash_get (hash *ht, char* key)
171{
172errno=0;
173 lista* curr;
174 int hash_val;
175
176//if(pthread_mutex_lock(&mutex)!=0)printf("lock mutex errore");
177
178
179 hash_val = fhash(key);
180int nodo=0;
181 for (curr=ht->cella[hash_val]; curr != NULL; curr=curr->next){
182 if ( strcmp(curr->key,key)==0 ){
183 printf("cella[%d],nodo[%d] ho trovato %s\n",hash_val,nodo,curr->key);
184 ;
185}
186nodo++;
187 }
188
189//RILASCIA LA MUTEX SE CI RIESCE
190
191 // if(pthread_mutex_unlock(&mutex)!=0)printf("unlock mutex errore");
192
193 if(curr==NULL){
194 errno=EINVAL;
195 return "L'utente non è presende nel database";
196 }
197
198errno=ENOENT;
199return "problemuccio";
200}
201
202
203//inserisci in ht
204
205hash* hash_insert(hash *ht, char* key)
206{
207errno=0;
208hash * fall=ht;
209
210 lista *curr;
211 int hash_val;
212
213 if(ht==NULL || key==NULL) {errno=ENOENT;return fall;}//+errore
214
215 hash_val = fhash(key);
216
217//if(pthread_mutex_lock(&mutex)!=0)printf("lock mutex errore");
218
219
220if(ht->cella[hash_val]!=NULL){
221 for (curr=ht->cella[hash_val]; curr->next != NULL; curr=curr->next){
222 if ( strcmp(curr->key,key)==0){
223 errno=EINVAL;
224 return ht;
225 } /* key already exists */
226 }
227}
228
229
230
231
232
233const char* return_all(hash *ht)
234{
235
236errno=0;
237lista* curr;
238
239char* string=malloc(MAX);
240int i, k=0;
241//if(pthread_mutex_lock(&mutex)!=0)printf("lock mutex errore");
242for(i=0;i<MAX_TRABOCCHI;i++)
243 {
244
245 for (curr=ht->cella[i]; curr != NULL; curr=curr->next)
246 {
247 if (curr->key!=NULL )
248 {
249 memcpy(ciao[k],curr->key,strlen(curr->key)+1);
250 k+=strlen(curr->key)+1;
251 }
252
253
254 }
255 }
256
257return string;
258}//fine return_all
259
260
261
262
263
264
265lista_addT(&ht->cella[hash_val],key);
266/*
267 /* if key was not found
268printf("\n\nsto aggiungengo %s nella cella[%d],nodo[0]\n",key,hash_val);
269
270 lista* new=malloc(sizeof(lista));
271 new->key=key;
272//strcpy(new->key,el);
273new->next=ht->cella[hash_val];
274ht->cella[hash_val]=new;
275
276printf("\n\nho aggiunto %s nella cella[%d],nodo[0]",ht->cella[hash_val]->key,hash_val);
277 */
278 ht->nkeys++;
279
280//RILASCIA LA MUTEX SE CI RIESCE
281//if(pthread_mutex_unlock(&mutex)!=0)printf("unlock mutex errore");
282
283 return ht;
284}
285
286
287
288/**
289 * Free one hash table entry located by key (key and data are freed using functions).
290 *
291 * @param ht -- the hash table to be freed
292 * @param key -- the key of the new item
293 * @param free_key -- pointer to function that frees the key
294 * @param free_data -- pointer to function that frees the data
295 *
296 * @returns 0 on success, -1 on failure.
297 */
298 int hash_delete(hash *ht, void* key)
299{
300errno=0;
301 lista *curr, *prec;
302 unsigned int hash_val;
303
304 if(!ht || !key) return -1;
305 hash_val = fhash(key);
306int i=0;
307
308//if(pthread_mutex_lock(&mutex)!=0)printf("lock mutex errore");
309
310 prec = NULL;
311 for (curr=ht->cella[hash_val]; curr != NULL; ) {
312
313 if ( strcmp(curr->key,key)==0) {
314
315 if (prec == NULL)
316 ht->cella[hash_val] = curr->next;
317
318 else
319 prec->next = curr->next;
320
321 // if (curr->key) free(curr->key);
322 // if (curr->info) free(curr->info);
323
324 ht->nkeys--;
325
326printf("cella[%d],nodo[%d] =cancello %s\n",hash_val,i,curr->key);
327 free(curr);
328
329 return 0;
330 }
331 i++;
332 prec = curr;
333 curr = curr->next;
334 }
335
336//if(pthread_mutex_unlock(&mutex)!=0)printf("unlock mutex errore");
337
338
339 return -1;
340}
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367int main(){
368
369
370int prova;
371
372char* gatto=calloc(1,MAX);
373char* ciao=malloc(200);
374char* result=calloc(1,MAX);
375
376
377//memset(ciao,1,sizeof(ciao));
378//creo nuova hash table
379 hash* ht=hash_create();
380
381//inserisco a priori l'elemento Ciccio
382//ht=hash_insert(ht,"Ciccio");
383// if(errno)perror("Error1: "); //controllo errno
384
385
386printf("\n\nnumero elementi %d \n\n",ht->nkeys);
387 //printf("Username già in uso\n");
388
389ht=hash_insert(ht,"Ciccio");
390 if(errno)perror("Error1: ");
391
392
393
394ht=hash_insert(ht,"ko");// printf("Username già in uso\n");
395 if(errno)perror("Error2: ");
396
397ht=hash_insert(ht,"ok");// printf("Username già in uso\n");
398 if(errno)perror("Error3: ");
399
400ht=hash_insert(ht,"baaaaa");
401 if(errno)perror("Error4: ");
402
403ht=hash_insert(ht,"abaaaa");
404 if(errno)perror("Error5: ");
405
406ht=hash_insert(ht,"aabaaa");
407 if(errno)perror("Error6: ");
408
409ht=hash_insert(ht,"aaabaa");
410 if(errno)perror("Error7: ");
411
412
413int tmp=0;
414printf("Benvenuto al database delle persone piselle. \n\n");
415
416 while(tmp!=-1){
417 printf("Aggiungi un nome,termina con -1 \n\n");
418//fgets(ciao,MAX,stdin);
419 scanf("%s",ciao);
420 // memcpy(ciao2,ciao,);
421//ciao=realloc(ciao,sizeof(strlen(ciao))-1);
422 scanf("%d",&tmp);
423
424 ht=hash_insert(ht,ciao);
425 if(errno)perror("Errorget1: ");
426
427
428 printf("\n\nnumero elementi %d \n\n",ht->nkeys);
429 hash_print(ht);
430
431 }
432
433char ciao2[MAX];
434strcpy(ciao2,return_all(ht));
435/*
436//while(errno) {
437//if(errno)perror("Error4: ");
438//printf ("error 432,ritenta\n");
439printf("Aggiungi 2 : username\n");
440fgets(ciao,20,stdin);
441ht=hash_insert(ht,ciao,ciao);
442 if(errno)perror("Errorget2: ");
443//}
444
445printf("Aggiungi 3 : username\n");
446fgets(ciao,20,stdin);
447ht=hash_insert(ht,ciao,ciao);
448 if(errno)perror("Errorget3: ");
449
450/*printf("Aggiungi 4 : username\n");
451fgets(ciao,20,stdin);
452ht=hash_insert(ht,ciao,ciao);
453 if(errno)perror("Errorget4: "); */
454
455
456
457//printf("compilaaa3\n");
458
459
460tmp=0;
461int tmp2=0;
462
463while(1){
464printf("\n\nRicerca mirata,scrivi *numero cella* INVIO *numero nodo*\ntermina con -1 \n\n");
465int i;
466scanf("%d",&tmp);
467if(tmp==-1)break;
468scanf("%d",&tmp2);
469
470lista * curr;
471curr=ht->cella[tmp];
472
473for(i=0;i<tmp2;i++){
474curr=curr->next;
475}
476
477printf("%s \n\n",curr->key);
478
479}
480
481
482
483
484
485while(strcmp(gatto,"nessuno") && strcmp(gatto,"Nessuno")){
486//printf("%d\n",fhash(gatto));printf("%d\n",fhash("nessuno"));
487
488printf("\n\nChi vuoi cercare in database?\ndigita *nessuno* o *Nessuno* per terminare \n\n");
489
490//fgets(gatto,MAX,stdin);
491scanf("%s",gatto);
492result=hash_get (ht,gatto);
493
494//if(strcmp(ciao,result)==0) printf("Si non ti preoccupare ti ho già segnato\n");
495
496//else{
497if(strcmp(gatto,"nessuno") && strcmp(gatto,"Nessuno") ){
498 //if(errno!=EINVAL) //&& strcmp(result,ciao)!=0
499 // printf("Trovato!E'bello\n");
500 //else
501 if(errno==EINVAL)printf("%s \n\n",result);
502}
503//}
504
505}
506
507
508char* yn=calloc(1,MAX);
509printf("\n\nVuoi scancellare uno ? chi? \n\n");
510
511scanf("%s",yn);
512
513
514
515
516 prova=hash_delete(ht,yn);
517
518 if(errno)perror("Hash_Delete error:");
519
520 hash_print(ht);
521
522
523
524
525printf("\n\nArrivederci.\n");
526
527return 0;
528}