"Fossies" - the Fresh Open Source Software Archive

Member "wcalc-2.5/src/common/list.c" (15 Jan 2014, 12479 Bytes) of package /linux/privat/wcalc-2.5.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "list.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.4.1_vs_2.5.

    1 #ifdef HAVE_CONFIG_H
    2 # include "config.h"
    3 #endif
    4 
    5 /* System Headers */
    6 #include <stdlib.h>                    /* for free() */
    7 #include <string.h>                    /* for memset() */
    8 
    9 /* Internal Headers */
   10 #include "list.h"
   11 
   12 /* structures for constructing the list */
   13 struct _listheader {
   14     struct _listheader *next;
   15     void               *payload;
   16     struct _listheader *pool_next;
   17 };
   18 
   19 struct _list {
   20     struct _listheader *head;
   21     struct _listheader *tail;
   22     unsigned long       len;
   23     struct _list       *pool_next;
   24     struct _list       *pool_prev;
   25 };
   26 
   27 struct _list_iterator {
   28     struct _listheader *cur;
   29     List                l;
   30 };
   31 
   32 struct cleanup {
   33     struct cleanup *next;
   34     void           *data;
   35 };
   36 
   37 static List                       lPool        = NULL;
   38 static List                       lPoolUsed    = NULL;
   39 static unsigned long long         lPoolSize    = 0; /* for exponential growth */
   40 static struct cleanup            *lCleanupPool = NULL;
   41 static inline List                get_l(void);
   42 static void                       fill_l_pool(void);
   43 
   44 static struct _listheader        *lhPool        = NULL;
   45 static unsigned long long         lhPoolSize    = 0; /* for exponential growth */
   46 static struct cleanup            *lhCleanupPool = NULL;
   47 static inline struct _listheader *get_lh(void);
   48 static void                       fill_lh_pool(void);
   49 static void                       poolReturn(struct _listheader *lh);
   50 
   51 /* This sets up the memory pool(s) */
   52 void lists_init(void)
   53 {                                      /*{{{ */
   54     fill_lh_pool();
   55     fill_l_pool();
   56 }                                      /*}}} */
   57 
   58 /* This clean up the memory pool(s) */
   59 void lists_cleanup(void)
   60 {                                      /*{{{ */
   61     struct cleanup *freec;
   62 
   63     while (lhCleanupPool != NULL) {
   64         freec         = lhCleanupPool;
   65         struct _listheader *freeme = freec->data;
   66         lhCleanupPool = lhCleanupPool->next;
   67         free(freeme);
   68         free(freec);
   69     }
   70     while (lCleanupPool != NULL) {
   71         freec        = lCleanupPool;
   72         List freeme = freec->data;
   73         lCleanupPool = lCleanupPool->next;
   74         free(freeme);
   75         free(freec);
   76     }
   77 }                                      /*}}} */
   78 
   79 /* This returns a struct to the pool */
   80 void poolReturn(struct _listheader *lh)
   81 {                                      /*{{{ */
   82     memset(lh, 0, sizeof(struct _listheader));
   83     lh->pool_next = lhPool;
   84     lhPool        = lh;
   85 }                                      /*}}} */
   86 
   87 /* This fills the list header memory pool with 1024 items (or doubles the pool
   88  * size) */
   89 static void fill_lh_pool(void)
   90 {                                      /*{{{ */
   91     struct _listheader *tlist;
   92     struct _listheader *temp;
   93     struct cleanup     *ch;
   94     size_t              newobjcount;
   95     size_t              i;
   96 
   97     newobjcount   = (lhPoolSize == 0) ? 1024 : lhPoolSize;
   98     tlist         = calloc(newobjcount, sizeof(struct _listheader));
   99     ch            = calloc(1, sizeof(struct cleanup));
  100     ch->data      = tlist;
  101     ch->next      = lhCleanupPool;
  102     lhCleanupPool = ch;
  103     for (i = 0; i < newobjcount; ++i) {
  104         temp            = &(tlist[i]);
  105         temp->pool_next = lhPool;
  106         lhPool          = temp;
  107     }
  108     lhPoolSize += newobjcount;
  109 }                                      /*}}} */
  110 
  111 /* This fills the list item memory pool with 2 items (or doubles the pool
  112  * size) */
  113 static void fill_l_pool(void)
  114 {                                      /*{{{ */
  115     size_t          i, newobjcount;
  116     List            temp;
  117     List            tlist;
  118     struct cleanup *ch;
  119 
  120     newobjcount  = (lPoolSize == 0) ? 2 : lPoolSize;
  121     tlist        = calloc(newobjcount, sizeof(struct _list));
  122     ch           = calloc(1, sizeof(struct cleanup));
  123     ch->data     = tlist;
  124     ch->next     = lCleanupPool;
  125     lCleanupPool = ch;
  126     for (i = 0; i < newobjcount; ++i) {
  127         temp            = &(tlist[i]);
  128         temp->pool_next = lPool;
  129         lPool           = temp;
  130     }
  131     lPoolSize += newobjcount;
  132 }                                      /*}}} */
  133 
  134 /* This frees up the memory allocated by the list */
  135 void freeList(List *lst)
  136 {                                      /*{{{ */
  137     List thelist;
  138 
  139     if (!lst) {
  140         return;
  141     }
  142 
  143     thelist = *lst;
  144     if (!thelist) {
  145         return;
  146     }
  147 
  148     while (thelist->len > 0 && thelist->head != NULL) {
  149         struct _listheader *h = thelist->head;
  150 
  151         thelist->head = h->next;
  152         thelist->len--;
  153         poolReturn(h);
  154     }
  155     if (lPoolUsed == thelist) {
  156         lPoolUsed = thelist->pool_next;
  157     }
  158     if (thelist->pool_next) {
  159         thelist->pool_next->pool_prev = thelist->pool_prev;
  160     }
  161     if (thelist->pool_prev) {
  162         thelist->pool_prev->pool_next = thelist->pool_next;
  163     }
  164     thelist->pool_next = lPool;
  165     thelist->pool_prev = NULL;
  166     lPool              = thelist;
  167     *lst               = NULL;
  168 }                                      /*}}} */
  169 
  170 /* this fetches a new list header from the pool */
  171 static inline struct _listheader *get_lh(void) /*{{{ */
  172 {
  173     struct _listheader *lh;
  174 
  175     if (NULL == lhPool) {
  176         fill_lh_pool();
  177     }
  178     lh            = lhPool;
  179     lhPool        = lh->pool_next;
  180     lh->pool_next = NULL;
  181     return lh;
  182 }                                      /*}}} */
  183 
  184 /* this fetches a new list from the pool */
  185 static inline List get_l(void)
  186 {                                      /*{{{ */
  187     List l;
  188 
  189     if (NULL == lPool) {
  190         fill_l_pool();
  191     }
  192     l            = lPool;
  193     lPool        = l->pool_next;
  194     l->pool_next = lPoolUsed;
  195     if (lPoolUsed) {
  196         lPoolUsed->pool_prev = l;
  197     }
  198     lPoolUsed            = l;
  199     lPoolUsed->pool_prev = NULL;
  200     return l;
  201 }                                      /*}}} */
  202 
  203 /* This adds "addme" to the end of the list */
  204 void addToList(List *lst,
  205                void *addme)
  206 {                                      /*{{{ */
  207     List                list;
  208     struct _listheader *pl;
  209 
  210     pl          = get_lh();
  211     pl->payload = addme;
  212     pl->next    = NULL;
  213     if (!lst) {
  214         return;
  215     }
  216     list = *lst;
  217     if (!list) {
  218         list       = *lst = get_l();
  219         list->tail = list->head = pl;
  220         list->len  = 1;
  221     } else {
  222         if (list->tail) {
  223             list->tail->next = pl;
  224             list->tail       = pl;
  225             list->len++;
  226         } else {
  227             list->tail = list->head = pl;
  228             list->len  = 1;
  229         }
  230     }
  231 }                                      /*}}} */
  232 
  233 /* This adds "addme" to the head of the list */
  234 void addToListHead(List *lst,
  235                    void *addme)
  236 {                                      /*{{{ */
  237     List                list;
  238     struct _listheader *pl;
  239 
  240     pl          = get_lh();
  241     pl->payload = addme;
  242     pl->next    = NULL;
  243     if (!lst) {
  244         return;
  245     }
  246     list = *lst;
  247     if (!list) {
  248         list       = *lst = get_l();
  249         list->tail = list->head = pl;
  250         list->len  = 1;
  251     } else {
  252         if (list->head) {
  253             pl->next   = list->head;
  254             list->head = pl;
  255             list->len++;
  256         } else {
  257             list->tail = list->head = pl;
  258             list->len  = 1;
  259         }
  260     }
  261 }                                      /*}}} */
  262 
  263 /* This removes the front of the list from the list and returns it */
  264 void *getHeadOfList(List list)
  265 {                                      /*{{{ */
  266     void               *payload;
  267     struct _listheader *pl;
  268 
  269     if (!list || !list->head) {
  270         return NULL;
  271     }
  272     payload    = list->head->payload;
  273     pl         = list->head;
  274     list->head = list->head->next;
  275     poolReturn(pl);
  276     list->len--;
  277     if (list->len == 0) {
  278         list->head = list->tail = NULL;
  279     }
  280     return payload;
  281 }                                      /*}}} */
  282 
  283 /* This returns the n'th element of the list, as if the list was an array */
  284 void *peekListElement(List   list,
  285                       size_t n)
  286 {                                      /*{{{ */
  287     struct _listheader *pl;
  288     size_t              counter;
  289 
  290     if (!list || !list->head || (list->len <= n)) {
  291         return NULL;
  292     }
  293     pl = list->head;
  294     for (counter = 1; counter <= n; counter++) {
  295         if (pl->next == NULL) {
  296             return NULL;
  297         }
  298         pl = pl->next;
  299     }
  300     return pl->payload;
  301 }                                      /*}}} */
  302 
  303 /* This returns the n'th element of the list, as if the list was an array,
  304  * and removes it from the list */
  305 void *getListElement(List   list,
  306                      size_t n)
  307 {                                      /*{{{ */
  308     struct _listheader *pl;
  309     void               *payload = NULL;
  310     struct _listheader *returnme;
  311 
  312     if (!list || !list->head || (list->len <= n)) {
  313         return NULL;
  314     }
  315     pl = list->head;
  316     if (n > 0) {
  317         size_t counter;
  318         for (counter = 1; counter < n; counter++) {
  319             if (pl->next == NULL) {
  320                 return NULL;
  321             }
  322             pl = pl->next;
  323         }
  324         if (pl->next) {
  325             payload  = pl->next->payload;
  326             returnme = pl->next;
  327             pl->next = pl->next->next;
  328             poolReturn(returnme);
  329         }
  330     } else {
  331         payload    = pl->payload;
  332         returnme   = pl;
  333         list->head = pl->next;
  334         if (list->tail == returnme) {
  335             list->tail = NULL;
  336         }
  337     }
  338     list->len--;
  339     return payload;
  340 }                                      /*}}} */
  341 
  342 /* This returns the head of the list */
  343 inline void *peekAheadInList(List list)
  344 {                                      /*{{{ */
  345     if (list && list->head) {
  346         return list->head->payload;
  347     }
  348     return NULL;
  349 }                                      /*}}} */
  350 
  351 /* This tells you how many items there are in the list */
  352 inline size_t listLen(List list)
  353 {                                      /*{{{ */
  354     if (list) {
  355         return list->len;
  356     } else {
  357         return 0;
  358     }
  359 }                                      /*}}} */
  360 
  361 /* This returns a list iterator to a list */
  362 ListIterator getListIterator(List list)
  363 {                                      /*{{{ */
  364     ListIterator li;
  365 
  366     if (!list) {
  367         return NULL;
  368     }
  369     li      = malloc(sizeof(struct _list_iterator));
  370     li->cur = list->head;
  371     li->l   = list;
  372     return li;
  373 }                                      /*}}} */
  374 
  375 /* This returns the value of the current element in the list Iterator */
  376 void *currentListElement(ListIterator li)
  377 {                                      /*{{{ */
  378     if (!li || !(li->cur)) {
  379         return NULL;
  380     }
  381     return li->cur->payload;
  382 }                                      /*}}} */
  383 
  384 /* This iterates a list iterator */
  385 void *nextListElement(ListIterator li)
  386 {                                      /*{{{ */
  387     void *payload;
  388 
  389     if (!li || !(li->cur)) {
  390         return NULL;
  391     }
  392     payload = li->cur->payload;
  393     li->cur = li->cur->next;
  394     return payload;
  395 }                                      /*}}} */
  396 
  397 /* This sets the iterator back to the beginning */
  398 void resetListIterator(ListIterator li)
  399 {                                      /*{{{ */
  400     if (li) {
  401         li->cur = li->l->head;
  402     }
  403 }                                      /*}}} */
  404 
  405 /* This frees up a list iterator */
  406 void freeListIterator(ListIterator li)
  407 {                                      /*{{{ */
  408     if (li) {
  409         free(li);
  410     }
  411 }                                      /*}}} */
  412 
  413 /* This searches the list for a specific value, and removes it */
  414 void removeFromList(List  list,
  415                     void *item)
  416 {   /*{{{*/
  417     struct _listheader *pl;
  418 
  419     if (!list || !list->head) {
  420         return;
  421     }
  422     pl = list->head;
  423     if (pl->payload == item) {
  424         if (list->head == list->tail) {
  425             list->head = list->tail = NULL;
  426             list->len  = 0;
  427         } else {
  428             list->len--;
  429             list->head = list->head->next;
  430         }
  431         poolReturn(pl);
  432     } else {
  433         while (pl->next && pl->next != list->tail) {
  434             if (pl->next->payload == item) {
  435                 break;
  436             }
  437             if (pl->next->next == NULL) {
  438                 return;
  439             }
  440             pl = pl->next;
  441         }
  442         if (pl->next && (pl->next->payload == item)) {
  443             struct _listheader *returnme = pl->next;
  444             pl->next = pl->next->next;
  445             poolReturn(returnme);
  446         }
  447     }
  448 } /*}}}*/
  449 
  450 /* vim:set expandtab: */