home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / ring < prev    next >
Encoding:
Text File  |  1992-07-21  |  9.7 KB  |  430 lines
  1. /*      > C.Ring - Ring data type */
  2.  
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "ring.h"
  7.  
  8. #ifdef test
  9. #include <stdio.h>
  10. #endif
  11.  
  12. struct link
  13. {
  14.         struct link *next;
  15.         struct link *prev;
  16.         char data[1];
  17. };
  18.  
  19. typedef struct link *link;
  20.  
  21. /* Return values from functions */
  22.  
  23. #define OK      1
  24. #define ERR     0
  25.  
  26. /* General component routines */
  27.  
  28. ring ring_new (int obj_len)
  29. {
  30.         register ring r;
  31.  
  32.         r = malloc(sizeof(struct ring));
  33.  
  34.         if ( r == NULL )
  35.                 return NULL;
  36.  
  37.         r->top      = NULL;
  38.         r->mark     = NULL;
  39.         r->obj_size = obj_len;
  40.  
  41.         return r;
  42. }
  43.  
  44. void ring_free (ring r)
  45. {
  46.         ring_clear(r);
  47.         free(r);
  48. }
  49.  
  50. void ring_clear (ring r)
  51. {
  52.         link this_entry = r->top;
  53.         link next_entry;
  54.         
  55.         if ( r->top == NULL )
  56.                 return;
  57.  
  58.         do {
  59.                 next_entry = this_entry->next;
  60.                 free(this_entry);
  61.                 this_entry = next_entry;
  62.         } while ( this_entry != (link)r->top );
  63.  
  64.         r->top = r->mark = NULL;
  65. }
  66.  
  67. int ring_copy (ring r1, const ring r2)
  68. {
  69.         link from, to;
  70.         link new;
  71.         int size;
  72.  
  73.         if ( r1->obj_size != r2->obj_size )
  74.                 return ERR;
  75.  
  76.         ring_clear(r1);
  77.  
  78.         size = r2->obj_size;
  79.         from = r2->top;
  80.  
  81.         if ( from == NULL )
  82.                 return ERR;
  83.         else
  84.         {
  85.                 new = malloc(sizeof(struct link) - 1 + size);
  86.                 if ( new == NULL )
  87.                         return ERR;
  88.  
  89.                 memcpy(new->data,from->data,size);
  90.                 new->next = NULL;
  91.                 new->prev = NULL;
  92.  
  93.                 to = new;
  94.                 r1->top = new;
  95.  
  96.                 if ( from == (link)r2->mark )
  97.                         r1->mark = to;
  98.  
  99.                 from = from->next;
  100.  
  101.                 while ( from != (link)r2->top )
  102.                 {
  103.                         new = malloc(sizeof(struct link) - 1 + size);
  104.                         if ( new == NULL )
  105.                         {
  106.                                 ring_clear(r1);
  107.                                 return ERR;
  108.                         }
  109.  
  110.                         memcpy(new->data,from->data,size);
  111.                         new->next = NULL;
  112.                         new->prev = to;
  113.  
  114.                         to->next = new;
  115.                         to = to->next;
  116.  
  117.                         if ( from == (link)r2->mark )
  118.                                 r1->mark = to;
  119.  
  120.                         from = from->next;
  121.                 }
  122.  
  123.                 ((link)r1->top)->prev = to;
  124.                 to->next = r1->top;
  125.         }
  126.  
  127.         return OK;
  128. }
  129.  
  130. int ring_equal (const ring r1, const ring r2)
  131. {
  132.         link p1 = r1->top;
  133.         link p2 = r2->top;
  134.         int size;
  135.  
  136.         if ( r1->obj_size != r2->obj_size )
  137.                 return 0;
  138.  
  139.         size = r1->obj_size;
  140.         if ( p1 == NULL || p2 == NULL )
  141.                 return ( p1 == p2 );
  142.         else if ( memcmp(p1->data,p2->data,size) != 0 )
  143.                 return 0;
  144.         else if ( p1 == (link)r1->mark && p2 != (link)r2->mark )
  145.                 return 0;
  146.         else
  147.         {
  148.                 p1 = p1->next;
  149.                 p2 = p2->next;
  150.  
  151.                 while ( p1 != (link)r1->top )
  152.                 {
  153.                         if ( p2 == (link)r2->top )
  154.                                 return 0;
  155.                         else if ( memcmp(p1->data,p2->data,size) != 0 )
  156.                                 return 0;
  157.                         else if
  158.                         (
  159.                                 p1 == (link)r1->mark
  160.                         &&
  161.                                 p2 != (link)r2->mark
  162.                         )
  163.                                 return 0;
  164.                         else
  165.                         {
  166.                                 p1 = p1->next;
  167.                                 p2 = p2->next;
  168.                         }
  169.                 }
  170.  
  171.                 return ( p2 == (link)r2->top );
  172.         }
  173. }
  174.  
  175. int ring_empty (const ring r)
  176. {
  177.         return ( r->top == NULL );
  178. }
  179.  
  180. int ring_size (const ring r)
  181. {
  182.         int i = 0;
  183.         link p;
  184.  
  185.         if ( r->top == NULL )
  186.                 return 0;
  187.  
  188.         p = r->top;
  189.  
  190.         do {
  191.                 ++i;
  192.                 p = p->next;
  193.         } while ( p != (link)r->top );
  194.  
  195.         return i;
  196. }
  197.  
  198. int ring_iterate (const ring r, int (*process)(void *, int))
  199. {
  200.         int ret;
  201.         link p;
  202.         int at_mark;
  203.  
  204.         if ( r->top == NULL )
  205.                 return 1;
  206.  
  207.         p = r->top;
  208.  
  209.         do {
  210.                 at_mark = ( p == r->mark );
  211.  
  212.                 ret = (*process)(p->data,at_mark);
  213.  
  214.                 /* Non-zero => stop processing here */
  215.  
  216.                 if ( ret != 0 )
  217.                         break;
  218.  
  219.                 p = p->next;
  220.  
  221.         } while ( p != (link)r->top );
  222.  
  223.         /* Negative => Abnormal (error) termination */
  224.  
  225.         return ( ret >= 0 );
  226. }
  227.  
  228. /* Ring-specific routines */
  229.  
  230. int ring_insert (ring r, const void *object)
  231. {
  232.         link new;
  233.         link p = r->top;
  234.  
  235.         new = malloc(sizeof(struct link) - 1 + r->obj_size);
  236.  
  237.         if ( new == NULL )
  238.                 return ERR;
  239.  
  240.         memcpy(new->data,object,r->obj_size);
  241.  
  242.         if ( p == NULL )
  243.         {
  244.                 new->next = new;
  245.                 new->prev = new;
  246.                 r->mark = new;
  247.         }
  248.         else
  249.         {
  250.                 new->next = p;
  251.                 new->prev = p->prev;
  252.                 new->next->prev = new;
  253.                 new->prev->next = new;
  254.         }
  255.  
  256.         r->top = new;
  257.  
  258.         return OK;
  259. }
  260.  
  261. int ring_pop (ring r)
  262. {
  263.         link p = r->top;
  264.  
  265.         if ( p == NULL )
  266.                 return ERR;
  267.  
  268.         else if ( p->next == p )
  269.         {
  270.                 free(p);
  271.                 r->top = NULL;
  272.                 r->mark = NULL;
  273.         }
  274.  
  275.         else
  276.         {
  277.                 p->prev->next = p->next;
  278.                 p->next->prev = p->prev;
  279.                 if ( p == (link)r->mark )
  280.                         r->mark = p->next;
  281.                 r->top = p->next;
  282.                 free(p);
  283.         }
  284.  
  285.         return OK;
  286. }
  287.  
  288. int ring_rotate (ring r, int dir, int n)
  289. {
  290.         link p = r->top;
  291.         int fwd = ( dir == Forward );
  292.  
  293.         if ( n < 0 )
  294.         {
  295.                 fwd = !fwd;
  296.                 n = -n;
  297.         }
  298.  
  299.         if ( p == NULL )
  300.                 return ERR;
  301.  
  302.         if ( fwd )
  303.         {
  304.                 while ( n-- > 0 )
  305.                         p = p->next;
  306.         }
  307.         else
  308.         {
  309.                 while ( n-- > 0 )
  310.                         p = p->prev;
  311.         }
  312.         
  313.         r->top = p;
  314.  
  315.         return OK;
  316. }
  317.  
  318. void *ring_top (const ring r)
  319. {
  320.         if ( r->top == NULL )
  321.                 return NULL;
  322.  
  323.         return ((link)r->top)->data;
  324. }
  325.  
  326. void ring_mark (ring r)
  327. {
  328.         r->mark = r->top;
  329. }
  330.  
  331. void ring_tomark (ring r)
  332. {
  333.         r->top = r->mark;
  334. }
  335.  
  336. int ring_atmark (const ring r)
  337. {
  338.         return ( r->top == r->mark );
  339. }
  340.  
  341. /*---------------------------------------------------------------------------*/
  342.  
  343. #ifdef test
  344.  
  345. int print (void *ptr, int at_mark)
  346. {
  347.         printf("%d%s", *(int *)ptr, (at_mark ? "* " : " ") );
  348.         return STATUS_CONTINUE;
  349. }
  350.  
  351. void ring_dump (ring r)
  352. {
  353.         printf("Ring: ");
  354.         ring_iterate(r,print);
  355.         putchar('\n');
  356. }
  357. #endif
  358.  
  359. /*---------------------------------------------------------------------------*/
  360.  
  361. #ifdef test
  362.  
  363. #define BUFLEN 255
  364.  
  365. int main (void)
  366. {
  367.         char buf[BUFLEN], str[BUFLEN];
  368.         int i, j, num;
  369.         ring r[10];
  370.  
  371.         for ( i = 0; i < 10; ++i )
  372.                 r[i] = ring_new(sizeof(int));
  373.  
  374.         for ( ; ; )
  375.         {
  376.                 printf(">");
  377.                 fgets(buf,BUFLEN,stdin);
  378.  
  379.                 if ( buf[0] == '\n' || buf[0] == '\0' )
  380.                         continue;
  381.                 else if ( sscanf(buf,"clear %1d",&i) == 1 )
  382.                         ring_clear(r[i]);
  383.                 else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
  384.                         ring_copy(r[i],r[j]);
  385.                 else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
  386.                         printf("%s\n",(ring_equal(r[i],r[j]) ? "yes" : "no"));
  387.                 else if ( sscanf(buf,"empty %1d",&i) == 1 )
  388.                         printf("%s\n",(ring_empty(r[i]) ? "yes" : "no"));
  389.                 else if ( sscanf(buf,"size %1d",&i) == 1 )
  390.                         printf("%d\n",ring_size(r[i]));
  391.                 else if ( sscanf(buf,"dump %1d",&i) == 1 )
  392.                         ring_dump(r[i]);
  393.                 else if ( sscanf(buf,"insert %1d %d",&i,&num) == 2 )
  394.                         ring_insert(r[i],&num);
  395.                 else if ( sscanf(buf,"pop %1d",&i) == 1 )
  396.                 {
  397.                         if ( !ring_pop(r[i]) )
  398.                                 printf("Empty\n");
  399.                 }
  400.                 else if ( sscanf(buf,"rotate %1d %s %d",&i,str,&num) == 3 )
  401.                         ring_rotate(r[i],(str[0]=='f'),num);
  402.                 else if ( sscanf(buf,"top %1d",&i) == 1 )
  403.                 {
  404.                         int *p = ring_top(r[i]);
  405.                         if ( p == NULL )
  406.                                 printf("Empty\n");
  407.                         else
  408.                                 printf("%d\n",*p);
  409.                 }
  410.                 else if ( sscanf(buf,"mark %1d",&i) == 1 )
  411.                         ring_mark(r[i]);
  412.                 else if ( sscanf(buf,"to mark %1d",&i) == 1 )
  413.                         ring_tomark(r[i]);
  414.                 else if ( sscanf(buf,"at mark %1d",&i) == 1 )
  415.                         printf("%s\n",(ring_atmark(r[i]) ? "yes" : "no"));
  416.                 else if ( strncmp(buf,"quit",4) == 0 )
  417.                         break;
  418.                 else
  419.                         printf("Mistake\n");
  420.         }
  421.  
  422.         printf("Deleting r[0-9]\n");
  423.         for ( i = 0; i < 10; ++i )
  424.                 ring_free(r[i]);
  425.  
  426.         return 0;
  427. }
  428.  
  429. #endif
  430.