home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / map < prev    next >
Text File  |  1992-07-21  |  11KB  |  466 lines
  1. /*      > C.Map - Map data type */
  2.  
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "map.h"
  7.  
  8. #ifdef test
  9. #include <stdio.h>
  10. #endif
  11.  
  12. /* Return values from functions */
  13.  
  14. #define OK      1
  15. #define ERR     0
  16.  
  17. /* Utility function - find a binding in a map */
  18.  
  19. static link find (const map m, const void *domain, int *bucket, link *prev)
  20. {
  21.         link this;
  22.         link p;
  23.         int i;
  24.  
  25.         p = NULL;
  26.         i = (m->hash)(domain) % m->buckets;
  27.  
  28.         if ( bucket != NULL )
  29.                 *bucket = i;
  30.  
  31.         this = m->bucket[i];
  32.  
  33.         while ( this != NULL )
  34.         {
  35.                 if ( memcmp(domain,this->data,m->domain_size) == 0 )
  36.                 {
  37.                         if ( prev != NULL )
  38.                                 *prev = p;
  39.  
  40.                         return this;
  41.                 }
  42.                 else
  43.                 {
  44.                         p = this;
  45.                         this = this->next;
  46.                 }
  47.         }
  48.  
  49.         if ( prev != NULL )
  50.                 *prev = p;
  51.  
  52.         return NULL;
  53. }
  54.  
  55. /* General component routines */
  56.  
  57. map map_new (int domain_len, int range_len, int buckets, int (*hash)(const void *))
  58. {
  59.         register map m;
  60.         int i;
  61.  
  62.         m = malloc(sizeof(struct map));
  63.  
  64.         if ( m == NULL )
  65.                 return NULL;
  66.  
  67.         m->bucket = malloc(buckets * ( sizeof(struct link) - 1 ));
  68.         if ( m->bucket == NULL )
  69.         {
  70.                 free(m);
  71.                 return NULL;
  72.         }
  73.  
  74.         for ( i = 0; i < buckets; ++i )
  75.                 m->bucket[i] = NULL;
  76.  
  77.         m->hash = hash;
  78.         m->buckets = buckets;
  79.         m->domain_size = domain_len;
  80.         m->range_size = range_len;
  81.  
  82.         return m;
  83. }
  84.  
  85. void map_free (map m)
  86. {
  87.         map_clear(m);
  88.         free(m->bucket);
  89.         free(m);
  90. }
  91.  
  92. void map_clear (map m)
  93. {
  94.         int i;
  95.         link this_entry;
  96.         link next_entry;
  97.  
  98.         for ( i = 0; i < m->buckets; ++i )
  99.         {
  100.                 this_entry = m->bucket[i];
  101.  
  102.                 while ( this_entry != NULL )
  103.                 {
  104.                         next_entry = this_entry->next;
  105.                         free(this_entry);
  106.                         this_entry = next_entry;
  107.                 }
  108.  
  109.                 m->bucket[i] = NULL;
  110.         }
  111. }
  112.  
  113. int map_copy (map m1, const map m2)
  114. {
  115.         link from, to;
  116.         link new;
  117.         int size;
  118.         int i;
  119.  
  120.         if ( m1->domain_size != m2->domain_size )
  121.                 return ERR;
  122.  
  123.         if ( m1->range_size != m2->range_size )
  124.                 return ERR;
  125.  
  126.         if ( m1->buckets != m2->buckets )
  127.                 return ERR;
  128.  
  129.         if ( m1->hash != m2->hash )
  130.                 return ERR;
  131.  
  132.         map_clear(m1);
  133.  
  134.         size = m2->domain_size + m2->range_size;
  135.  
  136.         for ( i = 0; i < m2->buckets; ++i )
  137.         {
  138.                 from = m2->bucket[i];
  139.  
  140.                 if ( from == NULL )
  141.                         m1->bucket[i] = NULL;
  142.                 else
  143.                 {
  144.                         new = malloc(sizeof(struct link) - 1 + size);
  145.  
  146.                         if ( new == NULL )
  147.                         {
  148.                                 map_clear(m1);
  149.                                 return ERR;
  150.                         }
  151.  
  152.                         memcpy(new->data,from->data,size);
  153.                         new->next = NULL;
  154.                         m1->bucket[i] = new;
  155.  
  156.                         to = new;
  157.                         from = from->next;
  158.  
  159.                         while ( from != NULL )
  160.                         {
  161.                                 new = malloc(sizeof(struct link) - 1 + size);
  162.  
  163.                                 if ( new == NULL )
  164.                                 {
  165.                                         map_clear(m1);
  166.                                         return ERR;
  167.                                 }
  168.  
  169.                                 memcpy(new->data,from->data,size);
  170.                                 new->next = NULL;
  171.  
  172.                                 to->next = new;
  173.  
  174.                                 to = to->next;
  175.                                 from = from->next;
  176.                         }
  177.                 }
  178.         }
  179.  
  180.         return OK;
  181. }
  182.  
  183. int map_equal (const map m1, const map m2)
  184. {
  185.         link p1;
  186.         link p2;
  187.         void *v1;
  188.         void *v2;
  189.         int count1;
  190.         int count2;
  191.         int i;
  192.         int d_size;
  193.         int r_size;
  194.  
  195.         if ( m1->domain_size != m2->domain_size )
  196.                 return 0;
  197.  
  198.         if ( m1->range_size != m2->range_size )
  199.                 return 0;
  200.  
  201.         if ( m1->buckets != m2->buckets )
  202.                 return 0;
  203.  
  204.         if ( m1->hash != m2->hash )
  205.                 return 0;
  206.  
  207.         d_size = m1->domain_size;
  208.         r_size = m1->range_size;
  209.  
  210.         for ( i = 0; i < m1->buckets; ++i )
  211.         {
  212.  
  213.                 if ( m1->bucket[i] == NULL && m2->bucket[i] != NULL )
  214.                         return 0;
  215.  
  216.                 if ( m2->bucket[i] == NULL && m1->bucket[i] != NULL )
  217.                         return 0;
  218.  
  219.                 p1 = m1->bucket[i];
  220.                 count1 = 0;
  221.  
  222.                 while ( p1 != NULL )
  223.                 {
  224.                         v1 = &p1->data[0];
  225.  
  226.                         for ( p2 = m2->bucket[i]; p2 != NULL; p2 = p2->next )
  227.                         {
  228.                                 v2 = &p2->data[0];
  229.                                 if ( memcmp(v1,v2,d_size) == 0 )
  230.                                         break;
  231.                         }
  232.  
  233.                         if ( p2 == NULL )
  234.                                 return 0;
  235.  
  236.                         v1 = &p1->data[d_size];
  237.                         v2 = &p2->data[d_size];
  238.                         if ( memcmp(v1,v2,r_size) != 0 )
  239.                                 return 0;
  240.  
  241.                         ++count1;
  242.  
  243.                         p1 = p1->next;
  244.                 }
  245.  
  246.                 count2 = 0;
  247.  
  248.                 for ( p2 = m2->bucket[i]; p2 != NULL; p2 = p2->next )
  249.                         ++count2;
  250.  
  251.                 if ( count1 != count2 )
  252.                         return 0;
  253.         }
  254.  
  255.         return 1;
  256. }
  257.  
  258. int map_empty (const map m)
  259. {
  260.         int i;
  261.  
  262.         for ( i = 0; i < m->buckets; ++i )
  263.                 if ( m->bucket[i] != NULL )
  264.                         return 0;
  265.  
  266.         return 1;
  267. }
  268.  
  269. int map_size (const map m)
  270. {
  271.         link p;
  272.         int i;
  273.         int count = 0;
  274.  
  275.         for ( i = 0; i < m->buckets; ++i )
  276.         {
  277.                 for ( p = m->bucket[i]; p != NULL; p = p->next )
  278.                         ++count;
  279.         }
  280.  
  281.         return count;
  282. }
  283.  
  284. int map_iterate (const map m, int (*process)(void *, void *))
  285. {
  286.         link p;
  287.         int i;
  288.         int ret;
  289.         void *domain;
  290.         void *range;
  291.  
  292.         for ( i = 0; i < m->buckets; ++i )
  293.         {
  294.                 for ( p = m->bucket[i]; p != NULL; p = p->next )
  295.                 {
  296.                         domain = &p->data[0];
  297.                         range = &p->data[m->domain_size];
  298.  
  299.                         ret = process(domain,range);
  300.  
  301.                         /* Non-zero => stop processing here */
  302.                         /* Negative => Abnormal (error) termination */
  303.  
  304.                         if ( ret != 0 )
  305.                                 return ( ret >= 0 );
  306.                 }
  307.         }
  308.  
  309.         return OK;
  310. }
  311.  
  312. /* Map-specific routines */
  313.  
  314. int map_bind (map m, const void *domain_val, const void *range_val)
  315. {
  316.         link this;
  317.         link new;
  318.         int i;
  319.  
  320.         this = find(m,domain_val,&i,NULL);
  321.  
  322.         if ( this != NULL )
  323.                 return ERR;
  324.  
  325.         new = malloc(sizeof(struct link) - 1 + m->domain_size + m->range_size);
  326.  
  327.         if ( new == NULL )
  328.                 return ERR;
  329.  
  330.         memcpy(&new->data[0],domain_val,m->domain_size);
  331.         memcpy(&new->data[m->domain_size],range_val,m->range_size);
  332.         new->next = m->bucket[i];
  333.  
  334.         m->bucket[i] = new;
  335.  
  336.         return OK;
  337. }
  338.  
  339. int map_unbind (map m, const void *domain_val)
  340. {
  341.         link this;
  342.         link prev;
  343.         int i;
  344.  
  345.         this = find(m,domain_val,&i,&prev);
  346.  
  347.         if ( this == NULL )
  348.                 return ERR;
  349.  
  350.         if ( prev == NULL )
  351.                 m->bucket[i] = this->next;
  352.         else
  353.                 prev->next = this->next;
  354.  
  355.