home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / lib / xp / xp_list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  10.8 KB  |  516 lines
  1. /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  2.  *
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  *
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  *
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19.  
  20. /* 
  21.   inked list manipulation routines
  22.  
  23.   this is a very standard linked list structure
  24.   used by many many programmers all over the world
  25.  
  26.   The lists have been modified to be doubly linked.  The
  27.     first element in a list is always the header.  The 'next'
  28.     pointer of the header is the first element in the list.
  29.     The 'prev' pointer of the header is the last element in
  30.     the list.
  31.  
  32.   The 'prev' pointer of the first real element in the list
  33.     is NULL as is the 'next' pointer of the last real element
  34.     in the list
  35.  
  36.  */
  37.  
  38. #include "xp.h"
  39.  
  40. #ifdef PROFILE
  41. #pragma profile on
  42. #endif
  43.  
  44. /*
  45.   Delete all of the elements in the list.
  46.   This function does *NOT* free the objects in the list, just the
  47.     list structure itself (seems like a bug...)
  48. */
  49. PUBLIC void 
  50. XP_ListDestroy (XP_List *list)
  51. {
  52.     XP_List *list_ptr;
  53.  
  54.     while (list) 
  55.       {
  56.         list_ptr = list;
  57.         list = list->next;
  58.         XP_FREE(list_ptr);
  59.       }
  60. }
  61.  
  62. /*
  63.   Create a new list
  64. */
  65. PUBLIC XP_List * 
  66. XP_ListNew (void)
  67. {
  68.     XP_List *new_struct = XP_NEW(XP_List);
  69.  
  70.     if (!new_struct) 
  71.         return(NULL);
  72.  
  73.     new_struct->object = NULL;
  74.     new_struct->next   = NULL;
  75.     new_struct->prev   = NULL;
  76.     return new_struct;
  77. }
  78.  
  79. /*
  80.   Add an object to the front of the list (which could also be the end)
  81. */
  82. PUBLIC void 
  83. XP_ListAddObject (XP_List *list, void *object)
  84. {
  85.  
  86.     XP_ASSERT (list);
  87.  
  88.     if (list) {
  89.         XP_List *new_struct = XP_NEW(XP_List);
  90.  
  91.         if (!new_struct) 
  92.           return;
  93.  
  94.         /* set back pointer of old first element */
  95.         if(list->next) {
  96.             list->next->prev = new_struct;
  97.         }
  98.  
  99.         /* we might have a next but since we are the first we WONT have a previous */
  100.         new_struct->object = object;
  101.         new_struct->next = list->next;
  102.         new_struct->prev = NULL;
  103.  
  104.         /* the new element is the first one */
  105.         list->next = new_struct;
  106.  
  107.         /* if this is the only element it is the end too */
  108.         if(NULL == list->prev)
  109.             list->prev = new_struct;
  110.  
  111.     }
  112. }
  113.  
  114. /*
  115.   Add an object to the end of the list
  116. */
  117. PUBLIC void
  118. XP_ListAddObjectToEnd (XP_List *list, void *object)
  119. {
  120.     XP_List * new_struct;
  121.  
  122.     if(NULL == list)
  123.         return;
  124.  
  125.     /* handle the case where the list is empty */
  126.     if(NULL == list->prev) {
  127.         XP_ListAddObject(list, object);
  128.         return;
  129.     }
  130.         
  131.     XP_ASSERT(list->prev);
  132.  
  133.     /* check for out of memory */
  134.     new_struct = XP_NEW(XP_List);
  135.     if (!new_struct) 
  136.       return;
  137.  
  138.     /* initialize our pointers */
  139.     new_struct->prev   = list->prev;
  140.     new_struct->next   = NULL;
  141.     new_struct->object = object;
  142.  
  143.     /* make old last element point to us */
  144.     list->prev->next = new_struct;
  145.  
  146.     /* update end of list pointer */
  147.     list->prev = new_struct;
  148.  
  149. }
  150.  
  151. /*
  152.   Return the 'object' pointer of the last list entry
  153. */
  154. PUBLIC void *
  155. XP_ListGetEndObject (XP_List *list)
  156. {
  157.     if (list && list->prev)
  158.         return(list->prev->object);
  159.     else
  160.         return(NULL);
  161. }
  162.  
  163. /* 
  164.   Dunno what this is doing since it doesn't need to be rewritten
  165.  */
  166. PUBLIC void *
  167. XP_ListGetObjectNum (XP_List *list, int num)
  168. {
  169.     if(list == NULL)
  170.         return(NULL);
  171.  
  172.     if(num < 1)
  173.         return(NULL);
  174.  
  175.     list = list->next;  /* the first list never has data */
  176.  
  177.     for(; list && num > 1; num--)
  178.       {
  179.         list = list->next;
  180.       }
  181.  
  182.     if(list)
  183.         return(list->object);
  184.     else
  185.         return(NULL);
  186. }
  187.  
  188. /* move the top object to the bottom of the list
  189.  * this function is useful for reordering the list
  190.  * so that a round robin ordering can occur
  191.  */
  192. PUBLIC void
  193. XP_ListMoveTopToBottom (XP_List *list)
  194. {
  195.     XP_List *obj1;
  196.     XP_List *prev_end;
  197.     XP_List *next_obj;
  198.  
  199.     if(!list->next || list->next == list->prev)
  200.         return;  /* no action required */
  201.  
  202.     /* move obj1 to the end */
  203.     obj1     = list->next;
  204.     next_obj = obj1->next;
  205.     prev_end = list->prev;
  206.  
  207.     list->next     = next_obj;
  208.     list->prev     = obj1;
  209.     obj1->prev     = prev_end;
  210.     obj1->next     = NULL;
  211.     prev_end->next = obj1;
  212.  
  213.     if(next_obj)
  214.         next_obj->prev = list;
  215. }
  216.  
  217. /*
  218.   Comment goes here
  219. */
  220. PUBLIC int
  221. XP_ListGetNumFromObject (XP_List *list, void * object)
  222. {
  223.     int count = 0;
  224.     void * obj2;
  225.  
  226.     while((obj2 = XP_ListNextObject(list)) != NULL)
  227.       {
  228.         count++;
  229.         if(obj2 == object)
  230.             return(count);
  231.       }
  232.  
  233.     return(0); /* not found */
  234. }
  235.         
  236. /* returns the list node of the specified object if it was 
  237.  * in the list
  238.  */
  239. PUBLIC XP_List *
  240. XP_ListFindObject (XP_List *list, void * obj)
  241. {
  242.     if(!list)
  243.         return(NULL);
  244.  
  245.     list = list->next;  /* the first list item never has data */
  246.  
  247.     while(list)
  248.       {
  249.         if(list->object == obj)
  250.             return(list);
  251.         list = list->next;
  252.       }
  253.  
  254.     return(NULL);
  255. }
  256.  
  257. /*
  258.   Count the number of items in the list
  259.   Should we cache this in the header?  maybe in header->object
  260. */
  261. PUBLIC int 
  262. XP_ListCount (XP_List *list)
  263. {
  264.   int count = 0;
  265.  
  266.   if (list)
  267.     while ((list = list->next) != NULL)
  268.       count++;
  269.  
  270.   return count;
  271. }
  272.  
  273. /*
  274.   Insert an object somewhere into the list.
  275.   If insert_before is not NULL find the element whose 'object' is equal to
  276.     insert_before and add a new element in front of that element.
  277. */
  278. PUBLIC void
  279. XP_ListInsertObject (XP_List *list, void *insert_before, void *object)
  280. {
  281.     XP_List *temp;
  282.     XP_List *new_struct;
  283.  
  284.     XP_ASSERT(list);
  285.  
  286.     if (list) {
  287.         if(NULL == insert_before) {
  288.             XP_ListAddObjectToEnd(list, object);
  289.             return;
  290.         }
  291.  
  292.         /* find the prev pointer so we can add the forward pointer to
  293.          * the new object
  294.          */
  295.         temp = list;
  296.  
  297.         /* walk down the list till we find the element we want */
  298.         for(temp = list; temp; temp = temp->next)
  299.             if(temp->object == insert_before)
  300.                 break;
  301.  
  302.         /*
  303.           We got all the way though and didn't find the element we wanted
  304.             so just stick the new element on the end of the list
  305.         */
  306.         if(!temp) {
  307.             XP_ListAddObjectToEnd(list, object);
  308.             return;
  309.         }
  310.  
  311.         new_struct = XP_NEW(XP_List);
  312.         if (!new_struct)
  313.             return;
  314.  
  315.         /* set our values */
  316.         new_struct->object = object;
  317.         new_struct->next   = temp;
  318.         new_struct->prev   = temp->prev;
  319.  
  320.         /* there is either a previous element or we are the new first element */
  321.         if(temp->prev)
  322.             temp->prev->next = new_struct;
  323.         else
  324.             list->next = new_struct;
  325.  
  326.         temp->prev = new_struct;
  327.  
  328.     }
  329. }
  330.  
  331. /*
  332.   Insert an object somewhere into the list.
  333.   If insert_after is not NULL find the element whose 'object' is equal to
  334.     insert_after and add a new element in back of that element.
  335. */
  336. PUBLIC void
  337. XP_ListInsertObjectAfter (XP_List *list, void *insert_after, void *object)
  338. {
  339.     XP_List *tmp; 
  340.     XP_List *new_struct;
  341.  
  342.     if(list) {
  343.  
  344.         /* if no element to insert after just add to the end of the list */
  345.         if(NULL == insert_after) {
  346.             XP_ListAddObjectToEnd(list, object);
  347.             return;
  348.         }
  349.             
  350.             /* check that insert_after is a valid list entry */
  351.         for(tmp = list; tmp; tmp = tmp->next)
  352.             if(tmp->object == insert_after)
  353.                 break;
  354.  
  355.         /* the object we were asked to insert after is not actually in the
  356.            list.  Add the new item to the end
  357.          */
  358.         if(!tmp) {
  359.             XP_ListAddObjectToEnd(list, object);
  360.             return;
  361.         }
  362.  
  363.         /* creat a new list struct and insert it */
  364.         new_struct = XP_NEW(XP_List);
  365.         if (!new_struct)
  366.             return;
  367.  
  368.         new_struct->object = object;
  369.         new_struct->next = tmp->next;
  370.         new_struct->prev = tmp;
  371.  
  372.         /* we either have a next element or we are the last one */
  373.         if(tmp->next)
  374.             tmp->next->prev = new_struct;
  375.         else
  376.             list->prev = new_struct;
  377.  
  378.         tmp->next = new_struct;
  379.  
  380.     }
  381. }
  382.  
  383.  
  384. /*
  385.   Remove the element whose 'object' field is equal to remove_me
  386.   Return TRUE if such an element was remove else FALSE
  387. */
  388. PUBLIC Bool 
  389. XP_ListRemoveObject (XP_List *list, void *remove_me)
  390. {
  391.     XP_List * tmp;
  392.  
  393.     /* check if list is empty */
  394.     if(NULL == list)
  395.         return(FALSE);
  396.  
  397.     /* walk down list looking for object we want */
  398.     for(tmp = list; tmp; tmp = tmp->next)
  399.         if(tmp->object == remove_me)
  400.             break;
  401.  
  402.     /* element was not found */
  403.     if(NULL == tmp)
  404.         return(FALSE);
  405.  
  406.     /* we either have a prev or we were the first element */
  407.     if(tmp->prev)
  408.         tmp->prev->next = tmp->next;
  409.     else
  410.         list->next = tmp->next;
  411.  
  412.     /* we either have a next or we were the last element */
  413.     if(tmp->next)
  414.         tmp->next->prev = tmp->prev;
  415.     else
  416.         list->prev = tmp->prev;
  417.  
  418.     /* OK we have updated all of the pointers now free the element */
  419.     XP_FREE (tmp);
  420.     return TRUE; 
  421.  
  422. }
  423.  
  424. /*
  425.   Remove the last element in the list and return it
  426. */
  427. PUBLIC void * 
  428. XP_ListRemoveEndObject (XP_List *list)
  429. {
  430.     XP_List * last;
  431.     void    * data;
  432.  
  433.     /* check if bogus list */
  434.     if(NULL == list)
  435.         return(NULL);
  436.  
  437.     /* check if no last element (bug or empty list) */
  438.     if(NULL == list->prev)
  439.         return(NULL);
  440.  
  441.     last = list->prev;
  442.  
  443.     /* 
  444.       there is either a previous element or we were the first and
  445.       only element 
  446.      */      
  447.     if(last->prev)    
  448.         last->prev->next = NULL;
  449.     else
  450.         list->next = NULL;
  451.  
  452.     /* always a new last element */
  453.     list->prev = last->prev;
  454.  
  455.     /* remember the data pointer so we can return it */
  456.     data = last->object;
  457.     XP_FREE(last);
  458.     return(data);
  459.  
  460. }
  461.  
  462. /*
  463.   Remove the first element in the list and return its 'object'
  464. */
  465. PUBLIC void * 
  466. XP_ListRemoveTopObject (XP_List *list)
  467. {
  468.     XP_List * first;
  469.     void    * data;
  470.  
  471.     /* check if bogus list */
  472.     if(NULL == list)
  473.         return(NULL);
  474.  
  475.     /* check if no first element (bug or empty list) */
  476.     if(NULL == list->next)
  477.         return(NULL);
  478.  
  479.     first = list->next;
  480.  
  481.     /*
  482.       There is either a next element or we were the last element too
  483.     */
  484.     if(first->next)
  485.         first->next->prev = NULL;
  486.     else
  487.         list->prev = NULL;
  488.  
  489.     /* new first element */
  490.     list->next = first->next;
  491.  
  492.     /* remember the data pointer so we can return it */
  493.     data = first->object;
  494.     XP_FREE(first);
  495.     return(data);
  496.     
  497. }
  498.  
  499. PUBLIC void * 
  500. XP_ListPeekTopObject (XP_List *list)
  501. {
  502.   if (list && list->next) 
  503.     {
  504.       return list->next->object;
  505.     } 
  506.   else  /* Empty list */
  507.     {
  508.       return NULL;
  509.     } 
  510. }
  511.  
  512. #ifdef PROFILE
  513. #pragma profile off
  514. #endif
  515.  
  516.