Changeset 1414

Show
Ignore:
Timestamp:
10/13/07 18:47:04 (11 months ago)
Author:
till
Message:

nebula
- fixed sized queues for outlier list and cluster elements; size can be set via command line options
- hash tries can be cleaned up by recursively deleting paths
- progress output

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • nebula/trunk/src/Makefile.am

    r1375 r1414  
    99                        util.c util.h \ 
    1010                        trie.c trie.h \ 
    11                         hashlist.c hashlist.h \ 
     11                        hashq.c hashq.h \ 
    1212                        ngram.c ngram.h \ 
    1313                        cluster.c cluster.h \ 

  • nebula/trunk/src/cluster.c

    r1377 r1414  
    2020 
    2121#include <stdio.h> 
     22#include <string.h> 
    2223 
    2324#include "cluster.h" 
     25#include "hashq.h" 
    2426#include "nebula.h" 
    2527#include "trie.h" 
    2628 
    2729 
    28 u_int16_t add_entry_to_cluster(cluster *cl, hash_list *entry) { 
    29         if ((cl->entries = (hash_list **) realloc(cl->entries, (cl->cnt+1) * sizeof(hash_list *))) == NULL) { 
     30/* create new cluster */ 
     31inline cluster *cluster_new(void) { 
     32        cluster *new; 
     33 
     34        /* create new cluster */ 
     35        if ((new = calloc(1, sizeof(cluster))) == NULL) { 
    3036                fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
    3137                exit(EXIT_FAILURE); 
    3238        } 
    33         cl->entries[cl->cnt++] = entry; 
    3439 
    35         return(cl->cnt); 
     40        /* create element queue */ 
     41        if ((new->hq = calloc(1, sizeof(hashq))) == NULL) { 
     42                fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
     43                exit(EXIT_FAILURE); 
     44        } 
     45 
     46        return(new); 
    3647} 
    3748 
    3849 
    39 cluster *extend_cluster(hash_list *md5sum1, hash_list *md5sum2) { 
    40         cluster *cl, *cl_new; 
     50/* delete cluster */ 
     51void cluster_free(cluster *cl, u_char list_files, void(*cbfn)(hashq *hq, u_char flag)) { 
     52        if (!cl) return; 
    4153 
    42         if (md5sum1->cl == NULL) { 
    43                cl = NULL; 
     54        if (cbfn) cbfn(cl->hq, list_files); 
     55        free(cl); 
    4456 
    45                 /* create new cluster */ 
    46                 if ((cl_new = calloc(1, sizeof(cluster))) == NULL) { 
    47                         fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
    48                         exit(EXIT_FAILURE); 
    49                 } 
    50                 md5sum1->cl = cl_new; 
    51                 md5sum2->cl = cl_new; 
    52  
    53                 add_entry_to_cluster(cl_new, md5sum1); 
    54                 add_entry_to_cluster(cl_new, md5sum2); 
    55  
    56                 /* prepend new cluster to list */ 
    57                 cl_new->next = cluster_list; 
    58                 cluster_list = cl_new; 
    59  
    60                 num_of_clusters++; 
    61  
    62                 return(cl_new); 
    63         } 
    64                  
    65         /* add element to existing cluster */ 
    66         md5sum2->cl = md5sum1->cl; 
    67         add_entry_to_cluster(md5sum1->cl, md5sum2); 
    68  
    69         return(md5sum1->cl); 
     57        return; 
    7058} 
    7159 
    7260 
    73 void clusterlist_delete(cluster *list) { 
    74         int     i; 
    75         cluster *cl; 
     61/* free a cluster's hash queue and its hashes */ 
     62void cluster_hashq_free(hashq *hq, u_char list_files) { 
     63        hashq_free(hq, list_files, hash_free); 
     64        return; 
     65} 
     66 
     67 
     68cluster *add_entry_to_cluster(cluster *cl, hash *entry) { 
     69        qelem   *new; 
     70 
     71        if (cl->hq->size < clusterq_max) { 
     72                // set cluster pointer in hash struct 
     73                entry->cl = cl; 
     74 
     75                // add hash to queue 
     76                if ((new = hashq_prepend(cl->hq, entry)) == NULL) { 
     77                        fprintf(stderr, "Error - Could not add entry to cluster.\n"); 
     78                        exit(EXIT_FAILURE); 
     79                } 
     80        } else { 
     81                if (verbose) fprintf(stderr, "Warning - Could not add hash to cluster queue: Maximum size reached.\n"); 
     82                return(NULL); 
     83        } 
     84 
     85        return(cl); 
     86} 
     87 
     88 
     89cluster *create_cluster(hash *l1, hash *l2) { 
     90        cluster *cl = cluster_new(); 
     91 
     92        add_entry_to_cluster(cl, l1); 
     93        add_entry_to_cluster(cl, l2); 
     94 
     95        /* prepend new cluster to list */ 
     96        cl->next = cluster_list; 
     97        if(cluster_list) cluster_list->prev = cl; 
     98        cluster_list = cl; 
     99 
     100        num_of_clusters++; 
     101 
     102        return(cl); 
     103} 
     104 
     105 
     106cluster *clusters_merge(cluster *dst, cluster *new) { 
     107                cluster *cl1, *cl2; 
     108                qelem   *entry; 
     109 
     110                cl1 = dst; 
     111                cl2 = new; 
     112 
     113                // join lists 
     114                cl1->hq->tail->next = cl2->hq->head; 
     115                cl1->hq->tail = cl2->hq->tail; 
     116                cl1->hq->size += cl2->hq->size; 
     117 
     118                // let elements of cl2 point to cl1 
     119                for (entry = cl2->hq->head; entry; entry = entry->next) ((hash*)entry->data)->cl = cl1; 
     120                cl2->hq->head = cl2->hq->tail = NULL; 
     121 
     122                // unlink and free cluster 2 
     123                if(cl2->prev) cl2->prev->next = cl2->next; 
     124                if(cl2->next) cl2->next->prev = cl2->prev; 
     125 
     126                // check whether cl2 is the list head 
     127                if (cluster_list == cl2) cluster_list = cl2->next; 
     128 
     129 
     130//              hashq_free(cl2->hq, 0, NULL); 
     131                free(cl2->hq); 
     132                cluster_free(cl2, 0, NULL); 
     133                num_of_clusters--; 
     134 
     135                return(dst); 
     136} 
     137 
     138 
     139void clusterlist_delete(cluster *list, u_char list_files) { 
     140        cluster         *cl; 
    76141 
    77142        while(list) { 
    78143                cl = list; 
    79                 printf("Cluster has %u entries.\n", cl->cnt); 
    80                 if (list_files) 
    81                         for (i=0; i<cl->cnt; printf("   %s\n", cl->entries[i++]->filename)); 
    82                  
    83                 free(list->entries); 
    84144                list = cl->next; 
    85                 free(cl); 
     145                printf("Cluster has %u entries.\n", cl->hq->size); 
     146                cluster_free(cl, list_files, cluster_hashq_free); 
    86147        } 
    87148} 

  • nebula/trunk/src/cluster.h

    r1375 r1414  
    2828#include <stdlib.h> 
    2929 
    30 #include "hashlist.h" 
     30#include "hashq.h" 
    3131#include "trie.h" 
    3232 
    …… 
    3636typedef struct cluster { 
    3737        u_int16_t cnt; 
     38        struct cluster *prev; 
    3839        struct cluster *next; 
    39         hash_list **entries; 
     40        hashq *hq; 
    4041} cluster; 
    4142 
    4243 
    43 cluster *extend_cluster(hash_list *md5sum1, hash_list *md5sum2); 
    44 void clusterlist_delete(cluster *list); 
     44inline cluster *create_hashlist(hash *hl1, hash *hl2); 
     45cluster *add_entry_to_cluster(cluster *cl, hash *entry); 
     46cluster *create_cluster(hash *l1, hash *l2); 
     47cluster *clusters_merge(cluster *dst, cluster *new); 
     48void clusterlist_delete(cluster *list, u_char list_files); 
    4549 
    4650#endif 

  • nebula/trunk/src/nebula.c

    r1375 r1414  
    2828#include <sys/stat.h> 
    2929#include <sys/types.h> 
     30#include <sys/queue.h> 
    3031#include <string.h> 
    3132#include <unistd.h> 
    3233 
    3334#include "cluster.h" 
    34 #include "hashlist.h" 
    3535#include "md5.h" 
    3636#include "nebula.h" 
    …… 
    4848 
    4949int main(int argc, char *argv[]) { 
    50         int             i; 
     50        int             i, qsize, show_progress; 
    5151        u_char          *content, *tmpbuf; 
    5252        FILE            *md5sum_file, *spamsum_file; 
     53        char            option, *curfile; 
     54        struct dirent   *dir_entry; 
     55        struct stat     statbuf; 
     56        hash            *tmp_hash; 
     57        qelem           *cur_hq, *tmp_hq; 
     58        cluster         *cl; 
     59        double          score; 
    5360        DIR             *dirp; 
    5461        trie_node       *t; 
    5562        bstring         bstr; 
    56         char            option, *curfile; 
    57         struct dirent   *dir_entry; 
    58         struct stat     statbuf; 
    59         ss_match        spamsum_match; 
    60         hash_list       *md5sum1, *md5sum2, *spamsum1, *spamsum2; 
    61         cluster         *cl; 
     63 
    6264 
    6365        spamsum_file    = NULL; 
    …… 
    6567        dirp            = NULL; 
    6668 
    67         spamsum_list    = NULL; 
    68         md5sum_list     = NULL; 
     69        outlierq        = NULL; 
    6970        cluster_list    = NULL; 
    7071 
    7172        content         = NULL; 
    72         verbose         = 0; 
    73         list_files      = 0; 
    7473        num_of_files    = 0; 
    7574        num_of_clusters = 0; 
    76         cluster_radius  = 95.0; 
    7775        i               = 0; 
    78  
    79         memset(&spamsum_trie, 0, sizeof(trie_node)); 
     76        qsize           = 0; 
     77        total_files     = 0; 
     78 
     79        /* default values for parameters */ 
     80        verbose                 = 0;    // don't be verbose 
     81        show_progress           = 0;    // don't show progress dots 
     82        list_files              = 0;    // don't list cluster objects 
     83        cluster_radius          = 95.0; // 95% similarity as cluster criteria 
     84        outlierq_max            = 500000; 
     85        clusterq_max            = 500000; 
     86 
    8087        memset(&md5sum_trie, 0, sizeof(trie_node)); 
    81         memset(&spamsum_match, 0, sizeof(ss_match)); 
    8288 
    8389        // process args 
    84         while((option = getopt(argc, argv, "lvd:r:h?")) > 0) { 
     90        while((option = getopt(argc, argv, "c:q:plvd:r:h?")) > 0) { 
    8591                switch(option) { 
     92                        case 'c': 
     93                                clusterq_max = atoi(optarg); 
     94                                if (clusterq_max < 2) { 
     95                                        fprintf(stderr, "Error - Maximum cluster size must be at least 2.\n"); 
     96                                        exit(EXIT_FAILURE); 
     97                                } 
     98                                break; 
    8699                        case 'd': 
    87100                                if ((dirp = opendir(optarg)) == NULL) { 
    …… 
    104117                                } 
    105118                                break; 
     119                        case 'q': 
     120                                outlierq_max = atoi(optarg); 
     121                                if (outlierq_max < 1) { 
     122                                        fprintf(stderr, "Error - Outlier queue size must be a non-negative value.\n"); 
     123                                        exit(EXIT_FAILURE); 
     124                                } 
     125                                break; 
     126                        case 'p': 
     127                                show_progress = 1; 
     128                                break; 
    106129                        case 'v': 
    107130                                verbose = 1; 
    …… 
    117140        set_signal_handlers(); 
    118141 
     142        /* initialize outlier queue */ 
     143        outlierq = hashq_new(); 
     144 
    119145        if (!dirp) { 
    120146                if ((argc - optind) < 1) usage(argv[0], EXIT_FAILURE); 
    …… 
    122148        } 
    123149 
     150        if (dirp) { 
     151                while ((dir_entry = readdir(dirp)) != NULL) if (dir_entry->d_type == 8) total_files++; 
     152                rewinddir(dirp); 
     153                printf("processing %u files.\n", (unsigned int) total_files); 
     154        } 
     155 
     156        if (!verbose && show_progress) { 
     157                printf("files processed:                       "); 
     158                fflush(stdout); 
     159        } 
     160 
    124161        // process files 
    125162        for (;;) { 
     163                // get next file content 
    126164                if (dirp) { 
    127165                        if ((dir_entry = readdir(dirp)) == NULL) break; 
    …… 
    138176                } 
    139177 
    140                 if (verbose) printf("  file %s:\n", curfile); 
    141  
    142178                bstr = bstr_map(curfile); 
    143179                num_of_files++; 
    144180 
    145                 md5sum1         = NULL; 
    146                 md5sum2         = NULL; 
    147                 spamsum1        = NULL; 
    148                 spamsum2        = NULL; 
    149                 cl              = NULL; 
    150  
    151                 // build md5sum trie 
     181                if (verbose) printf("  processing file %s.\n", curfile); 
     182                else if (show_progress) { 
     183                        printf("\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b"); 
     184                        if (num_of_files < total_files) 
     185                                printf("%05.2f%% (%04d clusters)", num_of_files/total_files*100, num_of_clusters); 
     186                        else 
     187                                printf("100.00%% (%04d clusters)\n", num_of_clusters); 
     188                        fflush(stdout); 
     189                } 
     190 
     191 
     192                // calculate md5sum 
    152193                if ((tmpbuf = (u_char *) mem_md5sum(bstr.data, bstr.len)) == NULL) { 
    153194                        fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
    154195                        exit(EXIT_FAILURE); 
    155196                } 
     197 
    156198                if ((t = trie_find_memstr(&md5sum_trie, tmpbuf, strlen((char *)tmpbuf))) != NULL) { 
     199                    
    157200                        // md5sum is already in trie 
    158201                        free(tmpbuf); 
    159                         ((hash_list*)t->data)->cnt++; 
    160                         if (verbose) printf("    md5sum is %s (%u instances)\n", ((hash_list*)t->data)->hash, ((hash_list*)t->data)->cnt); 
     202                        ((hash*)t->data)->cnt++; 
     203                        if (verbose) printf("    md5sum is %s (%u instances)\n", ((hash*)t->data)->md5sum, ((hash*)t->data)->cnt); 
    161204                        if (verbose) printf("    absolute match found.\n"); 
    162  
    163                         /* increase cluster counter */ 
    164 //                      if (((hash_list*)t->data)->cl) ((hash_list*)t->data)->cl->cnt++; 
    165205                } else { 
    166                         // insert md5sum into trie 
     206                        // md5sum not in trie, create new element 
    167207                        t = trie_memins(&md5sum_trie, tmpbuf, strlen((char *)tmpbuf), NULL); 
    168                         md5sum_list = t->data = hashlist_new_entry(md5sum_list); 
    169                         md5sum2 = (hash_list*)t->data; 
    170  
    171                         ((hash_list*)t->data)->hashlen = strlen((char *)tmpbuf); 
    172                         ((hash_list*)t->data)->hash = (char *) tmpbuf; 
    173                         ((hash_list*)t->data)->cnt++; 
    174                         if ((((hash_list*)t->data)->filename = strdup(curfile)) == NULL) { 
     208                        if ((t->data = calloc(1, sizeof(hash))) == NULL) { 
    175209                                fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
    176                         } 
    177                         if (verbose) printf("    md5sum is %s (%u instances)\n", md5sum2->hash, md5sum2->cnt); 
    178  
    179  
    180                         // build spamsum trie 
    181                         if ((tmpbuf = (u_char *) spamsum(bstr.data, bstr.len, 0)) == NULL) { 
     210                                exit(EXIT_FAILURE); 
     211                        } 
     212                        ((hash*)t->data)->hashlen = 32; 
     213                        ((hash*)t->data)->md5sum = (char *) tmpbuf; 
     214                        ((hash*)t->data)->cnt++; 
     215                        // set filename 
     216                        if ((((hash*)t->data)->filename = strdup(curfile)) == NULL) { 
     217                                fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
     218                                exit(EXIT_FAILURE); 
     219                        } 
     220                        // set spamsum hash 
     221                        if ((((hash*)t->data)->spamsum = spamsum(bstr.data, bstr.len, 0)) == NULL) { 
    182222                                fprintf(stderr, "Error - Unable to allocate memoory: %m.\n"); 
    183223                                exit(EXIT_FAILURE); 
    184224                        } 
    185                         if (((t = trie_find_memstr(&spamsum_trie, tmpbuf, strlen((char *)tmpbuf))) != NULL) && (t->data)) { 
    186                                 //spamsum is already in trie 
    187                                 free(tmpbuf); 
    188                                 spamsum_match.score = 100.0; 
    189                                 spamsum_match.entry = (hash_list*)t->data; 
    190                                 spamsum2 = spamsum_match.entry; 
    191                         } else { 
    192                                 // find best match 
    193                                 spamsum_match = spamsum_match_list(spamsum_list, (char *) tmpbuf, 100); 
    194  
    195                                 // insert spamsum 
    196                                 t = trie_memins(&spamsum_trie, tmpbuf, strlen((char *)tmpbuf), NULL); 
    197                                 spamsum_list = t->data = hashlist_new_entry(spamsum_list); 
    198                                 spamsum2 = (hash_list*)t->data; 
    199                                 spamsum2->neighbour_hash = md5sum2; 
    200  
    201                                 ((hash_list*)t->data)->hashlen = strlen((char *)tmpbuf); 
    202                                 ((hash_list*)t->data)->hash = (char *) tmpbuf; 
    203                                 if ((((hash_list*)t->data)->filename = strdup(curfile)) == NULL) { 
    204                                         fprintf(stderr, "Error - Unable to allocate memory: %m.\n"); 
    205                                 } 
    206                         } 
    207                         if (verbose) printf("    highest spamsum match score is %.0f.\n", spamsum_match.score); 
    208                         md5sum2->neighbour_hash = spamsum2; 
    209                         spamsum1 = spamsum_match.entry; 
    210  
    211                         if (spamsum1) { 
    212                                 md5sum1 = spamsum1->neighbour_hash; 
    213  
    214                                 if (spamsum_match.score >= cluster_radius) { 
    215                                         if ((cl = extend_cluster(md5sum1, md5sum2)) == NULL) { 
    216                                                 fprintf(stderr, "Error - Unable to extend cluster.\n"); 
     225                        if (verbose) printf("    md5sum is %s (%u instances)\n", ((hash*)t->data)->md5sum, ((hash*)t->data)->cnt); 
     226 
     227                        // connect all clusters within range 
     228                        for (cl = cluster_list; cl; cl = cl->next) { 
     229                                for (cur_hq = cl->hq->head; cur_hq; cur_hq = cur_hq->next) 
     230                                        if ((score = spamsum_match(((hash*)t->data)->spamsum, ((hash*)cur_hq->data)->spamsum)) >= cluster_radius) { 
     231                                                if (!((hash*)t->data)->cl) { 
     232                                                        add_entry_to_cluster(cl, (hash*)t->data); 
     233                                                        break; 
     234                                                } else { 
     235                                                        if (cl != ((hash*)t->data)->cl) { 
     236                                                                clusters_merge(cl, ((hash*)t->data)->cl); 
     237                                                        } 
     238                                                        break; 
     239                                                } 
     240                                        } 
     241                        } 
     242 
     243                        // connect all outliers within range 
     244                        for (cur_hq = outlierq->head; cur_hq; cur_hq = cur_hq->next) { 
     245                                if ((score = spamsum_match(((hash*)t->data)->spamsum, ((hash*)cur_hq->data)->spamsum)) >= cluster_radius) { 
     246                                        // unlink match from outlier list 
     247                                        tmp_hq = cur_hq; 
     248                                        cur_hq = cur_hq->next; 
     249                                        if ((tmp_hash = hashq_unlink(outlierq, tmp_hq)) == NULL) { 
     250                                                fprintf(stderr, "Error - Unable to unlink outlier from queue.\n"); 
    217251                                                exit(EXIT_FAILURE); 
    218252                                        } 
    219                                         if (verbose) printf("    cluster has now %u elements.\n", cl->cnt); 
    220                                 } 
    221                         } 
    222  
    223                         ((hash_list*)t->data)->cnt++; 
    224                         if (verbose) printf("    spamsum is %s (%u instances)\n", ((hash_list*)t->data)->hash, ((hash_list*)t->data)->cnt); 
    225                 } 
    226  
     253                                        if (((hash*)t->data)->cl) { 
     254                                                // add other outliers to cluster 
     255                                                if (add_entry_to_cluster(((hash*)t->data)->cl, tmp_hash) == NULL) 
     256                                                        hash_free(tmp_hash, 0); 
     257                                        } else { 
     258                                                // create new cluster of two outliers 
     259                                                create_cluster(((hash*)t->data), tmp_hash); 
     260                                        } 
     261                                } 
     262                                if (!cur_hq) break; 
     263                        } 
     264 
     265                                 
     266                        if (verbose) printf("    spamsum is %s (%u instances)\n", ((hash*)t->data)->spamsum, ((hash*)t->data)->cnt); 
     267 
     268                        if (!((hash*)t->data)->cl) { 
     269                                // insert outlier into queue 
     270                                if (outlierq->size >= outlierq_max) { 
     271                                        tmp_hash = hashq_unlink(outlierq, outlierq->tail); 
     272                                        trie_del_memstr(&md5sum_trie, (u_char *) tmp_hash->md5sum, strlen(tmp_hash->md5sum)); 
     273                                        trie_del_memstr(&spamsum_trie, (u_char *) tmp_hash->spamsum, strlen(tmp_hash->spamsum)); 
     274                                        hash_free(tmp_hash, 0); 
     275                                } 
     276                                hashq_ins(outlierq, t->data, outlierq_max); 
     277                        } 
     278                } 
    227279                bstr_unmap(bstr); 
    228280                if (verbose) printf("\n"); 

  • nebula/trunk/src/nebula.h

    r1375 r1414  
    2727 
    2828#include <sys/types.h> 
     29#include <sys/queue.h> 
    2930 
    3031#include "cluster.h" 
     32#include "hashq.h" 
    3133 
    32 u_char  verbose, list_files; 
    33 u_int16_t num_of_files, num_of_clusters; 
    34 double  cluster_radius; 
    35 trie_node spamsum_trie, md5sum_trie; 
    36 cluster *cluster_list; 
     34u_char          verbose, list_files; 
     35int             clusterq_max, outlierq_max;  
     36u_int16_t       num_of_clusters; 
     37float           num_of_files, total_files; 
     38double          cluster_radius; 
     39trie_node       spamsum_trie, md5sum_trie; 
     40cluster         *cluster_list; 
     41hashq           *outlierq; 
    3742 
    3843#endif 

  • nebula/trunk/src/signals.c

    r1376 r1414  
    3030 
    3131void handle_signal(int sig) { 
    32         printf("Premature termination forced.\n"); 
     32        printf("Premature termination forced (signal %d caught).\n", sig); 
    3333        cleanup(); 
    3434        exit(EXIT_SUCCESS); 

  • nebula/trunk/src/spamsum.c

    r1373 r1414  
    2727#include <stdio.h> 
    2828 
    29 #include "hashlist.h" 
    3029#include "spamsum.h" 
    3130 
    …… 
    284283 
    285284 
    286 /* return the maximum match for a linked list containing a list of spamsums */ 
    287 ss_match spamsum_match_list(hash_list *list, const char *sum, u_int32_t threshold) { 
    288         ss_match        rv; 
    289         u_int32_t       score, best; 
    290  
    291         score   = 0; 
    292         best    = 0; 
    293         memset(&rv, 0, sizeof(ss_match)); 
    294  
    295         while (list) { 
    296                 score = spamsum_match(sum, list->hash); 
    297                 if (score >= best) { 
    298                         best            = score; 
    299                         rv.score        = best; 
    300                         rv.entry        = list; 
    301                         if (best >= threshold) break; 
    302                 } 
    303                 list = list->next; 
    304         } 
    305  
    306         return(rv); 
    307 } 
    308  
    309  
    310285/* return the maximum match for a file containing a list of spamsums */ 
    311286u_int32_t spamsum_match_db(const char *fname, const char *sum, u_int32_t threshold) { 
    …… 
    413388           100 being a excellent match. */ 
    414389        score = 100 - score; 
    415  
    416         /* when the blocksize is small we don't want to exaggerate the match size */ 
    417         if (score > block_size/MIN_BLOCKSIZE * MIN(len1, len2)) { 
    418                 score = block_size/MIN_BLOCKSIZE * MIN(len1, len2); 
    419         } 
    420390 
    421391        return score; 

  • nebula/trunk/src/spamsum.h

    r1373 r1414  
    2626#endif 
    2727 
    28 #include "hashlist.h" 
    29  
    30 typedef struct ss_match { 
    31         double          score; 
    32         hash_list       *entry; 
    33 } ss_match; 
     28#include "hashq.h" 
    3429 
    3530char *spamsum(const u_char *in, size_t length, u_int32_t bsize); 
    3631u_int32_t spamsum_match(const char *str1, const char *str2); 
    37 ss_match spamsum_match_list(hash_list *list, const char *sum, u_int32_t threshold); 
    3832u_int32_t spamsum_match_db(const char *fname, const char *sum, u_int32_t threshold); 
    3933 

  • nebula/trunk/src/trie.c

    r1376 r1414  
    3030 
    3131 
     32void print_trie(const trie t, int depth) { 
     33        int i, j; 
     34        for(i=0; i<t->childlist_len; i++) { 
     35                if (t->childlist_len > 1) for (j=0; j<depth; j++) printf(" "); 
     36                putchar(t->childlist[i].key); 
     37                print_trie(&t->childlist[i], depth+1); 
     38                if (t->childlist_len > 1) putchar('\n'); 
     39        } 
     40        return; 
     41} 
     42 
     43 
    3244/* find and return trie node for key */ 
    3345trie trie_find_node(const trie t, const u_int16_t size, const u_char key) { 
    …… 
    3547        u_int16_t high, low; 
    3648         
    37         if (t == NULL) return(NULL); 
     49        if (t == NULL || size == 0) return(NULL); 
    3850 
    3951        for (low=0, high=(size-1); high-low>0; ) { 
    …… 
    5567 
    5668        node = t; 
    57         for (k=0; k<n && node != NULL; k++) 
     69        for (k=0; k<n && node != NULL; k++) { 
    5870                node = trie_find_node(node->childlist, node->childlist_len, data[k]); 
     71                if (node);// printf("%d: node is '%c'\n", k, node->key); 
     72                else break; 
     73        } 
    5974         
    6075        return(node); 
     76} 
     77 
     78 
     79/* delete a path from a trie */ 
     80int trie_del_memstr(trie t, const u_char* data, u_int16_t n) { 
     81        u_int16_t i = 0; 
     82        u_int16_t high, low; 
     83        trie node = t; 
     84 
     85        if (!t || !data)        return(0); 
     86        if (!t->childlist)      return(1); 
     87 
     88        i = 0; 
     89        for (low=0, high=(node->childlist_len-1); high-low>0; ) { 
     90                i = (high+low)/2; 
     91                if (*data <= node->childlist[i].key) high = i; 
     92                else{ 
     93                        i = (high+low+1)/2; 
     94                        low = i; 
     95                } 
     96        } 
     97 
     98        if (node->childlist[i].key == data[0]) { 
     99                /* check subtrie recursively */ 
     100                if (!trie_del_memstr(&node->childlist[i], &data[1], n-1)) return(0); 
     101 
     102                /* if subpath was deleted, delete node from childlist */ 
     103                node->childlist_len--; 
     104                if (node->childlist_len) { 
     105                        if (node->childlist_len > i) memmove(&(node->childlist[i]), &(node->childlist[i+1]), (node->childlist_len-i) * sizeof(trie_node)); 
     106                        if ((node->childlist = realloc(node->childlist, node->childlist_len * sizeof(trie_node))) == NULL) { 
     107                                fprintf(stderr, "Error - Unable to reallocate memory: %m.\n"); 
     108                                exit(EXIT_FAILURE); 
     109                        } 
     110                        return(0); 
     111                } else { 
     112                        free(node->childlist); 
     113                        node->childlist = NULL; 
     114                        return(1); 
     115                } 
     116        } 
     117 
     118        return(0); 
    61119} 
    62120 

  • nebula/trunk/src/trie.h

    r1373 r1414  
    3737 
    3838 
     39void print_trie(const trie t, int depth); 
     40 
    3941trie trie_find_node(const trie t, const u_int16_t size, const u_char key); 
    4042trie trie_find_memstr(trie t, const u_char* data, u_int16_t n); 
     43int trie_del_memstr(trie t, const u_char* data, u_int16_t n); 
    4144trie trie_insert_node(trie parent, const u_char key); 
    4245trie trie_memins(trie t, const u_char *data, ssize_t n, void(*cbfn)(trie t)); 

  • nebula/trunk/src/util.c

    r1375 r1414  
    2828 
    2929#include "cluster.h" 
     30#include "hashq.h" 
    3031#include "nebula.h" 
    3132#include "trie.h" 
    …… 
    7576void cleanup(void) { 
    7677        // free data structures 
    77         printf("%u files form %u clustes.\n-----------------------\n", num_of_files, num_of_clusters); 
    78         clusterlist_delete(cluster_list); 
     78        printf("%u files form %u clustes.\n-----------------------\n", (unsigned int) num_of_files, num_of_clusters); 
    7979 
    80         hashlist_delete(spamsum_list); 
    81         hashlist_delete(md5sum_list); 
     80        hashq_free(outlierq, 0, hash_free); 
     81        clusterlist_delete(cluster_list, list_files); 
     82        trie_delete(md5sum_trie.childlist, md5sum_trie.childlist_len, NULL); 
    8283        trie_delete(spamsum_trie.childlist, spamsum_trie.childlist_len, NULL); 
    83         trie_delete(md5sum_trie.childlist, md5sum_trie.childlist_len, NULL); 
    8484         
    8585        return; 

  • nebula/trunk/src/util.h

    r1375 r1414  
    2727 
    2828typedef struct bstring { 
    29         u_int16_t len; 
     29        u_int32_t len; 
    3030        u_char *data; 
    3131} bstring;