#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Location
    Cape Town, South Africa
    Posts
    13
    Rep Power
    0

    Question qsort and bsearch


    I am reading in domain names from a squid access log (obviously I have converted the URLs to domains) and have to find a faster method of comparing domains in a user's list. What this program does is compares incoming domain names with domain names that are stored in the logcache_user struct - if the domain does not exist, an addentry function is called.

    Initially I just stored the domain names in sequential order and used [I] if((user->data[i]->ip == ip) && (user->data[i]->cost == c)) && (strcmp(user->data->domain, domain) == 0)) but that ended up slowing the whole program down, as there could be 14000+ users in the cache.

    So I though about using a quicksort
    Code:
    void logcache_addentry(logcache_user *user, unsigned long ip, double cost, unsigned long ltime, char *domain)
    {
                                 .
                                 .
                                 .
    
    printf("\n\n UNSORTED User:     %s\n", user->user);
                     for (i=0;i<user->count && !data;i++)
                             printf("Domain[%i]: %s\n",i,user->data[i]->domain);
                                                                                                                                                                                        
                      if (user->dcount >= 1)
                      {
                             printf("\n\n SORTED User:     %s        DCOUNT:         %i\n", user->user,user->dcount);
                             qsort(user->data[0]->domain,user->dcount,sizeof(logcache_user *),comp);
                                      for (i=0;i<user->dcount && !data;i++)
                                                   printf("Domain[%i]: %s\n",i,user->data[i]->domain);
                      }
     
     
     
     
     
                    user->dcount = user->dcount+1;
            }
    }
    Code:
    logcache_userdata *logcache_getentry(logcache_user *user, unsigned long ip, double cost, char *domain)
    {
            char *key, **key1 = NULL;
            char *ptr = NULL;
            int i=0;
            int c = (cost *100);
                                                                                                                                                                                        
            logcache_userdata *data = NULL;
                                                                                                                                                                                        
            for(i=0;i<user->count && !data;i++) {
                    if((user->data[i]->ip == ip) && (user->data[i]->cost == c)) // && (strcmp(user->data[i]->domain, domain) == 0))
                    {
                            key = domain;
                            key1 = &key;
                            ptr = bsearch(key1,user->data[0]->domain,sizeof(logcache_user *),comp);
                            if (ptr != NULL)
                            {
                                    data = user->data[i];
                                    data->domain = domain;
                                    free(key);
                                    free(ptr);
                            }
                            else
                            {
                                    printf("Domain not found\n\n");
                            }
                    }
            }
                                                                                                                                                                                        
            return data;
    }
    I get the following error when I try to compile:

    gcc -I../include -I/usr/local/include -c -o logcache.o logcache.c
    logcache.c: In function `logcache_getentry':
    logcache.c:222: warning: passing arg 4 of `bsearch' makes integer from pointer without a cast
    logcache.c:222: too few arguments to function `bsearch'
    gmake: *** [logcache.o] Error 1


    Any help would be greatly appreciated
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    55
    Rep Power
    11
    The bsearch function prototype would be helpful, as would the declaration of "comp." I would imagine the most likely fix is passing &comp. But as I said I/we need declaration & prototype to be sure.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Location
    Cape Town, South Africa
    Posts
    13
    Rep Power
    0
    bsearch is part of the C standard library.

    bsearch prototype is:
    Code:
    void *bsearch(const void *key,const void *base,size_t num, size_t width, int (*comp)(void *element1, void *element2));
    Code:
    int comp(const void *s1, const void *s2)
    {
        //    printf("\nComparing     %s      AND     %s\n\n",*(char **)s1,*(char **)s2);
            return (strcmp(*(char **)s1, *(char **)s2));
    }
    I found the answer: I forgot to pass the size_t num parameter, so here is how it should look:

    Code:
    ptr = bsearch(key1,user->data[0]->domain,user->dcount,sizeof(logcache_user *),comp);
    user->dcount keeps track of the number of new domains being added to the list; however i am now just getting segmentation faults

IMN logo majestic logo threadwatch logo seochat tools logo