home *** CD-ROM | disk | FTP | other *** search
/ Revista do CD-ROM 71 / CDROM71.ISO / internet / navoff / data1.cab / Sources / src / htshash.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-04-01  |  10.6 KB  |  372 lines
  1. /* ------------------------------------------------------------ */
  2. /*
  3. HTTrack Website Copier, Offline Browser for Windows and Unix
  4. Copyright (C) Xavier Roche, Yann Philippot and other contributors
  5.  
  6. This program is free software; you can redistribute it and/or
  7. modify it under the terms of the GNU General Public License
  8. as published by the Free Software Foundation; either version 2
  9. of the License, or any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  19.  
  20.  
  21. Important notes:
  22.  
  23. - We hereby ask people using this source NOT to use it in purpose of grabbing
  24. emails addresses, or collecting any other private information on persons.
  25. This would disgrace our work, and spoil the many hours we spent on it.
  26.  
  27.  
  28. This project has been developed by Xavier Roche and Yann Philippot,
  29. from the company Serianet at Caen, France (http://www.serianet.com)
  30. and other contributors (see the greetings file)
  31.  
  32. Please visit our Website: http://www.httrack.com
  33. */
  34.  
  35.  
  36. /* ------------------------------------------------------------ */
  37. /* File: httrack.c subroutines:                                 */
  38. /*       hash table system (fast index)                         */
  39. /* Author: Xavier Roche                                         */
  40. /* ------------------------------------------------------------ */
  41.  
  42. #include "htshash.h"
  43.  
  44. /* specific definitions */
  45. #include "htsbase.h"
  46. #include "htsmd5.h"
  47. #include <stdio.h>
  48. #include <stdlib.h>
  49. #include <string.h>
  50. /* END specific definitions */
  51.  
  52. // GESTION DES TABLES DE HACHAGE
  53. // MΘthode α 2 clΘs (adr+fil), 2e cle facultative
  54. // hash[no_enregistrement][pos]->hash est un index dans le tableau gΘnΘral liens
  55. // #define HTS_HASH_SIZE 8191  (premier si possible!)
  56. // type: numero enregistrement - 0 est case insensitive (sav) 1 (adr+fil) 2 (former_adr+former_fil)
  57. #if HTS_HASH
  58. // recherche dans la table selon nom1,nom2 et le no d'enregistrement
  59. // retour: position ou -1 si non trouvΘ
  60. int hash_read(hash_struct* hash,char* nom1,char* nom2,int type) {
  61.   unsigned int cle;
  62.   int pos; 
  63.   // calculer la clΘ de recherche, non modulΘe
  64.   if (type)
  65.     cle = hash_cle(nom1,nom2);
  66.   else
  67.     cle = hash_cle(convtolower(nom1),nom2);         // case insensitive
  68.   // la position se calcule en modulant
  69.   pos = (int) (cle%HTS_HASH_SIZE);
  70.   // entrΘe trouvΘe?
  71.   if (hash->hash[type][pos] >= 0) {             // un enregistrement avec une telle clΘ existe..
  72.     // tester table de raccourcis (hash)
  73.     // pos est maintenant la position recherchΘe dans liens
  74.     pos = hash->hash[type][pos];
  75.     while (pos>=0) {              // parcourir la chaine
  76.       switch (type) {
  77.       case 0:         // sav
  78.         if (strfield2(nom1,hash->liens[pos]->sav)) {  // case insensitive
  79. #if DEBUG_HASH==2
  80.           printf("hash: found shortcut at %d\n",pos);
  81. #endif
  82.           return pos;
  83.         }
  84.         break;
  85.       case 1:         // adr+fil
  86.         if ((strcmp(nom1,jump_identification(hash->liens[pos]->adr))==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  87. #if DEBUG_HASH==2
  88.           printf("hash: found shortcut at %d\n",pos);
  89. #endif
  90.           return pos;
  91.         }
  92.         break;
  93.       case 2:         // former_adr+former_fil
  94.         if (hash->liens[pos]->former_adr)
  95.         if ((strcmp(nom1,jump_identification(hash->liens[pos]->former_adr))==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  96. #if DEBUG_HASH==2
  97.           printf("hash: found shortcut at %d\n",pos);
  98. #endif
  99.           return pos;
  100.         }
  101.         break;
  102.       }
  103.       // calculer prochaine position dans la chaine
  104.       {
  105.         int old=pos;
  106.         pos=hash->liens[pos]->hash_next[type];   // sinon prochain dans la chaine
  107.         if (old==pos)
  108.           pos=-1;         // erreur de bouclage (ne devrait pas arriver)
  109.       }
  110.     }
  111.     
  112.     // Ok va falloir chercher alors..
  113.     /*pos=hash->max_lien;    // commencer α max_lien
  114.     switch (type) {
  115.     case 0:         // sav
  116.       while(pos>=0) {
  117.         if (hash->liens[pos]->hash_sav == cle ) {
  118.           if (strcmp(nom1,hash->liens[pos]->sav)==0) {
  119.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  120. #if DEBUG_HASH==2
  121.             printf("hash: found long search at %d\n",pos);
  122. #endif
  123.             return pos;
  124.           }
  125.         }
  126.         pos--;
  127.       }
  128.       break;
  129.     case 1:         // adr+fil
  130.       while(pos>=0) {
  131.         if (hash->liens[pos]->hash_adrfil == cle ) {
  132.           if ((strcmp(nom1,hash->liens[pos]->adr)==0) && (strcmp(nom2,hash->liens[pos]->fil)==0)) {
  133.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  134. #if DEBUG_HASH==2
  135.             printf("hash: found long search at %d\n",pos);
  136. #endif
  137.             return pos;
  138.           }
  139.         }
  140.         pos--;
  141.       }
  142.       break;
  143.     case 2:         // former_adr+former_fil
  144.       while(pos>=0) {
  145.         if (hash->liens[pos]->hash_fadrfil == cle ) {
  146.           if (hash->liens[pos]->former_adr)
  147.             if ((strcmp(nom1,hash->liens[pos]->former_adr)==0) && (strcmp(nom2,hash->liens[pos]->former_fil)==0)) {
  148.             hash->hash[type][(int) (cle%HTS_HASH_SIZE)] = pos;    // noter plus rΘcent dans shortcut table
  149. #if DEBUG_HASH==2
  150.             printf("hash: found long search at %d\n",pos);
  151. #endif
  152.             return pos;
  153.           }
  154.         }
  155.         pos--;
  156.       }
  157.     }*/
  158. #if DEBUG_HASH==1
  159.     printf("hash: not found after test %s%s\n",nom1,nom2);
  160. #endif
  161.     return -1;    // non trouvΘ
  162.   } else {
  163. #if DEBUG_HASH==2
  164.     printf("hash: not found %s%s\n",nom1,nom2);
  165. #endif
  166.     return -1;    // non trouvΘ : clΘ non entrΘe (mΩme une fois)
  167.   }
  168. }
  169.  
  170. // enregistrement lien lpos dans les 3 tables hash1..3
  171. void hash_write(hash_struct* hash,int lpos) {
  172.   unsigned int cle;
  173.   int pos; 
  174.   int* ptr;
  175.   //
  176.   if (hash->liens[lpos]) {                       // on sait jamais..
  177.     hash->max_lien = max(hash->max_lien,lpos);
  178. #if DEBUG_HASH
  179.     hashnumber=hash->max_lien;
  180. #endif
  181.     // ΘlΘment actuel sur -1 (fin de chaine)
  182.     hash->liens[lpos]->hash_next[0]=hash->liens[lpos]->hash_next[1]=hash->liens[lpos]->hash_next[2]=-1;
  183.     //
  184.     cle = hash_cle(convtolower(hash->liens[lpos]->sav),"");    // CASE INSENSITIVE
  185.     pos = (int) (cle%HTS_HASH_SIZE);
  186.     ptr = hash_calc_chaine(hash,0,pos);         // calculer adresse chaine
  187.     *ptr = lpos;                   // noter dernier enregistrΘ
  188. #if DEBUG_HASH==3
  189.     printf("[%d",pos);
  190. #endif
  191.     //
  192.     cle = hash_cle(jump_identification(hash->liens[lpos]->adr),hash->liens[lpos]->fil);
  193.     pos = (int) (cle%HTS_HASH_SIZE);
  194.     ptr = hash_calc_chaine(hash,1,pos);         // calculer adresse chaine
  195.     *ptr = lpos;                   // noter dernier enregistrΘ
  196. #if DEBUG_HASH==3
  197.     printf(",%d",pos);
  198. #endif
  199.     //
  200.     if (hash->liens[lpos]->former_adr) {         // former_adr existe?
  201.       cle = hash_cle(jump_identification(hash->liens[lpos]->former_adr),hash->liens[lpos]->former_fil);
  202.       pos = (int) (cle%HTS_HASH_SIZE);
  203.       ptr = hash_calc_chaine(hash,2,pos);         // calculer adresse chaine
  204.       *ptr = lpos;                   // noter dernier enregistrΘ
  205. #if DEBUG_HASH==3
  206.       printf(",%d",pos);
  207. #endif
  208.     }
  209. #if DEBUG_HASH==3
  210.     printf("] "); fflush(stdout);
  211. #endif
  212.   }
  213. #if DEBUT_HASH
  214.   else {
  215.     printf("* hash_write=0!!\n");
  216.     exit(1);
  217.   }
  218. #endif
  219.   //
  220. }
  221.  
  222. // calcul clΘ
  223. // il n'y a pas de formule de hashage universelle, celle-ci semble acceptable..
  224. unsigned long int hash_cle(char* nom1,char* nom2) {
  225.   /*
  226.   unsigned int sum=0;
  227.   int i=0;
  228.   while(*nom1) {
  229.     sum += 1;
  230.     sum += (unsigned int) *(nom1);
  231.     sum *= (unsigned int) *(nom1++);
  232.     sum += (unsigned int) i;
  233.     i++;
  234.   }
  235.   while(*nom2) {
  236.     sum += 1;
  237.     sum += (unsigned int) *(nom2);
  238.     sum *= (unsigned int) *(nom2++);
  239.     sum += (unsigned int) i;
  240.     i++;
  241.   }
  242.   */
  243.   return md5sum32(nom1)
  244.         +md5sum32(nom2);
  245. }
  246.  
  247. // calcul de la position finale dans la chaine des elements ayant la mΩme clΘ
  248. int* hash_calc_chaine(hash_struct* hash,int type,int pos) {
  249. #if DEBUG_HASH
  250.   int count=0;
  251. #endif
  252.   if (hash->hash[type][pos] == -1)
  253.     return &(hash->hash[type][pos]);    // premier ΘlΘment dans la chaine
  254.   pos=hash->hash[type][pos];
  255.   while(hash->liens[pos]->hash_next[type] != -1) {
  256.     pos = hash->liens[pos]->hash_next[type];
  257. #if DEBUG_HASH
  258.     count++;
  259. #endif
  260.   }
  261. #if DEBUG_HASH
  262.   count++;
  263.   longest_hash[type]=max(longest_hash[type],count);
  264. #endif
  265.   return &(hash->liens[pos]->hash_next[type]);
  266. }
  267. #endif
  268. // FIN GESTION DES TABLES DE HACHAGE
  269.  
  270. // --
  271.  
  272. // Check for duplicate entry (==1 : added)
  273. int inthash_write(hash_chain** hash,int hash_size,char* str,long int e) {
  274.   int pos = (hash_cle(str,"") % hash_size);
  275.   hash_chain* h=hash[pos];
  276.   while (h) {
  277.     if (strcmp(h->value,str)==0) {
  278.       h->pos=e;
  279.       return 0;
  280.     }
  281.     h=h->next;
  282.   }
  283.   // Not found, add it!
  284.   inthash_add(hash,hash_size,str,e);
  285.   return 1;
  286. }
  287.  
  288. // Increment pos value, create one if necessary (=0)
  289. // (==1 : created)
  290. int inthash_inc(hash_chain** hash,int hash_size,char* str) {
  291.   long int e=0;
  292.   int r=0;
  293.   if (inthash_read(hash,hash_size,str,&e)) {
  294.     e++;
  295.   }
  296.   else {    /* create new value */
  297.     e=0;
  298.     r=1;
  299.   }
  300.   inthash_write(hash,hash_size,str,e);
  301.   return (r);
  302. }
  303.  
  304.  
  305. // Does not check for duplicate entry
  306. void inthash_add(hash_chain** hash,int hash_size,char* str,long int e) {
  307.   int pos = (hash_cle(str,"") % hash_size);
  308.   hash_chain** h=&hash[pos];
  309.  
  310.   while (*h)
  311.     h=&((*h)->next);
  312.   *h=(hash_chain*)calloc(1,sizeof(hash_chain));
  313.   if (h) {
  314.     (*h)->next=NULL;
  315.     strcpy((*h)->value,str);
  316.     (*h)->pos=e;
  317.   }
  318. }
  319.  
  320. int inthash_read(hash_chain** hash,int hash_size,char* str,long int* e) {
  321.   int pos = (hash_cle(str,"") % hash_size);
  322.   hash_chain* h=hash[pos];
  323.   while (h) {
  324.     if (strcmp(h->value,str)==0) {
  325.       *e=h->pos;
  326.       return 1;
  327.     }
  328.     h=h->next;
  329.   }
  330.   return 0;
  331. }
  332.  
  333. void inthash_init(hash_chain** hash,int hash_size) {
  334.   int i;
  335.   for(i=0;i<hash_size;i++) {
  336.     hash[i]=NULL;
  337.   }
  338. }
  339.  
  340. void inthash_del(hash_chain** hash,int hash_size) {
  341.   if (hash) {
  342.     int i;
  343.     for(i=0;i<hash_size;i++) {
  344.       inthash_delchain(hash[i],0);
  345.       hash[i]=NULL;
  346.     }
  347.   }
  348. }
  349.  
  350. void inthash_mdel(hash_chain** hash,int hash_size) {
  351.   if (hash) {
  352.     int i;
  353.     for(i=0;i<hash_size;i++) {
  354.       inthash_delchain(hash[i],1);
  355.       hash[i]=NULL;
  356.     }
  357.   }
  358. }
  359.  
  360. void inthash_delchain(hash_chain* hash,int free_int) {
  361.   if (hash) {
  362.     inthash_delchain(hash->next,free_int);
  363.     if (free_int) {     // pos is a malloc() block, delete it!
  364.       if (hash->pos)
  365.         free((void*)hash->pos);
  366.       hash->pos=0;
  367.     }
  368.     free(hash);
  369.   }
  370. }
  371.  
  372.