Guest User

Untitled

a guest
Oct 18th, 2019
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct hash{
  2.     size_t largo;
  3.     size_t cantidad;
  4.     hash_destruir_dato_t destruir_dato;
  5.     lista_t** tabla;
  6. };
  7.  
  8. typedef struct datos{
  9.     char* clave;
  10.     void* valor;
  11. }datos_t;
  12.  
  13. void borrar_tabla(hash_t* hash, size_t cantidad, bool es_redimensionar, lista_t** tabla_nueva);
  14.  
  15. bool redimensionar_hash(hash_t* hash, size_t redimension);
  16.  
  17. size_t hashing(const char* clave, size_t tam);
  18.  
  19. void destruir_datos(hash_t* hash, datos_t* dato);
  20.  
  21. lista_t** crear_tabla(size_t capacidad);
  22.  
  23. datos_t* crear_dato(char* clave, void* valor){
  24.     datos_t* dato = malloc(sizeof(datos_t));
  25.     if(!dato) return NULL;
  26.     dato->clave = strdup(clave);
  27.     dato->valor = valor;
  28.     return dato;
  29. }
  30.  
  31. lista_t** crear_tabla(size_t capacidad){
  32.     lista_t** tabla = malloc(sizeof(hash_t)*capacidad);
  33.     if (!tabla) return NULL;
  34.     size_t i  = 0;
  35.     while( i < capacidad){
  36.         tabla[i] = lista_crear();
  37.         i++;
  38.     }
  39.     return tabla;
  40. }
  41.  
  42. hash_t *hash_crear(hash_destruir_dato_t destruir_dato){
  43.     hash_t* hash = malloc(sizeof(hash_t));
  44.     if(!hash) return NULL;
  45.     hash->largo = TAM;
  46.     hash->cantidad = 0;
  47.     if(destruir_dato != NULL) hash->destruir_dato = destruir_dato;
  48.     else hash->destruir_dato = NULL;
  49.     lista_t** tabla = crear_tabla(hash->largo);
  50.     if (!tabla) return NULL;
  51.     hash->tabla = tabla;
  52.     return hash;
  53. }
  54.  
  55. size_t hashing(const char* clave, size_t tam){
  56.     size_t hash = 5381;
  57.     int c;
  58.     while((c = *clave++) != 0){
  59.         hash = ((hash << 5) + hash) + c;
  60.     }
  61.     return hash % tam;
  62. }
  63.  
  64. bool hash_pertenece(const hash_t *hash, const char *clave){
  65.     size_t index = hashing(clave, hash->largo-1);
  66.     lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
  67.     while(!lista_iter_al_final(iter_lista)){
  68.         if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
  69.             lista_iter_destruir(iter_lista);
  70.             return true;
  71.         }
  72.         lista_iter_avanzar(iter_lista);
  73.     }
  74.     lista_iter_destruir(iter_lista);
  75.     return false;
  76. }
  77.  
  78. size_t hash_cantidad(const hash_t *hash){
  79.     return hash->cantidad;
  80. }
  81.  
  82. bool hash_guardar(hash_t *hash, const char *clave, void *dato){
  83.     if(((float)hash->cantidad/(float)hash->largo) > FACTOR_AUMENTO){
  84.         size_t redimension = hash->largo * 2;
  85.         if(!redimensionar_hash(hash,redimension)) return false;
  86.     }
  87.     datos_t* datos = crear_dato((char*)clave, dato);
  88.     size_t index = hashing(datos->clave,hash->largo-1);
  89.     lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
  90.     bool pertenece = hash_pertenece(hash, datos->clave);
  91.     if (pertenece){
  92.         while(!lista_iter_al_final(iter_lista)){
  93.             if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
  94.                 datos_t* aux = (datos_t*)lista_iter_borrar(iter_lista);
  95.                 destruir_datos(hash, aux);
  96.             }
  97.         }
  98.     }
  99.     lista_iter_insertar(iter_lista,datos);
  100.     if (!pertenece) hash->cantidad++;
  101.     lista_iter_destruir(iter_lista);
  102.     return true;
  103. }
  104.  
  105. void *hash_obtener(const hash_t *hash, const char *clave){
  106.     if (!hash_pertenece(hash,clave)) return NULL;
  107.     size_t index = hashing(clave, hash->largo-1);
  108.     lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
  109.     while(!lista_iter_al_final(iter_lista)){
  110.         if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
  111.             void* dato = ((datos_t*)lista_iter_ver_actual(iter_lista))->valor;
  112.             lista_iter_destruir(iter_lista);
  113.             return dato;
  114.         }
  115.         lista_iter_avanzar(iter_lista);
  116.     }
  117.     lista_iter_destruir(iter_lista);
  118.     return NULL;
  119. }
  120.  
  121. void *hash_borrar(hash_t *hash, const char *clave){
  122.     if (!hash_pertenece(hash,clave)) return NULL;
  123.     size_t index = hashing(clave, hash->largo-1);
  124.     lista_iter_t* iter_lista = lista_iter_crear(hash->tabla[index]);
  125.     while(!lista_iter_al_final(iter_lista)){
  126.         if (strcmp(clave,((datos_t*)lista_iter_ver_actual(iter_lista))->clave) == 0){
  127.             datos_t* dato_aux = (datos_t*)lista_iter_borrar(iter_lista);
  128.             void* aux = dato_aux->valor;
  129.             free(dato_aux->clave);
  130.             free(dato_aux);
  131.             hash->cantidad--;
  132.             lista_iter_destruir(iter_lista);
  133.             return aux;
  134.         }
  135.         lista_iter_avanzar(iter_lista);
  136.     }
  137.     lista_iter_destruir(iter_lista);
  138.     if(((float)hash->cantidad/(float)hash->largo) > FACTOR_REDUCCION){
  139.         size_t redimension = hash->largo / 2;
  140.         if(redimension > TAM) redimensionar_hash(hash,redimension);
  141.     }
  142.     return NULL;
  143. }
  144.  
  145. ///////////////////////////// REDIMENSIONAR /////////////////////////////////////////////
  146. ////////////////////////////////////////////////////////////////////////////////////////
  147.  
  148. bool redimensionar_hash(hash_t* hash, size_t redimension){
  149.     lista_t** tabla_nueva = crear_tabla(redimension);
  150.     size_t tam_viejo = hash->largo;
  151.     hash->largo = redimension;
  152.     borrar_tabla(hash, tam_viejo, true, tabla_nueva);
  153.     hash->tabla = tabla_nueva;
  154.     return true;
  155. }
  156.  
  157. void borrar_tabla(hash_t* hash, size_t cantidad, bool es_redimensionar, lista_t** tabla_nueva){
  158.     size_t i = 0;
  159.     while(i != cantidad){
  160.         if (lista_esta_vacia(hash->tabla[i])) lista_destruir(hash->tabla[i],NULL);
  161.         else{
  162.             while(!lista_esta_vacia(hash->tabla[i])){
  163.                 datos_t* aux = (datos_t*)lista_borrar_primero(hash->tabla[i]);
  164.                 if (es_redimensionar){
  165.                     size_t index = hashing(aux->clave,hash->largo-1);
  166.                     lista_insertar_ultimo(tabla_nueva[index], aux);
  167.                 }else destruir_datos(hash,  aux);
  168.             }
  169.             lista_destruir(hash->tabla[i], NULL);
  170.         }
  171.         i++;
  172.     }
  173.     free(hash->tabla);
  174. }
  175.  
  176. void destruir_datos(hash_t* hash, datos_t* dato){
  177.     free(dato->clave);
  178.     if (hash->destruir_dato != NULL) hash->destruir_dato(dato->valor);
  179.     free(dato);
  180. }
  181.  
  182. void hash_destruir(hash_t *hash){
  183.     borrar_tabla(hash, hash->largo, false, NULL);
  184.     free(hash);
  185. }
  186. //////////////////////////////////////////////////////////////////
  187. ///////////////////  ITERADOR DEL HASH  /////////////////////////
  188. ////////////////////////////////////////////////////////////////
  189.  
  190. struct hash_iter{
  191.     const hash_t* hash;
  192.     size_t pos;
  193.     size_t index;
  194.     lista_iter_t* iter_lista;
  195. };
  196.  
  197. size_t buscar_indice_valido(size_t indice, hash_iter_t* iter){
  198.     while(indice < iter->hash->largo){
  199.         if(!lista_esta_vacia(iter->hash->tabla[indice])){
  200.             iter->index =  indice;
  201.             return indice;
  202.         }
  203.         indice++;
  204.     }
  205.     return iter->hash->largo-1;
  206. }
  207.  
  208. hash_iter_t *hash_iter_crear(const hash_t *hash){
  209.     hash_iter_t* iter = malloc(sizeof(hash_iter_t));
  210.     if(!iter) return NULL;
  211.     iter->hash = hash;
  212.     iter->pos = 0;
  213.     iter->index = 0;
  214.     iter->iter_lista = lista_iter_crear(iter->hash->tabla[buscar_indice_valido(iter->index, iter)]);
  215.     return iter;
  216. }
  217.  
  218. bool hash_iter_al_final(const hash_iter_t *iter){
  219.     if (iter->pos == iter->hash->cantidad || (iter->index == iter->hash->largo-1 && lista_iter_al_final(iter->iter_lista))) return true;
  220.     return false;
  221. }
  222.  
  223. void comprobar_lugar_valido(hash_iter_t* iter){
  224.     lista_iter_destruir(iter->iter_lista);
  225.     iter->index++;
  226.     iter->iter_lista = lista_iter_crear(iter->hash->tabla[buscar_indice_valido(iter->index, iter)]);
  227. }
  228.  
  229. bool hash_iter_avanzar(hash_iter_t *iter){
  230.     if(hash_iter_al_final(iter)) return false;
  231.     if (!lista_iter_al_final(iter->iter_lista)){
  232.         lista_iter_avanzar(iter->iter_lista);
  233.         if (lista_iter_al_final(iter->iter_lista) && (!hash_iter_al_final(iter))) comprobar_lugar_valido(iter);
  234.         iter->pos++;
  235.     }
  236.     return true;
  237. }
  238.  
  239. const char *hash_iter_ver_actual(const hash_iter_t *iter){
  240.     if(hash_iter_al_final(iter)) return NULL;
  241.     datos_t* aux = (datos_t*)lista_iter_ver_actual(iter->iter_lista);
  242.     const char* clave = (const char*)aux->clave;
  243.     return clave;
  244. }
  245.  
  246. void hash_iter_destruir(hash_iter_t* iter){
  247.     free(iter->iter_lista);
  248.     free(iter);
  249. }
RAW Paste Data