home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / xdme_1.84_src.lha / XDME / Lib / src / DLL.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-25  |  7.6 KB  |  300 lines
  1. /******************************************************************************
  2.  
  3.     MODULE
  4.     DLL.c
  5.  
  6.     DESCRIPTION
  7.     Type DLL - Double Linked List
  8.  
  9.     This module is used to simplify work with some Exec
  10.     structures like Tasks, Processes, Lists ...
  11.  
  12.     DList/DNode are equivalent to Exec:MinList/MinNode
  13.     I chose using new names to keep bindings stricter;
  14.     (btw. there seems to be 0 Exec function accepting Min*
  15.     according to Protos)
  16.  
  17.     HISTORY
  18.     14-11-94 b_noll created
  19.     $Log: DLL.c $
  20.  
  21. ******************************************************************************/
  22.  
  23. /**************************************
  24.           Includes
  25. **************************************/
  26.  
  27. #ifndef   DLL_H
  28. #include <DLL.h>
  29. #endif /* DLL_H */
  30.  
  31. /**************************************
  32.       Internal Defines & Structures
  33. **************************************/
  34.  
  35. #undef    Prototype
  36. #define Prototype extern
  37. #undef DLL_GetHead
  38. #undef DLL_GetTail
  39. #undef DLL_GetSucc
  40. #undef DLL_GetPred
  41.  
  42.  
  43.  
  44. Prototype void DLL_Init (struct DList *l);
  45. void DLL_Init (struct DList *l)
  46. {
  47.     l->Head    = (struct DNode *)&l->Tail;
  48.     l->Tail    = NULL;
  49.     l->TailPred = (struct DNode *)l;
  50. } /* DLL_Init */
  51.  
  52. /* ---- Movement */
  53.  
  54. Prototype struct DNode *DLL_GetHead (struct DList *l);
  55. struct DNode *DLL_GetHead (struct DList *l)
  56. {
  57.     return l->Head->Succ ? l->Head : NULL;
  58. } /* DLL_GetHead */
  59. #define DLL_GetHead(l)   (l->Head->Succ?    l->Head:    NULL)
  60.  
  61. Prototype struct DNode *DLL_GetTail (struct DList *l);
  62. struct DNode *DLL_GetTail (struct DList *l)
  63. {
  64.     return l->TailPred->Succ ? l->TailPred : NULL;
  65. } /* DLL_GetTail */
  66. #define DLL_GetTail(l)   (l->TailPred->Pred?l->TailPred:NULL)
  67.  
  68. Prototype struct DNode *DLL_GetSucc (struct DList *l, struct DNode *n);
  69. struct DNode *DLL_GetSucc (struct DList *l, struct DNode *n)
  70. {
  71.     return n->Succ->Succ ? n->Succ : NULL;
  72. } /* DLL_GetSucc */
  73. #define DLL_GetSucc(l,n) (n->Succ->Succ?    n->Succ:    NULL)
  74.  
  75. Prototype struct DNode *DLL_GetPred (struct DList *l, struct DNode *n);
  76. struct DNode *DLL_GetPred (struct DList *l, struct DNode *n)
  77. {
  78.     return n->Pred->Pred ? n->Pred : NULL;
  79. } /* DLL_GetPred */
  80. #define DLL_GetPred(l,n) (n->Pred->Pred?    n->Pred:    NULL)
  81.  
  82. /* ---- Destruction */
  83.  
  84. Prototype void DLL_Remove (struct DList *l, struct DNode *n);
  85. void DLL_Remove (struct DList *l, struct DNode *n)
  86. {
  87.     n->Pred->Succ = n->Succ;
  88.     n->Succ->Pred = n->Pred;
  89. } /* DLL_Remove */
  90. #define DLL_Remove(l,n) do{ n->Pred->Succ = n->Succ; n->Succ->Pred = n->Pred; }while(0)
  91.  
  92. Prototype struct DNode * DLL_RemTail (struct DList *l);
  93. struct DNode * DLL_RemTail (struct DList *l)
  94. {
  95.     struct DNode *n;
  96.     if ((n = DLL_GetTail(l))) {
  97.     DLL_Remove (l,n);
  98.     } /* if */
  99.     return n;
  100. } /* DLL_RemTail */
  101.  
  102. Prototype struct DNode * DLL_RemHead (struct DList *l);
  103. struct DNode * DLL_RemHead (struct DList *l)
  104. {
  105.     struct DNode *n;
  106.     if ((n = DLL_GetHead(l))) {
  107.     DLL_Remove (l,n);
  108.     } /* if */
  109.     return n;
  110. } /* DLL_RemHead */
  111.  
  112. /* ---- Construction */
  113.  
  114. Prototype void DLL_AddBehind (struct DList *l, struct DNode *n, struct DNode *pos);
  115. void DLL_AddBehind (struct DList *l, struct DNode *n, struct DNode *pos)
  116. {
  117.     n->Succ        = pos->Succ;
  118.     n->Pred        = pos;
  119.     pos->Succ->Pred = n;
  120.     pos->Succ        = n;
  121. } /* DLL_AddBehind */
  122.  
  123. Prototype void DLL_AddInfront (struct DList *l, struct DNode *n, struct DNode *pos);
  124. void DLL_AddInfront (struct DList *l, struct DNode *n, struct DNode *pos)
  125. {
  126.     DLL_AddBehind (l, n, pos->Pred);
  127. } /* DLL_AddInfront */
  128.  
  129. Prototype void DLL_AddHead (struct DList *l, struct DNode *n);
  130. void DLL_AddHead (struct DList *l, struct DNode *n)
  131. {
  132.     DLL_AddBehind (l, n, (struct DNode *)l);
  133. } /* DLL_AddHead */
  134.  
  135. Prototype void DLL_AddTail (struct DList *l, struct DNode *n);
  136. void DLL_AddTail (struct DList *l, struct DNode *n)
  137. {
  138.     DLL_AddBehind (l, n, l->TailPred);
  139. } /* DLL_AddTail */
  140.  
  141. /* ---- Movement 2 */
  142.  
  143. Prototype int DLL_Length (struct DList *l);
  144. int DLL_Length (struct DList *l) {
  145.     struct DNode *n;
  146.     int       num = 0;
  147.  
  148.     for (n = DLL_GetHead (l); n; n = DLL_GetSucc(l,n))
  149.     num ++;
  150.  
  151.     return num;
  152. } /* DLL_Length */
  153.  
  154. Prototype struct DNode *DLL_NumToNode (struct DList *l, int num);
  155. struct DNode *DLL_NumToNode (struct DList *l, int num) {
  156.     struct DNode *n;
  157.     if (num >= 0) {
  158.     for (n = DLL_GetHead (l); (num > 0) && (n != NULL); n = DLL_GetSucc (l,n), num --);
  159.     } else {
  160.     for (n = DLL_GetTail (l); (num < 0) && (n != NULL); n = DLL_GetPred (l,n), num ++);
  161.     } /* if */
  162.  
  163.     return n;
  164. } /* DLL_NumToNode */
  165.  
  166. Prototype int DLL_NodeToNum (struct DList *l, struct DNode *n);
  167. int DLL_NodeToNum (struct DList *l, struct DNode *n) {
  168.     int num = 0;
  169.  
  170.     if (n != NULL) {
  171.     while (n = DLL_GetPred (l,n)) {
  172.         num ++;
  173.     } /* while */
  174.  
  175.     return num;
  176.     } /* if */
  177.     return -1;
  178. } /* DLL_NodeToNum */
  179.  
  180. /* ---- Movement 3 */
  181.  
  182. Prototype struct DNode *DLL_Find (struct DList *l, int (*find)(struct DNode *, void *, int), void *ud);
  183. struct DNode *DLL_Find (struct DList *l, int (*find)(struct DNode *, void *, int), void *ud) {
  184.     struct DNode *n;
  185.     int       i = 0;
  186.     for (n = DLL_GetHead(l); n; n = DLL_GetSucc(l,n)) {
  187.     if (!(*find)(n, ud, i++))
  188.         return n;
  189.     } /* for */
  190.     return NULL;
  191. } /* DLL_Find */
  192.  
  193. Prototype void DLL_Scan (struct DList *l, void (*scan)(struct DNode *, void *, int), void *ud);
  194. void DLL_Scan (struct DList *l, void (*scan)(struct DNode *, void *, int), void *ud) {
  195.     struct DNode *n, *nn;
  196.     int i = 0;
  197.     for (n = DLL_GetHead(l); n; n = nn) {
  198.     nn = DLL_GetSucc(l,n);
  199.     (*scan)(n, ud, i++);
  200.     } /* for */
  201. } /* DLL_Scan */
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208. #if 0
  209. /* ---- Complex functions */
  210.  
  211.  
  212. Prototype void DLL_Sort (struct DList *l, int (*comp)(struct DNode *, struct DNode *));
  213. void DLL_Sort (struct DList *l, int (*comp)(struct DNode *, struct DNode *)) {
  214.     struct DNode *n, *c;
  215.     struct DList inter;
  216.     int diff;
  217.  
  218.     NewList (&inter);
  219.  
  220.     while (n = DLL_GetHead(l)) {
  221.     for (c = DLL_GetSucc(l,n); c; c = DLL_GetSucc(c)) {
  222.         diff = (*comp)(c, n);
  223.         if (diff < 0)
  224.         n = c;
  225.     } /* for */
  226.     DLL_Remove (l, n);
  227.     DLL_AddHead(&inter, n);
  228.     } /* while */
  229.  
  230.     while (n = DLL_RemHead(&inter)) {
  231.     AddHead(l, n);
  232.     } /* while */
  233. } /* DLL_Sort */
  234.  
  235.  
  236. Prototype void DLL_Filter (struct DList *l, struct DList *dest, int (*check)(struct DNode *, void *), void *ud);
  237. void DLL_Filter (struct DList *l, struct DList *dest, int (*check)(struct DNode *, void *), void *ud) {
  238.     struct DNode *n, *nn;
  239.     int chck;
  240.  
  241.     for (n = DLL_GetHead(l); n; n = nn) {
  242.     nn = DLL_GetSucc(l,n);
  243.  
  244.     chck = (*check)(n, ud);
  245.     if (chck) {
  246.         DLL_Remove(l, n);
  247.         DLL_AddTail(dest, n);
  248.     } /* if */
  249.     } /* for */
  250. } /* DLL_Filter */
  251.  
  252.  
  253.  
  254.  
  255.  
  256. Prototype void DLL_Join (struct DList *dest, struct DList *add);
  257. void DLL_Join (struct DList *dest, struct DList *add) {
  258. #if 1
  259.     struct DNode *inter;
  260.  
  261.     while (inter = DLL_RemHead (add)) {
  262.     AddTail (dest, inter);
  263.     } /* while */
  264. #else
  265.     struct DNode *last     = dest->TailPred;
  266.     struct DNode *afirst = DLL_GetHead (add);
  267.  
  268.     if (afirst) {
  269.     last->Succ   = afirst;
  270.     afirst->Pred = last;
  271.     last = DLL_GetTail (add);
  272.  
  273.     last->Succ     = &dest->Tail;
  274.     dest->TailPred = last;
  275.  
  276.     NewList (add);
  277.     } /* if */
  278. #endif /* NOT_DEF */
  279. } /* DLL_Join */
  280.  
  281.  
  282. Prototype void DLL_AddSorted (struct DList *l, struct DNode *n, int (*comp)(struct DNode *, struct DNode *, void *), void *ud);
  283. void DLL_AddSorted (struct DList *l, struct DNode *n, int (*comp)(struct DNode *, struct DNode *, void *), void *ud) {
  284.     struct DNode *m;
  285.     for (m = DLL_GetHead(l); m && ((*comp)(m, n, ud) < 0); m = DLL_GetSucc (l,m));
  286.     if (!m) {
  287.     DLL_AddTail(l,n);
  288.     } else {
  289.     Insert(l, n, m->Pred);
  290.     }
  291. } /* DLL_AddSorted */
  292.  
  293. #endif
  294.  
  295.  
  296. /******************************************************************************
  297. *****  END DLL.c
  298. ******************************************************************************/
  299.  
  300.