17aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley/* llist.c - Linked list functions 215bdc11ec8dd724cc07502d534a04084d226f132Rob Landley * 315bdc11ec8dd724cc07502d534a04084d226f132Rob Landley * Linked list structures have a next pointer as their first element. 415bdc11ec8dd724cc07502d534a04084d226f132Rob Landley */ 515bdc11ec8dd724cc07502d534a04084d226f132Rob Landley 615bdc11ec8dd724cc07502d534a04084d226f132Rob Landley#include "toys.h" 715bdc11ec8dd724cc07502d534a04084d226f132Rob Landley 8e604d5344466df8584c48c8492397fcffa63a671Rob Landley// Callback function to free data pointer of double_list or arg_list 9e604d5344466df8584c48c8492397fcffa63a671Rob Landley 10e604d5344466df8584c48c8492397fcffa63a671Rob Landleyvoid llist_free_arg(void *node) 11e604d5344466df8584c48c8492397fcffa63a671Rob Landley{ 12e604d5344466df8584c48c8492397fcffa63a671Rob Landley struct arg_list *d = node; 13e604d5344466df8584c48c8492397fcffa63a671Rob Landley 14e604d5344466df8584c48c8492397fcffa63a671Rob Landley free(d->arg); 15e604d5344466df8584c48c8492397fcffa63a671Rob Landley free(d); 16e604d5344466df8584c48c8492397fcffa63a671Rob Landley} 17e604d5344466df8584c48c8492397fcffa63a671Rob Landley 18e604d5344466df8584c48c8492397fcffa63a671Rob Landleyvoid llist_free_double(void *node) 19e604d5344466df8584c48c8492397fcffa63a671Rob Landley{ 20e604d5344466df8584c48c8492397fcffa63a671Rob Landley struct double_list *d = node; 21e604d5344466df8584c48c8492397fcffa63a671Rob Landley 22e604d5344466df8584c48c8492397fcffa63a671Rob Landley free(d->data); 23e604d5344466df8584c48c8492397fcffa63a671Rob Landley free(d); 24e604d5344466df8584c48c8492397fcffa63a671Rob Landley} 25e604d5344466df8584c48c8492397fcffa63a671Rob Landley 269e2b6db36ab6486172fccd0e1786532826d58c53Rob Landley// Call a function (such as free()) on each element of a linked list. 27e604d5344466df8584c48c8492397fcffa63a671Rob Landleyvoid llist_traverse(void *list, void (*using)(void *node)) 2815bdc11ec8dd724cc07502d534a04084d226f132Rob Landley{ 29fe91e68e8d1e6a2974b57a9855032ad94d137e8eRob Landley void *old = list; 30fe91e68e8d1e6a2974b57a9855032ad94d137e8eRob Landley 317aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley while (list) { 327aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley void *pop = llist_pop(&list); 337aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley using(pop); 34bdf037ff5e1b933d624ac74c62c5c1eb14464737Rob Landley 357aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley // End doubly linked list too. 36fe91e68e8d1e6a2974b57a9855032ad94d137e8eRob Landley if (old == list) break; 377aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley } 3815bdc11ec8dd724cc07502d534a04084d226f132Rob Landley} 390a04b3ef850cd3d6f06b3c8d0036993adc9ba7b2Rob Landley 400a04b3ef850cd3d6f06b3c8d0036993adc9ba7b2Rob Landley// Return the first item from the list, advancing the list (which must be called 410a04b3ef850cd3d6f06b3c8d0036993adc9ba7b2Rob Landley// as &list) 420a04b3ef850cd3d6f06b3c8d0036993adc9ba7b2Rob Landleyvoid *llist_pop(void *list) 430a04b3ef850cd3d6f06b3c8d0036993adc9ba7b2Rob Landley{ 447aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley // I'd use a void ** for the argument, and even accept the typecast in all 457aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley // callers as documentation you need the &, except the stupid compiler 467aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley // would then scream about type-punned pointers. Screw it. 477aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley void **llist = (void **)list; 487aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley void **next = (void **)*llist; 497aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley *llist = *next; 507aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley 517aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley return (void *)next; 520a04b3ef850cd3d6f06b3c8d0036993adc9ba7b2Rob Landley} 536ef04efa853b80c76ead2d252b3f4771f4c25d5dRob Landley 545f57bccc41c8893914121b00e16a96dd16282486Rob Landleyvoid *dlist_pop(void *list) 555f57bccc41c8893914121b00e16a96dd16282486Rob Landley{ 565f57bccc41c8893914121b00e16a96dd16282486Rob Landley struct double_list **pdlist = (struct double_list **)list, *dlist = *pdlist; 575f57bccc41c8893914121b00e16a96dd16282486Rob Landley 58bb215e4a1fece603cdede556c1107135b31312a0Rob Landley if (dlist->next == dlist) *pdlist = 0; 59bb215e4a1fece603cdede556c1107135b31312a0Rob Landley else { 60bb215e4a1fece603cdede556c1107135b31312a0Rob Landley dlist->next->prev = dlist->prev; 61bb215e4a1fece603cdede556c1107135b31312a0Rob Landley dlist->prev->next = *pdlist = dlist->next; 62bb215e4a1fece603cdede556c1107135b31312a0Rob Landley } 635f57bccc41c8893914121b00e16a96dd16282486Rob Landley 645f57bccc41c8893914121b00e16a96dd16282486Rob Landley return dlist; 655f57bccc41c8893914121b00e16a96dd16282486Rob Landley} 665f57bccc41c8893914121b00e16a96dd16282486Rob Landley 672c48247a01a19c709f693d649d8158bccb5fbf70Rob Landleyvoid dlist_add_nomalloc(struct double_list **list, struct double_list *new) 682c48247a01a19c709f693d649d8158bccb5fbf70Rob Landley{ 697aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley if (*list) { 707aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley new->next = *list; 717aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley new->prev = (*list)->prev; 727aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley (*list)->prev->next = new; 737aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley (*list)->prev = new; 747aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley } else *list = new->next = new->prev = new; 752c48247a01a19c709f693d649d8158bccb5fbf70Rob Landley} 762c48247a01a19c709f693d649d8158bccb5fbf70Rob Landley 772c48247a01a19c709f693d649d8158bccb5fbf70Rob Landley 7853c75045868da4cbc1a20b70d0a0711ae052344cRob Landley// Add an entry to the end of a doubly linked list 79bdf037ff5e1b933d624ac74c62c5c1eb14464737Rob Landleystruct double_list *dlist_add(struct double_list **list, char *data) 806ef04efa853b80c76ead2d252b3f4771f4c25d5dRob Landley{ 817aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley struct double_list *new = xmalloc(sizeof(struct double_list)); 826ef04efa853b80c76ead2d252b3f4771f4c25d5dRob Landley 837aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley new->data = data; 847aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley dlist_add_nomalloc(list, new); 85bdf037ff5e1b933d624ac74c62c5c1eb14464737Rob Landley 867aa651a6a4496d848f86de9b1e6b3a003256a01fRob Landley return new; 876ef04efa853b80c76ead2d252b3f4771f4c25d5dRob Landley} 88dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley 89dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley// Terminate circular list for traversal in either direction. Returns end *. 90dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landleyvoid *dlist_terminate(void *list) 91dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley{ 92dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley struct double_list *end = list; 93dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley 94dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley if (!list) return 0; 95dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley 96dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley end = end->prev; 97dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley end->next->prev = 0; 98dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley end->next = 0; 99dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley 100dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley return end; 101dc640259adff6007d195fd4cc78dcf9829e5e6eeRob Landley} 10257dafe3915339090c6233cc82025adf116ddf667Rob Landley 10357dafe3915339090c6233cc82025adf116ddf667Rob Landley// Find num in cache 10457dafe3915339090c6233cc82025adf116ddf667Rob Landleystruct num_cache *get_num_cache(struct num_cache *cache, long long num) 10557dafe3915339090c6233cc82025adf116ddf667Rob Landley{ 10657dafe3915339090c6233cc82025adf116ddf667Rob Landley while (cache) { 10757dafe3915339090c6233cc82025adf116ddf667Rob Landley if (num==cache->num) return cache; 10857dafe3915339090c6233cc82025adf116ddf667Rob Landley cache = cache->next; 10957dafe3915339090c6233cc82025adf116ddf667Rob Landley } 11057dafe3915339090c6233cc82025adf116ddf667Rob Landley 11157dafe3915339090c6233cc82025adf116ddf667Rob Landley return 0; 11257dafe3915339090c6233cc82025adf116ddf667Rob Landley} 11357dafe3915339090c6233cc82025adf116ddf667Rob Landley 11457dafe3915339090c6233cc82025adf116ddf667Rob Landley// Uniquely add num+data to cache. Updates *cache, returns pointer to existing 11557dafe3915339090c6233cc82025adf116ddf667Rob Landley// entry if it was already there. 11657dafe3915339090c6233cc82025adf116ddf667Rob Landleystruct num_cache *add_num_cache(struct num_cache **cache, long long num, 11757dafe3915339090c6233cc82025adf116ddf667Rob Landley void *data, int len) 11857dafe3915339090c6233cc82025adf116ddf667Rob Landley{ 11957dafe3915339090c6233cc82025adf116ddf667Rob Landley struct num_cache *old = get_num_cache(*cache, num); 12057dafe3915339090c6233cc82025adf116ddf667Rob Landley 12157dafe3915339090c6233cc82025adf116ddf667Rob Landley if (old) return old; 12257dafe3915339090c6233cc82025adf116ddf667Rob Landley 12357dafe3915339090c6233cc82025adf116ddf667Rob Landley old = xzalloc(sizeof(struct num_cache)+len); 12457dafe3915339090c6233cc82025adf116ddf667Rob Landley old->next = *cache; 12557dafe3915339090c6233cc82025adf116ddf667Rob Landley old->num = num; 12657dafe3915339090c6233cc82025adf116ddf667Rob Landley memcpy(old->data, data, len); 12757dafe3915339090c6233cc82025adf116ddf667Rob Landley *cache = old; 12857dafe3915339090c6233cc82025adf116ddf667Rob Landley 12957dafe3915339090c6233cc82025adf116ddf667Rob Landley return 0; 13057dafe3915339090c6233cc82025adf116ddf667Rob Landley} 131