home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / deque < prev    next >
Encoding:
Text File  |  1992-07-21  |  7.1 KB  |  327 lines
  1. /*      > C.Deque - Deque data type */
  2.  
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "deque.h"
  7.  
  8. #ifdef test
  9. #include <stdio.h>
  10. #endif
  11.  
  12. struct link
  13. {
  14.         struct link *next;
  15.         char data[1];
  16. };
  17.  
  18. typedef struct link *link;
  19.  
  20. /* Return values from functions */
  21.  
  22. #define OK      1
  23. #define ERR     0
  24.  
  25. /* General component routines */
  26.  
  27. deque deq_new (int obj_len)
  28. {
  29.         register deque d;
  30.  
  31.         d = malloc(sizeof(struct deque));
  32.  
  33.         if ( d == NULL )
  34.                 return NULL;
  35.  
  36.         d->head     = NULL;
  37.         d->tail     = NULL;
  38.         d->obj_size = obj_len;
  39.  
  40.         return d;
  41. }
  42.  
  43. void deq_free (deque d)
  44. {
  45.         deq_clear(d);
  46.         free(d);
  47. }
  48.  
  49. void deq_clear (deque d)
  50. {
  51.         link this_entry = d->head;
  52.         link next_entry;
  53.         
  54.         while ( this_entry != NULL )
  55.         {
  56.                 next_entry = this_entry->next;
  57.                 free(this_entry);
  58.                 this_entry = next_entry;
  59.         }
  60.  
  61.         d->head = d->tail = NULL;
  62. }
  63.  
  64. int deq_copy (deque d1, const deque d2)
  65. {
  66.         link p;
  67.         link new;
  68.         link last;
  69.         int size;
  70.  
  71.         if ( d1->obj_size != d2->obj_size )
  72.                 return ERR;
  73.  
  74.         deq_clear(d1);
  75.  
  76.         last = (link)d1;
  77.         size = d2->obj_size;
  78.  
  79.         for ( p = d2->head; p != NULL; p = p->next )
  80.         {
  81.                 new = malloc(sizeof(struct link) - 1 + size);
  82.                 if ( new == NULL )
  83.                 {
  84.                         deq_clear(d1);
  85.                         return ERR;
  86.                 }
  87.                 last->next = new;
  88.                 memcpy(new->data,p->data,size);
  89.                 last = new;
  90.         }
  91.  
  92.         last->next = NULL;
  93.         d1->tail = last;
  94.  
  95.         return OK;
  96. }
  97.  
  98. int deq_equal (const deque d1, const deque d2)
  99. {
  100.         int size;
  101.         link p1;
  102.         link p2;
  103.  
  104.         if ( d1->obj_size != d2->obj_size )
  105.                 return 0;
  106.  
  107.         size = d1->obj_size;
  108.  
  109.         for
  110.         (
  111.                 p1 = d1->head, p2 = d2->head;
  112.                 p1 != NULL && p2 != NULL;
  113.                 p1 = p1->next, p2 = p2->next
  114.         )
  115.         {
  116.                 if ( memcmp(p1->data,p2->data,size) != 0 )
  117.                         return 0;
  118.         }
  119.  
  120.         return ( p1 == p2 );
  121. }
  122.  
  123. int deq_empty (const deque d)
  124. {
  125.         return ( d->head == NULL );
  126. }
  127.  
  128. int deq_size (const deque d)
  129. {
  130.         int i = 0;
  131.         link p;
  132.  
  133.         for ( p = d->head; p != NULL; p = p->next )
  134.                 ++i;
  135.  
  136.         return i;
  137. }
  138.  
  139. int deq_iterate (const deque d, int (*process)(void *))
  140. {
  141.         int ret = 0;
  142.         link p;
  143.  
  144.         for ( p = d->head; p != NULL; p = p->next )
  145.         {
  146.                 ret = (*process)(p->data);
  147.  
  148.                 /* Non-zero => stop processing here */
  149.  
  150.                 if ( ret != 0 )
  151.                         break;
  152.         }
  153.  
  154.         /* Negative => Abnormal (error) termination */
  155.  
  156.         return ( ret >= 0 );
  157. }
  158.  
  159. /* deque-specific routines */
  160.  
  161. int deq_add (deque d, int pos, const void *object)
  162. {
  163.         link new;
  164.  
  165.         new = malloc(sizeof(struct link) - 1 + d->obj_size);
  166.  
  167.         if ( new == NULL )
  168.                 return ERR;
  169.  
  170.         memcpy(new->data,object,d->obj_size);
  171.  
  172.         if ( pos == Front )
  173.         {
  174.                 new->next = d->head;
  175.                 d->head = new;
  176.                 if ( d->tail == NULL )
  177.                         d->tail = d->head;
  178.         }
  179.  
  180.         else
  181.         {
  182.                 new->next = NULL;
  183.                 if ( d->tail != NULL )
  184.                         ((link)d->tail)->next = new;
  185.                 d->tail = new;
  186.                 if ( d->head == NULL )
  187.                         d->head = d->tail;
  188.         }
  189.  
  190.         return OK;
  191. }
  192.  
  193. int deq_pop (deque d, int pos)
  194. {
  195.         link p;
  196.  
  197.         if ( d->head == NULL )
  198.                 return ERR;
  199.  
  200.         else if ( d->head == d->tail )
  201.         {
  202.                 free(d->head);
  203.                 d->head = d->tail = NULL;
  204.         }
  205.  
  206.         else if ( pos == Front )
  207.         {
  208.                 p = d->head;
  209.                 d->head = p->next;
  210.                 free(p);
  211.         }
  212.  
  213.         else
  214.         {
  215.                 p = d->head;
  216.                 while ( p->next != (link)d->tail )
  217.                         p = p->next;
  218.                 p->next = NULL;
  219.                 free(d->tail);
  220.                 d->tail = p;
  221.         }
  222.  
  223.         return OK;
  224. }
  225.  
  226. void *deq_front (const deque d)
  227. {
  228.         if ( d->head == NULL )
  229.                 return NULL;
  230.  
  231.         return ((link)d->head)->data;
  232. }
  233.  
  234. void *deq_back (const deque d)
  235. {
  236.         if ( d->tail == NULL )
  237.                 return NULL;
  238.  
  239.         return ((link)d->tail)->data;
  240. }
  241.  
  242. /*---------------------------------------------------------------------------*/
  243.  
  244. #ifdef test
  245. int print (void *ptr)
  246. {
  247.         printf("%d ",*(int *)ptr);
  248.         return STATUS_CONTINUE;
  249. }
  250.  
  251. void deq_dump (deque d)
  252. {
  253.         printf("deque: ");
  254.         deq_iterate(d,print);
  255.         putchar('\n');
  256. }
  257. #endif
  258.  
  259. /*---------------------------------------------------------------------------*/
  260.  
  261. #ifdef test
  262.  
  263. #define BUFLEN 255
  264.  
  265. int main (void)
  266. {
  267.         char buf[BUFLEN], str[BUFLEN];
  268.         int i, j, num;
  269.         deque d[10];
  270.  
  271.         for ( i = 0; i < 10; ++i )
  272.                 d[i] = deq_new(sizeof(int));
  273.  
  274.         for ( ; ; )
  275.         {
  276.                 printf(">");
  277.                 fgets(buf,BUFLEN,stdin);
  278.  
  279.                 if ( buf[0] == '\n' || buf[0] == '\0' )
  280.                         continue;
  281.                 else if ( sscanf(buf,"clear %1d",&i) == 1 )
  282.                         deq_clear(d[i]);
  283.                 else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
  284.                         deq_copy(d[i],d[j]);
  285.                 else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
  286.                         printf("%s\n",(deq_equal(d[i],d[j]) ? "yes" : "no"));
  287.                 else if ( sscanf(buf,"empty %1d",&i) == 1 )
  288.                         printf("%s\n",(deq_empty(d[i]) ? "yes" : "no"));
  289.                 else if ( sscanf(buf,"size %1d",&i) == 1 )
  290.                         printf("%d\n",deq_size(d[i]));
  291.                 else if ( sscanf(buf,"dump %1d",&i) == 1 )
  292.                         deq_dump(d[i]);
  293.                 else if ( sscanf(buf,"add %1d %s %d",&i,str,&num) == 3 )
  294.                         deq_add(d[i],(str[0]=='f'),&num);
  295.                 else if ( sscanf(buf,"pop %1d %s",&i,str) == 2 )
  296.                         deq_pop(d[i],(str[0]=='f'));
  297.                 else if ( sscanf(buf,"front %1d",&i) == 1 )
  298.                 {
  299.                         int *p = deq_front(d[i]);
  300.                         if ( p == NULL )
  301.                                 printf("Empty\n");
  302.                         else
  303.                                 printf("%d\n",*p);
  304.                 }
  305.                 else if ( sscanf(buf,"back %1d",&i) == 1 )
  306.                 {
  307.                         int *p = deq_back(d[i]);
  308.                         if ( p == NULL )
  309.                                 printf("Empty\n");
  310.                         else
  311.                                 printf("%d\n",*p);
  312.                 }
  313.                 else if ( strncmp(buf,"quit",4) == 0 )
  314.                         break;
  315.                 else
  316.                         printf("Mistake\n");
  317.         }
  318.  
  319.         printf("Deleting d[0-9]\n");
  320.         for ( i = 0; i < 10; ++i )
  321.                 deq_free(d[i]);
  322.  
  323.         return 0;
  324. }
  325.  
  326. #endif
  327.