home *** CD-ROM | disk | FTP | other *** search
/ Jason Aller Floppy Collection / 125.img / PRO-C4.ZIP / BENCH1.ZIP / BENCH / DLLIST.C < prev    next >
C/C++ Source or Header  |  1990-05-28  |  15KB  |  454 lines
  1. /***( dllist.c )****************************************************************
  2. *                                                                              *
  3. *  Contains generic doubly-linked list functions.                              *
  4. *                                                                              *
  5. ********************************************************************************
  6. *                                                                              *
  7. *  Written: Dec  7, 1989 - SBF                                                 *
  8. *  Updated: Dec 14, 1989 - SBF ( added dll_getpos and dll_setpos            )  *
  9. *           Dec 27, 1989 - SBF ( added dll_rebuild                          )  *
  10. *           MMM DD, YYYY - XXX (                                            )  *
  11. *                                                                              *
  12. *******************************************************************************/
  13. #include <stdio.h>
  14. #include <bench.h>
  15. #include <dllist.h>
  16.  
  17. #ifdef ANSI
  18. int rebuild_cmp(); /*generic **, generic **);*/
  19. #else
  20. int rebuild_cmp();
  21. #endif
  22.  
  23. struct dll_cb *dll_cb[MAXNUMDLL];
  24.  
  25. /*
  26.  * dll_add() - Add an entry to the list, according to the comparison function
  27.  *             passed into dll_open(), or in un-sorted order
  28. */
  29. int dll_add(dll_d, ptr, add_mode)
  30. int dll_d;                                          /* Handle for list to use */
  31. generic *ptr;                                      /* Pointer to entry to add */
  32. int add_mode;                                       /* ADD_SORT or ADD_NOSORT */
  33. {
  34.     register struct dll_entry *deptr;  /* Pointer to current or new list entry */
  35.     struct dll_entry *denext;                    /* Pointer to next list entry */
  36.     struct dll_entry *deprev;                /* Pointer to previous list entry */
  37.     register struct dll_cb *cb;               /* Pointer to list control block */
  38.  
  39.     if ((cb = dll_cb[dll_d]) == NULL)       /* Check validity of control block */
  40.         return(-1);
  41.  
  42.     if (cb->dll_head == NULL)            /* Add the first entry (head is NULL) */
  43.     {
  44.         cb->dll_head = deptr = (struct dll_entry *)alloc(sizeof(struct dll_entry));
  45.         if (cb->dll_head == NULL)                               /* Alloc failed */
  46.             return(-1);
  47.         
  48.         cb->dll_head->dll_ptr = (generic *)alloc(cb->dll_size);
  49.         if (cb->dll_head->dll_ptr == NULL)
  50.             return(-1);
  51.  
  52.         cb->dll_head->dll_next = NULL;                  /* Next of tail is NULL */
  53.         cb->dll_head->dll_prev = cb->dll_head;          /* Prev of head is tail */
  54.         memcpy((char *)cb->dll_head->dll_ptr, (char *)ptr, cb->dll_size);
  55.     }
  56.     else               /* Insert entry into list according to compare function */
  57.     {
  58.         if (add_mode == ADD_SORT)
  59.         {
  60.             for (deptr = cb->dll_head; deptr != NULL; deptr = deptr->dll_next)
  61.             {
  62.                 if ((*cb->dll_cmp)(deptr->dll_ptr, ptr) < 0)
  63.                     continue;
  64.                 else
  65.                 {
  66.                     denext = deptr;                          /* Save prev and next */
  67.                     deprev = deptr->dll_prev;
  68.                                                               /* Allocate entry */
  69.                     deptr = (struct dll_entry *)alloc(sizeof(struct dll_entry));
  70.                     if (deptr == NULL)
  71.                         return(-1);
  72.     
  73.                     deptr->dll_ptr = (generic *)alloc(cb->dll_size);
  74.                     if (deptr->dll_ptr == NULL)
  75.                         return(-1);
  76.     
  77.                     if (denext == cb->dll_head)               /* Is it a new head? */
  78.                         cb->dll_head = deptr;
  79.     
  80.                     deptr->dll_next = denext;   /* Set next and prev and save data */
  81.                     deptr->dll_prev = deprev;
  82.                     memcpy((char *)deptr->dll_ptr, (char *)ptr, cb->dll_size);
  83.     
  84.                     denext->dll_prev = deptr;
  85.     
  86.                     if (cb->dll_head != deptr)
  87.                         deprev->dll_next = deptr;
  88.     
  89.                     break;
  90.                 }
  91.             }
  92.         }
  93.         else
  94.             deptr = NULL;
  95.  
  96.         if (deptr == NULL)                          /* This entry is a new tail */
  97.         {
  98.             deprev = cb->dll_head->dll_prev;  /* Save prev and allocate an entry */
  99.             deptr = (struct dll_entry *)alloc(sizeof(struct dll_entry));
  100.             if (deptr == NULL)
  101.                 return(-1);
  102.  
  103.             deptr->dll_ptr = (generic *)alloc(cb->dll_size);
  104.             if (deptr->dll_ptr == NULL)
  105.                 return(-1);
  106.                                              /* Set tail pointer (head->prev) */
  107.             cb->dll_head->dll_prev = deprev->dll_next = deptr;
  108.  
  109.             deptr->dll_next = NULL;           /* Set next and prev and save data */
  110.             deptr->dll_prev = deprev;
  111.             memcpy((char *)deptr->dll_ptr, (char *)ptr, cb->dll_size);
  112.         }
  113.     }
  114.  
  115.     cb->dll_curr = deptr;
  116.  
  117.     return(0);
  118. }
  119.  
  120. /*
  121.  * dll_close() - Close a doubly-linked list
  122. */
  123. int dll_close(dll_d)
  124. int dll_d;                       /* Handle of control block for list to close */
  125. {
  126.     register struct dll_cb *cb;                    /* Pointer to control block */
  127.     register struct dll_entry *deptr;       /* Pointer to current item in list */
  128.     struct dll_entry *denext;                  /* Pointer to next item in list */
  129.     struct dll_entry *detail = NULL;                /* Pointer to tail of list */
  130.     struct dll_entry *delast = NULL;            /* Pointer to last entry freed */
  131.  
  132.     if ((cb = dll_cb[dll_d]) == NULL)           /* Check for valid list handle */
  133.         return(-1);
  134.  
  135.     if (cb->dll_head != NULL)               /* Free the list if it has entries */
  136.     {
  137.         detail = cb->dll_head->dll_prev;                       /* Save the tail */
  138.  
  139.         for (deptr = cb->dll_head; deptr != NULL; deptr = denext)
  140.         {
  141.             denext = deptr->dll_next;            /* Free one entry after another */
  142.             free(deptr->dll_ptr);
  143.             free(deptr);
  144.             delast = deptr;                             /* Save last entry freed */
  145.         }
  146.     }
  147.  
  148.     free(cb);                                 /* Free the actual control block */
  149.     dll_cb[dll_d] = NULL;                     /* Make the pointer usable again */
  150.  
  151.     if (delast != detail)  /* Consistancy check - was the tail the last freed? */
  152.         return(-1);
  153.     else
  154.         return(0);
  155. }
  156.  
  157. /*
  158.  * dll_curr() - Get current list entry
  159. */
  160. generic *dll_curr(dll_d)
  161. int dll_d;
  162. {
  163.     return(dll_seek(dll_d, 0, SEEK_CUR));
  164. }
  165.  
  166. /*
  167.  * dll_del() - Delete the current list item
  168. */
  169. int dll_del(dll_d)
  170. int dll_d;                                        /* Handle for control block */
  171. {
  172.     register struct dll_cb *cb;                    /* Pointer to control block */
  173.     register struct dll_entry *decurr;             /* Pointer to current entry */
  174.     struct dll_entry *deprev;                     /* Pointer to previous entry */
  175.     struct dll_entry *denext;                         /* Pointer to next entry */
  176.  
  177.     if ((cb = dll_cb[dll_d]) == NULL)                /* Check for valid handle */
  178.         return(-1);
  179.  
  180.     if (cb->dll_curr == NULL)                       /* Check for current entry */
  181.         return(-1);
  182.  
  183.     decurr = cb->dll_curr;                      /* Save current, prev and next */
  184.     deprev = decurr->dll_prev;
  185.     denext = decurr->dll_next;
  186.  
  187.     if (decurr != cb->dll_head)          /* Curr is not head so set prev->next */
  188.         deprev->dll_next = decurr->dll_next;
  189.  
  190.     if (denext != NULL)                    /* Tail delete needs head->prev set */
  191.         denext->dll_prev = decurr->dll_prev;
  192.     else
  193.         cb->dll_head->dll_prev = deprev;
  194.  
  195.     if (decurr == cb->dll_head)                /* Head delete needs head reset */
  196.     {
  197.         cb->dll_head = denext;
  198.         cb->dll_curr = NULL;               /* Set curr to NULL (for dll_next()) */
  199.     }
  200.     else
  201.         cb->dll_curr = deprev;             /* Set curr to prev (for dll_next()) */
  202.  
  203.     free(decurr->dll_ptr);                              /* Actually free entry */
  204.     free(decurr);
  205.  
  206.     return(0);
  207. }
  208.  
  209. /*
  210.  * dll_find() - Find a list entry with given data
  211. */
  212. generic *dll_find(dll_d, ptr)
  213. int dll_d;                                        /* Handle for control block */
  214. generic *ptr;                                      /* Pointer to data to find */
  215. {
  216.     register struct dll_cb *cb;                    /* Pointer to control block */
  217.     register struct dll_entry *deptr;       /* Pointer to entry being compared */
  218.  
  219.     if ((cb = dll_cb[dll_d]) == NULL)                /* Check for valid handle */
  220.         return(NULL);
  221.  
  222.                                                        /* Find an equal entry */
  223.     for (deptr = cb->dll_head; deptr != NULL; deptr = deptr->dll_next)
  224.         if ((*cb->dll_cmp)(deptr->dll_ptr, ptr) == 0)
  225.             break;
  226.  
  227.     if (deptr == NULL)                         /* No entry found (return NULL) */
  228.         return(NULL);
  229.  
  230.     cb->dll_curr = deptr;                /* Set current entry to the found one */
  231.     return(deptr->dll_ptr);                          /* Return pointer to data */
  232. }
  233.  
  234. /*
  235.  * dll_getpos() - Get current position (actual list pointer)
  236. */
  237. struct dll_entry *dll_getpos(dll_d)
  238. int dll_d;                                                     /* List handle */
  239. {
  240.     if (dll_cb[dll_d] == NULL)                  /* Check for valid list handle */
  241.         return(NULL);
  242.  
  243.     return(dll_cb[dll_d]->dll_curr);           /* Return current entry pointer */
  244. }
  245.  
  246. /*
  247.  * dll_open() - Open a doubly-linked list
  248. */
  249. int dll_open(cmp, size)
  250. int (*cmp)();                             /* Comparison function for add/find */
  251. int size;                                             /* Size of data in list */
  252. {
  253.     register int dll_d;                            /* Handle for control block */
  254.     register struct dll_cb *cb;                    /* Pointer to control block */
  255.  
  256.     for (dll_d = 0; dll_d < MAXNUMDLL; dll_d++)
  257.         if (dll_cb[dll_d] == NULL)                 /* Find a free control block */
  258.             break;
  259.  
  260.     if (dll_d == MAXNUMDLL)                               /* No free ones left */
  261.         return(-1);
  262.  
  263.     cb = dll_cb[dll_d] = (struct dll_cb *)alloc(sizeof(struct dll_cb));
  264.     if (cb == NULL)                                            /* Alloc failed */
  265.         return(-1);
  266.  
  267.     cb->dll_head = NULL;                           /* Initialize control block */
  268.     cb->dll_curr = NULL;
  269.     cb->dll_cmp = cmp;
  270.     cb->dll_size = size;
  271.  
  272.     return(dll_d);                     /* Return handle for control block used */
  273. }
  274.  
  275. /*
  276.  * dll_next() - Get next entry in list
  277. */
  278. generic *dll_next(dll_d)
  279. int dll_d;                                        /* Handle for control block */
  280. {
  281.     register struct dll_cb *cb;                    /* Pointer to control block */
  282.  
  283.     if ((cb = dll_cb[dll_d]) == NULL)                /* Check for valid handle */
  284.         return(NULL);
  285.  
  286.     if (cb->dll_head == NULL)                          /* Check for empty list */
  287.         return(NULL);
  288.  
  289.     if (cb->dll_curr == NULL)                      /* New list or head deleted */
  290.         cb->dll_curr = cb->dll_head;                      /* So... jump to head */
  291.     else
  292.     {
  293.         if (cb->dll_curr->dll_next == NULL)    /* At tail already (return NULL) */
  294.             return(NULL);
  295.  
  296.         cb->dll_curr = cb->dll_curr->dll_next;            /* Jump to next entry */
  297.     }
  298.  
  299.     return(cb->dll_curr->dll_ptr);                  /* Return pointer to data */
  300. }
  301.  
  302. /*
  303.  * dll_prev() - Get previous entry in list
  304. */
  305. generic *dll_prev(dll_d)
  306. int dll_d;                                         /* Handle of control block */
  307. {
  308.     register struct dll_cb *cb;                    /* Pointer to control block */
  309.  
  310.     if ((cb = dll_cb[dll_d]) == NULL)                /* Check for valid handle */
  311.         return(NULL);
  312.  
  313.                                /* List is empty or current entry isn't defined*/
  314.     if (cb->dll_head == NULL || cb->dll_curr == NULL)
  315.         return(NULL);
  316.  
  317.     if (cb->dll_curr == cb->dll_head)               /* Already at head of list */
  318.         return(NULL);
  319.  
  320.     cb->dll_curr = cb->dll_curr->dll_prev;           /* Jump to previous entry */
  321.     return(cb->dll_curr->dll_ptr);                   /* Return pointer to data */
  322. }
  323.  
  324. /*
  325.  * Stuff required by dll_rebuild
  326. */
  327. #ifdef ANSI
  328. static int (*new_cmp)(generic *, generic *);
  329. #else
  330. static int (*new_cmp)();
  331. #endif
  332.  
  333. int rebuild_cmp(ptr1, ptr2)
  334. generic **ptr1, **ptr2;
  335. {
  336.     return(new_cmp(*ptr1, *ptr2));
  337. }
  338.  
  339. /*
  340.  * dll_rebuild() - Sort a list using a new cmp() function and make the new
  341.  *                 function the active comparison function
  342. */
  343. int dll_rebuild(dll_d, cmp)
  344. int dll_d;
  345. int (*cmp)();
  346. {
  347.     register struct dll_cb *cb;
  348.     generic **dat_array;
  349.     struct dll_entry *dllptr;
  350.     int numentries = 0;
  351.     int datctr;
  352.  
  353.     if ((cb = dll_cb[dll_d]) == NULL)
  354.         return(-1);
  355.  
  356.     for(dllptr = cb->dll_head; dllptr != NULL; dllptr = dllptr->dll_next)
  357.         numentries++;
  358.  
  359.     if (numentries > 1)
  360.     {
  361.         dat_array = (generic **)alloc(numentries * sizeof(generic *));
  362.         if (dat_array == NULL)
  363.             return(-1);
  364.  
  365.         for(dllptr = cb->dll_head, datctr = 0; dllptr != NULL; dllptr = dllptr->dll_next, datctr++)
  366.             dat_array[datctr] = dllptr->dll_ptr;
  367.  
  368.         new_cmp = cmp;
  369.         qsort(dat_array, numentries, sizeof(generic *), rebuild_cmp);
  370.  
  371.         for(dllptr = cb->dll_head, datctr = 0; dllptr != NULL; dllptr = dllptr->dll_next, datctr++)
  372.             dllptr->dll_ptr = dat_array[datctr];
  373.     
  374.         free(dat_array);
  375.     }
  376.  
  377.     cb->dll_cmp = cmp;
  378.     return(0);
  379. }
  380.  
  381. /*
  382.  * dll_seek() - Seek a given number of entries from a specified position
  383. */
  384. generic *dll_seek(dll_d, offset, origin)
  385. int dll_d;                                        /* Handle for control block */
  386. int offset;                                      /* Number of entries to seek */
  387. int origin;                                            /* Origin to seek from */
  388. {
  389.     register struct dll_cb *cb;                    /* Pointer to control block */
  390.     generic *seekptr;                               /* Pointer to current data */
  391.     int seekctr;                     /* Counter for number of next's or prev's */
  392.     struct dll_entry *desave;                 /* Pointer to old current record */
  393.  
  394.     if ((cb = dll_cb[dll_d]) == NULL)                /* Check for valid handle */
  395.         return(NULL);
  396.  
  397.     if (cb->dll_head == NULL)                          /* Check for empty list */
  398.         return(NULL);
  399.  
  400.     desave = cb->dll_curr;                           /* Save the current entry */
  401.  
  402.     switch(origin)
  403.     {
  404.         case SEEK_SET:                                        /* Seek from head */
  405.             cb->dll_curr = cb->dll_head;
  406.             break;
  407.         case SEEK_CUR:                               /* Seek from current entry */
  408.             if (cb->dll_curr == NULL)
  409.                 return(NULL);
  410.             break;
  411.         case SEEK_END:                                        /* Seek from tail */
  412.             cb->dll_curr = cb->dll_head->dll_prev;
  413.             break;
  414.         default:                                         /* Unrecognized origin */
  415.             return(NULL);
  416.     }
  417.  
  418.     seekptr = cb->dll_curr->dll_ptr;                      /* Current data here */
  419.  
  420.     for(seekctr = 0; seekctr < abs(offset); seekctr++)/* Seek 'offset' entries */
  421.     {
  422.         if (offset < 0)                        /* Negative offset is dll_prev() */
  423.             seekptr = dll_prev(dll_d);
  424.         else                                   /* Positive offset is dll_next() */
  425.             seekptr = dll_next(dll_d);
  426.  
  427.         if (seekptr == NULL)          /* If error seeking restore current entry */
  428.         {
  429.             cb->dll_curr = desave;
  430.             break;
  431.         }
  432.     }
  433.  
  434.     return(seekptr);        /* Return pointer to data or NULL if error seeking */
  435. }
  436.  
  437. /*
  438.  * dll_setpos() - set current position (actual list pointer)
  439. */
  440. int dll_setpos(dll_d, dll_pos)
  441. int dll_d;                                                     /* List handle */
  442. struct dll_entry *dll_pos;                           /* Pointer to list entry */
  443. {
  444.     if (dll_cb[dll_d] == NULL)                       /* Check for valid handle */
  445.         return(-1);
  446.  
  447.     if (dll_pos == NULL)
  448.         return(-1);
  449.  
  450.     dll_cb[dll_d]->dll_curr = dll_pos;                      /* Set current position */
  451.  
  452.     return(0);
  453. }
  454.