"Fossies" - the Fresh Open Source Software Archive

Member "FunctionCheck-3.2.0/src/fcmanager/fc_xlhash.c" (26 May 2012, 11231 Bytes) of package /linux/privat/old/FunctionCheck-3.2.0.tar.gz:

    1 #include "fc_tools.h"
    2 #include "fc_xlhash.h"
    3 
    4 /* list of prime numbers to compute size of the hash-table */
    5 static const unsigned int fc_primes[] ={
    6     109,
    7     163,
    8     251,
    9     367,
   10     557,
   11     823,
   12     1237,
   13     1861,
   14     2777,
   15     4177,
   16     6247,
   17     9371,
   18     14057,
   19     21089,
   20     31627,
   21     47431,
   22     71143,
   23     106721,
   24     160073,
   25     240101,
   26     360163,
   27     540217,
   28     810343,
   29     1215497,
   30     1823231,
   31     2734867,
   32     4102283,
   33     6153409,
   34     9230113,
   35     13845163,
   36 };
   37 
   38 static const unsigned fc_nprimes = sizeof (fc_primes) / sizeof (fc_primes[0]);
   39 
   40 /* gives the nearest prime number */
   41 static unsigned int fc_spaced_primes_closest(unsigned int num)
   42 {
   43     unsigned int i;
   44 
   45     for (i = 0; i < fc_nprimes; i++)
   46         if (fc_primes[i] > num)
   47             return (fc_primes[i]);
   48 
   49     return (fc_primes[fc_nprimes - 1]);
   50 }
   51 
   52 /* gives the first prime number */
   53 #define fc_first_prime_number() (fc_primes[0])
   54 
   55 /* (!) create a hash-table */
   56 FC_LHash *fc_lhash_new(void)
   57 {
   58     FC_LHash *hash;
   59     int i;
   60 
   61     hash = malloc(sizeof (FC_LHash));
   62     if (hash == NULL)
   63     {
   64         fc_message("cannot allocate a lhash-table");
   65         return NULL;
   66     }
   67     /* create the initial list of nodes */
   68     hash->nodes = calloc(fc_first_prime_number(), sizeof (FC_LHNode*));
   69     if (hash->nodes == NULL)
   70     {
   71         fc_message("cannot allocate nodes list for a lhash-table");
   72         free(hash);
   73         return NULL;
   74     }
   75 
   76     /* create the initial nodes */
   77     hash->nb_rnodes = 0;
   78     hash->max_rnodes = 64;
   79     hash->rnodes = calloc(hash->max_rnodes, sizeof (FC_LHNode));
   80     if (hash->rnodes == NULL)
   81     {
   82         fc_message("cannot allocate nodes for a lhash-table");
   83         free(hash->rnodes);
   84         free(hash);
   85         return NULL;
   86     }
   87 
   88     /* initialize the nodes */
   89     for (i = 0; i < hash->max_rnodes; i++)
   90     {
   91         hash->rnodes[i].fnext = i < hash->max_rnodes - 1 ? &(hash->rnodes[i + 1]) : NULL;
   92     }
   93     hash->free_entry = &(hash->rnodes[0]);
   94 
   95     /* initialize the elements */
   96     hash->size = fc_first_prime_number();
   97     hash->nb = 0;
   98     hash->frozen = 0;
   99     hash->nb_add_rnodes = 0;
  100     for (i = 0; i < FC_LHASH_MAX_ADD; i++)
  101     {
  102         hash->add_rnodes[i] = NULL;
  103     }
  104 
  105     return hash;
  106 }
  107 
  108 /* (!) destroy a hash-table */
  109 void fc_lhash_destroy(FC_LHash *hash)
  110 {
  111     int i;
  112 
  113     if (hash == NULL)
  114         return;
  115 
  116     if (hash->nodes != NULL)
  117         free(hash->nodes);
  118     if (hash->rnodes != NULL)
  119         free(hash->rnodes);
  120     for (i = 0; i < hash->nb_add_rnodes; i++)
  121     {
  122         if (hash->add_rnodes[i] != NULL)
  123             free(hash->add_rnodes[i]);
  124     }
  125     free(hash);
  126 }
  127 
  128 /* (!) found a free entry in the rnode list */
  129 static FC_LHNode *fc_lhash_get_a_node(FC_LHash *hash)
  130 {
  131     FC_LHNode *tmp;
  132     int i;
  133 
  134     /* get the next available node */
  135     tmp = hash->free_entry;
  136     /* this entry is no more free */
  137     hash->free_entry = tmp->fnext;
  138 
  139     hash->nb_rnodes++;
  140 
  141     /* no more entry available (after this one) */
  142     if (hash->free_entry == NULL)
  143     {
  144         /* reallocation of the list */
  145 
  146         /* no more blocks of nodes available */
  147         if (hash->nb_add_rnodes == FC_LHASH_MAX_ADD)
  148         {
  149             /* nax number of node blocks */
  150             fc_message("no more block of nodes availalbe. LTable destroyed.");
  151             fc_lhash_destroy(hash);
  152             return NULL;
  153         }
  154 
  155         /* allocate a new block of nodes */
  156         hash->add_rnodes[hash->nb_add_rnodes] =
  157                 malloc(sizeof (FC_LHNode)*(2 * hash->max_rnodes));
  158         if (hash->add_rnodes[hash->nb_add_rnodes] == NULL)
  159         {
  160             fc_message("cannot reallocate nodes for a lhash-table. Table destroyed.");
  161             fc_lhash_destroy(hash);
  162             return NULL;
  163         }
  164 
  165         /* initialize the new list of nodes */
  166         for (i = 0; i < 2 * hash->max_rnodes; i++)
  167         {
  168             hash->add_rnodes[hash->nb_add_rnodes][i].fnext =
  169                     (i < 2 * hash->max_rnodes - 1) ? &(hash->add_rnodes[hash->nb_add_rnodes][i + 1]) : NULL;
  170         }
  171         hash->free_entry = &(hash->add_rnodes[hash->nb_add_rnodes][0]);
  172         hash->max_rnodes *= 2;
  173         hash->nb_add_rnodes++;
  174     }
  175 
  176     return tmp;
  177 }
  178 
  179 /* insert the given node in the temporary list */
  180 
  181 /* the field fnext is used to keep the new links */
  182 static void fc_lhash_insert_known(FC_LHNode **nodes, FC_LHNode *nd, int size)
  183 {
  184     int index;
  185     FC_LHNode *tmp;
  186 
  187     /* compute its new index */
  188     index = (unsigned int) (nd->key % size);
  189 
  190     nd->next = NULL;
  191     if (nodes[index] == NULL)
  192     {
  193         nodes[index] = nd;
  194     }
  195     else
  196     {
  197         tmp = nodes[index];
  198         while (tmp->next != NULL)
  199         {
  200             tmp = tmp->next;
  201         }
  202         tmp->next = nd;
  203     }
  204 }
  205 
  206 /* (!) increase the size of the hash-table */
  207 static void fc_lhash_increase_size(FC_LHash *hash)
  208 {
  209     FC_LHNode **new_nodes = NULL, *tmp = NULL;
  210     int new_size = 0;
  211     int i;
  212 
  213     if (hash->frozen)
  214         return;
  215 
  216     /* to prevent re-calls to this functions */
  217     hash->frozen = 1;
  218 
  219     new_size = (int) fc_spaced_primes_closest((unsigned int) hash->size);
  220 
  221     /* create the new list */
  222     new_nodes = calloc(new_size, sizeof (FC_LHNode*));
  223 
  224     /* for each existing entry, re-hash it in the new table */
  225     for (i = 0; i < hash->size; i++)
  226     {
  227         tmp = hash->nodes[i];
  228         while (tmp != NULL)
  229         {
  230             /* remove it from the current list */
  231             hash->nodes[i] = tmp->next;
  232             /* and re-insert it in the table (without creation) */
  233             fc_lhash_insert_known(new_nodes, tmp, new_size);
  234 
  235             /* agin until this part is empty */
  236             tmp = hash->nodes[i];
  237         }
  238     }
  239 
  240     /* replace the new list */
  241     hash->nodes = new_nodes;
  242     hash->size = new_size;
  243 
  244     hash->frozen = 0;
  245 }
  246 
  247 /* debug */
  248 void fc_lhash_debug(FC_LHash *hash)
  249 {
  250     int i;
  251     FC_LHNode *tmp;
  252 
  253     if (hash == NULL)
  254         return;
  255 
  256     for (i = 0; i < hash->size; i++)
  257     {
  258         printf("Point %d: [%p]\n", i, hash->nodes[i]);
  259         tmp = hash->nodes[i];
  260         while (tmp != NULL)
  261         {
  262             printf("k=%llu [%p] : ", tmp->key, tmp);
  263             tmp = tmp->next;
  264         }
  265         printf("\n");
  266     }
  267 }
  268 
  269 /* returns the corresp. node if any */
  270 static FC_LHNode *fc_lhash_lookup_node(FC_LHash *hash, unsigned long long key)
  271 {
  272     int index;
  273     FC_LHNode *tmp;
  274 
  275     if ((hash == NULL) || (key == 0))
  276         return NULL;
  277 
  278     /* compute the hash position */
  279     index = (unsigned int) (key % hash->size);
  280 
  281     tmp = hash->nodes[index];
  282 
  283     while (tmp != NULL)
  284     {
  285         if (tmp->key == key)
  286         {
  287             return (tmp);
  288         }
  289         tmp = tmp->next;
  290     }
  291 
  292     /* not found */
  293     return NULL;
  294 }
  295 
  296 /* (!) insert an element in a hash-table */
  297 void fc_lhash_insert(FC_LHash *hash, unsigned long long key,
  298                      int val, void *ptr1, void *ptr2)
  299 {
  300     int index;
  301     FC_LHNode *tmp, *pos;
  302 
  303     if ((hash == NULL) || (key == 0))
  304         return;
  305 
  306     /* first try to get the element */
  307     tmp = fc_lhash_lookup_node(hash, key);
  308 
  309     /* still here, just modify it */
  310     if (tmp != NULL)
  311     {
  312         tmp->key = key;
  313         tmp->value = val;
  314         tmp->ptr1 = ptr1;
  315         tmp->ptr2 = ptr2;
  316         return;
  317     }
  318 
  319     /* compute the hash position */
  320     index = (unsigned int) (key % hash->size);
  321 
  322     /* get a new node */
  323     tmp = fc_lhash_get_a_node(hash);
  324     tmp->key = key;
  325     tmp->value = val;
  326     tmp->ptr1 = ptr1;
  327     tmp->ptr2 = ptr2;
  328 
  329     /* insert it */
  330     tmp->next = NULL;
  331     if (hash->nodes[index] == NULL)
  332     {
  333         hash->nodes[index] = tmp;
  334     }
  335     else
  336     {
  337         pos = hash->nodes[index];
  338         while (pos->next != NULL)
  339         {
  340             pos = pos->next;
  341         }
  342         pos->next = tmp;
  343     }
  344 
  345     /* one more element */
  346     hash->nb++;
  347 
  348     /* if the number of element is too high, resize */
  349     if ((float) hash->nb / hash->size > 0.85)
  350     {
  351         fc_lhash_increase_size(hash);
  352     }
  353 }
  354 
  355 /* (!) search an element in a hash-table */
  356 int fc_lhash_lookup(FC_LHash *hash, unsigned long long key,
  357                     int *val, void **ptr1, void **ptr2)
  358 {
  359     int index;
  360     FC_LHNode *tmp;
  361 
  362     if ((hash == NULL) || (key == 0))
  363         return 0;
  364 
  365     /* compute the hash position */
  366     index = (unsigned int) (key % hash->size);
  367 
  368     tmp = hash->nodes[index];
  369 
  370     while (tmp != NULL)
  371     {
  372         if (tmp->key == key)
  373         {
  374             *val = tmp->value;
  375             *ptr1 = tmp->ptr1;
  376             *ptr2 = tmp->ptr2;
  377             return 1;
  378         }
  379         tmp = tmp->next;
  380     }
  381 
  382     return 0;
  383 }
  384 
  385 /* (!) search an element in a hash-table and return pointers
  386    on the entries (in order to modify their values without
  387    having to remove/modify/insert.
  388    WARNING: these pointers are only valid until you perfom
  389             an other action on this hash-table. after any
  390             operation they may become invalid */
  391 int fc_lhash_lookup_modify(FC_LHash *hash, unsigned long long key,
  392                            int **val, void ***ptr1, void ***ptr2)
  393 {
  394     int index;
  395     FC_LHNode *tmp;
  396 
  397     if ((hash == NULL) || (key == 0))
  398         return 0;
  399 
  400     /* compute the hash position */
  401     index = (unsigned int) (key % hash->size);
  402 
  403     tmp = hash->nodes[index];
  404 
  405     while (tmp != NULL)
  406     {
  407         if (tmp->key == key)
  408         {
  409             *val = &(tmp->value);
  410             *ptr1 = &(tmp->ptr1);
  411             *ptr2 = &(tmp->ptr2);
  412             return 1;
  413         }
  414         tmp = tmp->next;
  415     }
  416 
  417     *val = NULL;
  418     *ptr1 = NULL;
  419     *ptr2 = NULL;
  420     return 0;
  421 }
  422 
  423 /* (!) remove an element from a hash-table */
  424 void fc_lhash_remove(FC_LHash *hash, unsigned long long key)
  425 {
  426     unsigned int index;
  427     FC_LHNode *tmp, *otmp;
  428 
  429     if ((hash == NULL) || (key == 0))
  430         return;
  431 
  432     /* compute the hash position */
  433     index = (unsigned int) (key % hash->size);
  434 
  435     otmp = NULL;
  436     tmp = hash->nodes[index];
  437 
  438     while (tmp != NULL)
  439     {
  440         if (tmp->key == key)
  441         {
  442             /* the old one points to the current next */
  443             if (otmp != NULL)
  444             {
  445                 otmp->next = tmp->next;
  446             }
  447             else
  448             {
  449                 /* the first */
  450                 hash->nodes[index] = tmp->next;
  451             }
  452             /* add the node in the free list */
  453             tmp->fnext = hash->free_entry;
  454             hash->free_entry = tmp;
  455             tmp->key = 0;
  456             hash->nb--;
  457 
  458             /* done */
  459             return;
  460         }
  461         /* next entry */
  462         otmp = tmp;
  463         tmp = tmp->next;
  464     }
  465 
  466     /* entry not found */
  467 }
  468 
  469 /* (!) apply a function to each elements of the hash-table */
  470 void fc_lhash_foreach(FC_LHash *hash, FC_LHFunc func, void *data)
  471 {
  472     int i;
  473     FC_LHNode *tmp;
  474 
  475     if ((hash == NULL) || (func == NULL))
  476         return;
  477 
  478     /* for each list */
  479     for (i = 0; i < hash->size; i++)
  480     {
  481         tmp = hash->nodes[i];
  482         while (tmp != NULL)
  483         {
  484             (func) (tmp->key, tmp->value, tmp->ptr1,
  485                     tmp->ptr2, data);
  486 
  487             tmp = tmp->next;
  488         }
  489     }
  490 }
  491 
  492 /* (!) get the number of elements in the hash-table */
  493 int fc_lhash_size(FC_LHash *hash)
  494 {
  495     if (hash == NULL)
  496         return (0);
  497     return (hash->nb);
  498 }