home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / map < prev    next >
Encoding:
Text File  |  1992-07-21  |  11.1 KB  |  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.         free(this);
  356.  
  357.         return OK;
  358. }
  359.  
  360. void *map_value (const map m, const void *domain_val)
  361. {
  362.         link this;
  363.  
  364.         this = find(m,domain_val,NULL,NULL);
  365.  
  366.         if ( this == NULL )
  367.                 return NULL;
  368.         else
  369.                 return &this->data[m->domain_size];
  370. }
  371.  
  372. int map_bound (const map m, const void *domain_val)
  373. {
  374.         return ( find(m,domain_val,NULL,NULL) != NULL );
  375. }
  376.  
  377. /*---------------------------------------------------------------------------*/
  378.  
  379. #ifdef test
  380. int print (void *domain, void *range)
  381. {
  382.         printf("   %d->%d\n",*(int *)domain,*(int *)range);
  383.         return STATUS_CONTINUE;
  384. }
  385.  
  386. void map_dump (map m)
  387. {
  388.         printf("map:\n");
  389.         map_iterate(m,print);
  390. }
  391. #endif
  392.  
  393. /*---------------------------------------------------------------------------*/
  394.  
  395. #ifdef test
  396.  
  397. #define BUFLEN 255
  398.  
  399. int hash (const void *n)
  400. {
  401.         return *(int *)n;
  402. }
  403.  
  404. int main (void)
  405. {
  406.         char buf[BUFLEN];
  407.         int i, j, from, to;
  408.         map m[10];
  409.  
  410.         for ( i = 0; i < 10; ++i )
  411.                 m[i] = map_new(sizeof(int),sizeof(int),10,hash);
  412.  
  413.         for ( ; ; )
  414.         {
  415.                 printf(">");
  416.                 fgets(buf,BUFLEN,stdin);
  417.  
  418.                 if ( buf[0] == '\n' || buf[0] == '\0' )
  419.                         continue;
  420.                 else if ( sscanf(buf,"clear %1d",&i) == 1 )
  421.                         map_clear(m[i]);
  422.                 else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
  423.                         map_copy(m[i],m[j]);
  424.                 else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
  425.                         printf("%s\n",(map_equal(m[i],m[j]) ? "yes" : "no"));
  426.                 else if ( sscanf(buf,"empty %1d",&i) == 1 )
  427.                         printf("%s\n",(map_empty(m[i]) ? "yes" : "no"));
  428.                 else if ( sscanf(buf,"size %1d",&i) == 1 )
  429.                         printf("%d\n",map_size(m[i]));
  430.                 else if ( sscanf(buf,"dump %1d",&i) == 1 )
  431.                         map_dump(m[i]);
  432.                 else if ( sscanf(buf,"bind %1d %d %d",&i,&from,&to) == 3 )
  433.                 {
  434.                         if ( !map_bind(m[i],&from,&to) )
  435.                                 printf("Already bound\n");
  436.                 }
  437.                 else if ( sscanf(buf,"unbind %1d %d",&i,&from) == 2 )
  438.                 {
  439.                         if ( !map_unbind(m[i],&from) )
  440.                                 printf("Not bound\n");
  441.                 }
  442.                 else if ( sscanf(buf,"value %1d %d",&i,&from) == 2 )
  443.                 {
  444.                         int *p = map_value(m[i],&from);
  445.                         if ( p == NULL )
  446.                                 printf("Unbound\n");
  447.                         else
  448.                                 printf("%d\n",*p);
  449.                 }
  450.                 else if ( sscanf(buf,"bound %1d %d",&i,&from) == 2 )
  451.                         printf("%s\n",(map_bound(m[i],&from) ? "yes" : "no"));
  452.                 else if ( strncmp(buf,"quit",4) == 0 )
  453.                         break;
  454.                 else
  455.                         printf("Mistake\n");
  456.         }
  457.  
  458.         printf("Deleting m[0-9]\n");
  459.         for ( i = 0; i < 10; ++i )
  460.                 map_free(m[i]);
  461.  
  462.         return 0;
  463. }
  464.  
  465. #endif
  466.