"Fossies" - the Fresh Open Source Software Archive

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

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