home *** CD-ROM | disk | FTP | other *** search
/ Oracle Video Server 3.0.3.1 / OVS_3031_NT.iso / win32 / medianet / server / include / yslst.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-10-22  |  11.1 KB  |  277 lines
  1. /* Copyright (c) 1995 by Oracle Corporation.  All Rights Reserved.
  2.  *
  3.  * yslst.h - Linked List Manipulation
  4.  *
  5.  * DESCRIPTION
  6.  * This package implements doubly-linked lists in a fast, general purpose
  7.  * manner.  Each list consists of zero or more list elements.  List elements
  8.  * may either hold a pointer, or may hold copied data.  See ysDLst*() below
  9.  * for more information about the data-oriented list routines.
  10.  *
  11.  * THREAD SAFETY
  12.  * The user of this package is responsible for coordinating access to a
  13.  * list among multiple threads.  Locking a mutex associated with an
  14.  * individual list is sufficient to protect that list during insert and
  15.  * removal operations.
  16.  */
  17.  
  18. #ifndef YSLST_ORACLE
  19. #define YSLST_ORACLE
  20.  
  21. #ifndef SYSX_ORACLE
  22. #include <sysx.h>
  23. #endif
  24. #ifndef YS_ORACLE
  25. #include <ys.h>
  26. #endif
  27. #ifndef YSFO_ORACLE
  28. #include <ysfo.h>
  29. #endif
  30.  
  31. EXTC_START
  32.  
  33. /*
  34.  * ysLstCreate, ysLstDestroy - create and destroy a list
  35.  *
  36.  * DESCRIPTION
  37.  * ysLstCreate() creates and returns an empty list.  ysLstDestroy() destroys
  38.  * a list previously allocated with ysLstCreate().  If the list is not empty
  39.  * and destructor is a valid function pointer, the destructor function will
  40.  * be invoked once on the value of each list element.  In any case, the list
  41.  * itself is destroyed.
  42.  */
  43. yslst *ysLstCreate(void);
  44. void   ysLstDestroy(yslst *l, ysmff destructor);
  45.  
  46. /*
  47.  * ysLstHead, ysLstTail, ysLstPrev, ysLstNext, ysLstVal, ysLstCount
  48.  *   - List Navigation
  49.  *
  50.  * SYNOPSIS
  51.  * ysle *ysLstHead(yslst *l);
  52.  * ysle *ysLstTail(yslst *l);
  53.  * ysle *ysLstPrev(ysle *le);
  54.  * ysle *ysLstNext(ysle *le);
  55.  *
  56.  * void *ysLstVal(ysle *le);
  57.  * ub4   ysLstCount(yslst *l);
  58.  *
  59.  * DESCRIPTION
  60.  * Several functions are provided for list navigation and inspection.
  61.  * ysLstHead() and ysLstTail() return the head element and tail element
  62.  * of the list, respectively.  ysLstPrev() returns the element previous
  63.  * to the given element, and ysLstNext() returns the element following
  64.  * the given element.  If the element requested by one of these routines
  65.  * does not exist, a null pointer is returned.  These routines do not
  66.  * alter the list.
  67.  *
  68.  * ysLstVal() extracts the user value from a list element.  ysLstCount()
  69.  * returns the number of elements in the list.
  70.  */
  71. #define ysLstHead(l)   ((l)->head)
  72. #define ysLstTail(l)   ((l)->tail)
  73. #define ysLstPrev(le)  ((le)->prev)
  74. #define ysLstNext(le)  ((le)->next)
  75. #define ysLstVal(le)   ((le)->ptr)
  76. #define ysLstCount(l)  ((l)->cnt)
  77.  
  78. /*
  79.  * ysLstIns, ysLstRem - insert and remove a list element
  80.  *
  81.  * DESCRIPTION
  82.  * ysLstIns() and ysLstRem() provide for ordered insertion and removal of
  83.  * a value in a list.  ysLstIns() creates a new list element with the
  84.  * value val, and inserts it into the list following the list element le.
  85.  * If le is null, the new element is inserted at the beginning of the list.
  86.  * The list element created is returned.  ysLstRem() removes the list element
  87.  * le, and returns the value of the element.  If le is null, the list is left
  88.  * unchanged and a null pointer is returned.
  89.  */
  90. ysle  *ysLstIns(yslst *l, ysle *le, dvoid *val);
  91. dvoid *ysLstRem(yslst *l, ysle *le);
  92.  
  93. /*
  94.  * ysLstMov - move a list element
  95.  *
  96.  * DESCRIPTION
  97.  * ysLstMov() moves the list element sle to the position following the
  98.  * list element dle in the list l.  Both sle and dle must be part of the
  99.  * list at the time this routine is called.  If dle is null, then sle
  100.  * is moved to the beginning of the list.  Unlike the sequence ysLstRem()/
  101.  * ysLstIns(), this routine guarantees that the list element pointer
  102.  * remains unchanged.
  103.  */
  104. void ysLstMov(yslst *l, ysle *sle, ysle *dle);
  105.  
  106. /*
  107.  * ysLstEnq, ysLstDeq - enqueue and dequeue an element
  108.  * ysLstPush, ysLstPop - push and pop an element
  109.  *
  110.  * SYNOPSIS
  111.  * ysle *ysLstEnq(yslst *l, dvoid *val);
  112.  * dvoid *ysLstDeq(yslst *l);
  113.  * ysle *ysLstPush(yslst *l, dvoid *val);
  114.  * dvoid *ysLstPop(yslst *l);
  115.  *
  116.  * DESCRIPTION
  117.  * Several functions provide common idioms for list usage.  ysLstEnq() and
  118.  * ysLstDeq() manipulate the list as a first-in, first-out queue.  ysLstPush()
  119.  * and ysLstPop() manipulate the list as a last-in, first-out queue, also
  120.  * known as a stack.  If the queue or stack is empty when an element is
  121.  * dequeued or popped, a null pointer is returned.  Both ysLstEnq() and
  122.  * ysLstPush() return the list element that was created.
  123.  */
  124. #define ysLstEnq(l, v)  ysLstIns((l), ysLstTail(l), (v))
  125. #define ysLstDeq(l)     ysLstRem((l), ysLstHead(l))
  126. #define ysLstPush(l, v) ysLstIns((l), (ysle *) 0, (v))
  127. #define ysLstPop(l)     ysLstRem((l), ysLstHead(l))
  128.  
  129. /*
  130.  * ysLstMetricsOn, ysLstMetricsOff() - instrumented lists
  131.  *
  132.  * DESCRIPTION
  133.  * ysLstMetricsOn() turns on activity metrics for a list.  Once on, metrics
  134.  * describing the usage of the list are accumulated.  This continues until
  135.  * ysLstMetricsOff() is called, which disables measuring.  Turning metrics
  136.  * back on again resets all the accumulated statistics.  When a list is
  137.  * created, metrics are off and must explicitly be turned on.
  138.  *
  139.  * If metrics are already on when ysLstMetricsOn() is called, the accumulated
  140.  * statistics are reset.  If metrics are already off when ysLstMetricsOff()
  141.  * is called, the routine does nothing.
  142.  *
  143.  * Turning on metrics will affect the performance of the list operations.
  144.  */
  145. void ysLstMetricsOn(yslst *l);
  146. void ysLstMetricsOff(yslst *l);
  147.  
  148. /*
  149.  * ysLstGetMetrics, ysLstGetCurTime - get metrics for a list
  150.  *
  151.  * DESCRIPTION
  152.  * ysLstGetMetrics() returns a set of metrics accumulated for a list since
  153.  * the last call to ysLstMetricsOn().  These metrics are returned in the
  154.  * structure pointed to by metrics.  The fields are filled in as follows:
  155.  *
  156.  *    totins - total number of elements inserted into the list
  157.  *    curlen - current length of list; same as ysLstCount()
  158.  *    maxlen - maximum length that the list has ever reached
  159.  *    avglen - a rolling weighted average of the list length
  160.  *    maxtm - maximum time that an element ever spent on the list (in
  161.  *            microseconds)
  162.  *    avgtm - a rolling weighted average of the time each element spends
  163.  *            in the list (in microseconds)
  164.  *
  165.  * ysLstGetCurTime() returns the amount of time elapsed since the given
  166.  * element was placed on the list.
  167.  *
  168.  * These routines both throw the exception YS_EX_BADPARAM if the given list
  169.  * does not have metrics turned on.
  170.  */
  171. /* DISABLE check_naming */
  172. struct yslmtc
  173. {
  174.   ub4   totins;           /* total number of elements inserted into the list */
  175.   ub4   curlen;                                      /* same as ysLstCount() */
  176.   ub4   maxlen;                 /* maximum length that the list ever reached */
  177.   ub4   avglen;                                /* average length of the list */
  178.   sysb8 maxtm;         /* maximum time an element was in the list (in usecs) */
  179.   sysb8 avgtm;         /* average time an element was in the list (in usecs) */
  180. };
  181. /* ENABLE check_naming */
  182.  
  183. void ysLstGetMetrics(yslst *l, yslmtc *metrics);
  184. void ysLstGetCurTime(yslst *l, ysle *le, sysb8 *delta);
  185.  
  186. /*
  187.  * Data List Manipulation
  188.  *
  189.  * SYNOPSIS
  190.  * yslst *ysDLstCreate(size_t osz);
  191.  * void   ysDLstDestroy(yslst *l);
  192.  * dvoid *ysDLstVal(ysle *le);
  193.  * ysle  *ysDLstIns(yslst *l, ysle *le, dvoid *val);
  194.  * dvoid *ysDLstRem(yslst *l, ysle *le, dvoid *val);
  195.  * ysle  *ysDLstEnq(yslst *l, dvoid *val);
  196.  * dvoid *ysDLstDeq(yslst *l, dvoid *val);
  197.  * ysle  *ysDLstPush(yslst *l, dvoid *val);
  198.  * dvoid *ysDLstPop(yslst *l, dvoid *val);
  199.  *
  200.  * DESCRIPTION
  201.  * Data lists are lists whose elements actually hold data, as opposed to
  202.  * just a pointer to some data like the above list mechanism supports.
  203.  * When using data lists, the values being put onto the list are actually
  204.  * copied.  This is convenient when the data that is being put on the
  205.  * list is coming from stack variables.
  206.  *
  207.  * The routines used for data list manipulation are essentially as their
  208.  * pointer-oriented counterparts with the following exceptions:
  209.  *
  210.  * ysDLstCreate() takes the size of the elements that are on the list.
  211.  * This size must be same for all elements.  ysDLstRem(), ysDLstDeq(),
  212.  * and ysDLstPop() all take an extra argument which is a pointer to a
  213.  * location where the data value may be copied.  The buffer must be
  214.  * osz bytes long.  If null, then the value is not copied prior to
  215.  * removal.  As a convenience, all of these functions return the
  216.  * argument val for use by the caller.  If le is null when passed to
  217.  * ysDLstRem(), the list is left unchanged and a null pointer is
  218.  * returned.  If the list is empty when ysDLstDeq() or ysDLstPop()
  219.  * are called, then a null pointer is returned to indicate this fact.
  220.  * Note that is not possible to both pass a null pointer for val and
  221.  * use the return value as a meaningful indicator.
  222.  *
  223.  * ysDLstVal() returns a pointer to the value as it is embedded in the
  224.  * list.  This pointer is only valid for as long as the list element
  225.  * remains in the list.  Be sure to copy it if the value needs to be
  226.  * saved after the element is removed or the list destroyed.  (ysDLstRem()
  227.  * may be used to accomplish the copying and removal of the element
  228.  * simultaneously.
  229.  *
  230.  * ysDLstDestroy() destroys the list along with all values contained
  231.  * within the list.  There is no need for a separate destructor function.
  232.  *
  233.  * All routines that do not have a counterpart here may be used directly
  234.  * on lists of this type.  BE AWARE THAT THE CODE DOES NOT DO TYPE-
  235.  * CHECKING TO MAKE SURE THAT YOU ARE USING THE RIGHT OPERATIONS ON THE
  236.  * RIGHT LISTS.
  237.  */
  238. yslst  *ysDLstCreate(size_t osz);
  239. dvoid  *ysDLstRem(yslst *l, ysle *le, dvoid *val);
  240. /* DISABLE check_macro_naming */
  241. #define ysDLstDestroy(l)     ysLstDestroy((l), (ysmff) 0)
  242. #define ysDLstVal(le)        ((dvoid *) &(le)->ptr)
  243. #define ysDLstIns(l, le, v)  ysLstIns((l), (le), (v))
  244. #define ysDLstEnq(l, v)      ysLstIns((l), ysLstTail(l), (v))
  245. #define ysDLstDeq(l, v)      ysDLstRem((l), ysLstHead(l), (v))
  246. #define ysDLstPush(l, v)     ysLstIns((l), (ysle *) 0, (v))
  247. #define ysDLstPop(l, v)      ysDLstRem((l), ysLstHead(l), (v))
  248. /* ENABLE check_macro_naming */
  249.  
  250. /*
  251.  * PRIVATE DECLARATIONS
  252.  */
  253.  
  254. /* DISABLE check_naming */
  255. struct yslst
  256. {
  257.   ysle   *head;                                              /* head of list */
  258.   ysle   *tail;                                              /* tail of list */
  259.   ub4     cnt;                                         /* number of elements */
  260.   size_t  osz;                                                /* object size */
  261.   ysfop   fop;                                          /* fixed object pool */
  262.   boolean mtcon;                                   /* TRUE if metrics are on */
  263.   yslmtc  metrics;                                         /* metrics buffer */
  264. };
  265.  
  266. struct ysle
  267. {
  268.   ysle  *next;                                       /* next element in list */
  269.   ysle  *prev;                                   /* previous element in list */
  270.   sysb8  enqtm;                       /* time of enqueue (if metrics are on) */
  271.   dvoid *ptr;                                               /* element value */
  272. };
  273. /* ENABLE check_naming */
  274.  
  275. EXTC_END
  276. #endif /* YSLST_ORACLE */
  277.