"Fossies" - the Fresh Open Source Software Archive

Member "scalpel-2.0/src/prioque.h" (20 Apr 2011, 9006 Bytes) of archive /linux/misc/scalpel-2.0.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 "prioque.h" see the Fossies "Dox" file reference documentation.

    1 //
    2 // priority queue header file "prioque.h" */
    3 // (c) 198x/1998/2001/2004 (minor updates) by Golden G. Richard III, Ph.D. */
    4 //
    5 //
    6 // Major update October 2004: The package is now thread-safe.  The
    7 // package now depends on the pthreads library (for access to
    8 // semaphores).  All functions now take one or more pointers to a
    9 // queue or context, so existing applications will need to be 
   10 // modified slightly.
   11 
   12 // Additionally, new functions are now provided for walking the queue
   13 // "locally"--that is, more than one thread can maintain a position in
   14 // the queue using a local Context.  The old 'rewind_queue()',
   15 // 'pointer_to_current()', etc. are maintained for a single position
   16 // during a global walk.
   17 //
   18 // Finally, a long-standing memory leak was corrected.
   19 //
   20 // April 2007: added an option to init_queue to allow priority field to 
   21 // serve only as a tag--the queue is not sorted by the priority field when 
   22 // 'priority_is_tag_only' is set.
   23 //
   24 
   25 #include <pthread.h>
   26 
   27 #define  TRUE  1
   28 #define  FALSE 0
   29 #define CONSISTENCY_CHECKING
   30 
   31 #if ! defined(QUEUE_TYPE_DEFINED)
   32 #define QUEUE_TYPE_DEFINED
   33 
   34 /* type of one element in a queue */
   35 
   36 typedef struct _Queue_element
   37 {
   38   void *info;
   39   int priority;
   40   struct _Queue_element *next;
   41 } *Queue_element;
   42 
   43 /* basic queue type */
   44 
   45 typedef struct Queue
   46 {
   47   Queue_element queue;      /* linked list of elements */
   48   Queue_element current;    /* current position for sequential access functions */
   49   Queue_element previous;   /* one step back from current */
   50   int queuelength;      /* # of elements in queue */
   51   int elementsize;      /* 'sizeof()' one element */
   52   int duplicates;       /* are duplicates allowed? */
   53   int (*compare) (void *e1, void *e2);  /* element comparision function */
   54   pthread_mutex_t lock;
   55   int priority_is_tag_only;
   56 } Queue;
   57 
   58 typedef struct Context
   59 {
   60   Queue_element current;    /* current position for local seq access functions */
   61   Queue_element previous;   /* one step back from current */
   62   Queue *queue;         /* queue associated with this context */
   63 } Context;
   64 
   65 
   66 
   67 /********/
   68 /*
   69 NOTE: init_queue() must be called for a new queue before any other "prioque.c" 
   70 functions are called.
   71 */
   72 /********/
   73 
   74 
   75 /* function prototypes and descriptions for visible "prioque.c" functions
   76 */
   77 
   78 ////////////////////////////
   79 // SECTION 1
   80 ////////////////////////////
   81 
   82 /* initializes a new queue 'q' to have elements of size 'elementsize'.
   83    If 'duplicates' is true, then duplicate elements in the queue are
   84    allowed, otherwise duplicates are silently deleted.  The
   85    element-comparing function 'compare' is required only if
   86    duplicates==FALSE or either equal_queues() or element_in_queue()
   87    are used (otherwise, a null function is acceptable).  'compare'
   88    should be a standard qsort()-style element comparison function:
   89    returns 0 if elements match, otherwise a non-0 result (<, > cases
   90    are not used).
   91 
   92    NOTE:Only the 'compare' function is used for duplicate
   93    detection--priority is not considered (i.e., attempting to add a
   94    "duplicate" element that has a different priority than the existing
   95    element will have no effect!)
   96 */
   97 void init_queue (Queue * q, int elementsize, int duplicates,
   98          int (*compare) (void *e1, void *e2),
   99          int priority_is_tag_only);
  100 
  101 
  102 /* destroys all elements in 'q'
  103 */
  104 void destroy_queue (Queue * q);
  105 
  106 
  107 /* adds 'element' to the 'q' with position based on 'priority'.
  108    Elements with lower-numbered priorities are placed closer to the
  109    front of the queue, with strict 'to the rear' placement for items
  110    with equal priority [that is, given two items with equal priority,
  111    the one most recently added will appear closer to the rear of the
  112    queue].
  113 */
  114 void add_to_queue (Queue * q, void *element, int priority);
  115 
  116 
  117 
  118 
  119 /* removes the element at the front of the 'q' and places it in 'element'.
  120 */
  121 void remove_from_front (Queue * q, void *element);
  122 
  123 
  124 /* returns TRUE if the 'element' exists in the 'q', otherwise false.
  125    The 'compare' function is used for matching.  As a side-effect, the
  126    current position in the queue is set to matching element, so
  127    'update_current()' can be used to update the value of the
  128    'element'.  If the element is not found, the current position is
  129    set to the first element in the queue.
  130 */
  131 int element_in_queue (Queue * q, void *element);
  132 
  133 
  134 /* returns TRUE if 'q' is empty, FALSE otherwise 
  135 */
  136 int empty_queue (Queue * q);
  137 
  138 
  139 /* returns the number of elements in the 'q'.
  140 */
  141 int queue_length (Queue * q);
  142 
  143 
  144 /* makes a copy of 'q2' into 'q1'.  'q2' is not modified.
  145 */
  146 void copy_queue (Queue * q1, Queue * q2);
  147 
  148 
  149 /* determines if 'q1' and 'q2' are equivalent.  Uses the 'compare'
  150    function of the first queue, which should match the 'compare' for
  151    the second!  Returns TRUE if the queues are equal, otherwise
  152    returns FALSE.
  153 */
  154 int equal_queues (Queue * q1, Queue * q2);
  155 
  156 
  157 /* merge 'q2' into 'q1'.   'q2' is not modified.
  158 */
  159 void merge_queues (Queue * q1, Queue * q2);
  160 
  161 
  162 ////////////////////////////
  163 // SECTION 2
  164 ////////////////////////////
  165 
  166 /* the following are functions used to "walk" the queue (globally)
  167    like a linked list, examining or deleting elements along the way.
  168    Current position is rewound to the beginning by functions above (in
  169    SECTION 1), except for 'empty_queue()' and 'queue_length()', which
  170    do not modify the global current position.
  171 */
  172 
  173 /********************/
  174 /********************/
  175 
  176 
  177 /* move to the first element in the 'q' */
  178 void rewind_queue (Queue * q);
  179 
  180 
  181 /* move to the next element in the 'q' */
  182 void next_element (Queue * q);
  183 
  184 
  185 /* allows update of current element.  The priority should not
  186    be changed by this function!
  187 */
  188 
  189 void update_current (Queue * q, void *element);
  190 
  191 
  192 /* retrieve the element stored at the current position in the 'q' */
  193 void peek_at_current (Queue * q, void *element);
  194 
  195 
  196 /* return a pointer to the data portion of the current element */
  197 void *pointer_to_current (Queue * q);
  198 
  199 
  200 /* return priority of current element in the 'q' */
  201 int current_priority (Queue * q);
  202 
  203 
  204 /* delete the element stored at the current position */
  205 void delete_current (Queue * q);
  206 
  207 
  208 
  209 /* has the current position in 'q'  moved beyond the last valid element?  
  210    Returns TRUE if so, FALSE otherwise.
  211 */
  212 int end_of_queue (Queue * q);
  213 
  214 ////////////////////////////
  215 // SECTION 3
  216 ////////////////////////////
  217 
  218 // Functions in this section provide the ability to walk the queue
  219 // with a locally maintained position.  They do not affect the global
  220 // queue position for functions in SECTION 2.
  221 // 
  222 
  223 /* create a new local context for queue 'q'.  The first element in 
  224    'q' becomes the current element in the newly created context.
  225 */
  226 void local_init_context (Queue * q, Context * ctx);
  227 
  228 
  229 /* move to the first element in the 'q', maintaining a local position */
  230 void local_rewind_queue (Context * ctx);
  231 
  232 
  233 /* move to the next element in the 'q', maintaining a local position */
  234 void local_next_element (Context * ctx);
  235 
  236 
  237 /* allows update of current element, relative to current local position.
  238    The priority should not be changed by this function!
  239 */
  240 
  241 void local_update_current (Context * ctx, void *element);
  242 
  243 
  244 /* retrieve the element stored at the current local position in the 'q' */
  245 void local_peek_at_current (Context * ctx, void *element);
  246 
  247 
  248 /* return a pointer to the data portion of the element at the current
  249    local position */
  250 void *local_pointer_to_current (Context * ctx);
  251 
  252 
  253 /* return priority of element at current local position in the 'q' */
  254 int local_current_priority (Context * ctx);
  255 
  256 
  257 /* delete the element stored at the current local position */
  258 void local_delete_current (Context * ctx);
  259 
  260 
  261 /* has the current local position in 'q' moved beyond the last valid
  262    element?  Returns TRUE if so, FALSE otherwise.
  263 */
  264 int local_end_of_queue (Context * ctx);
  265 
  266 
  267 #endif
  268 
  269 
  270 /*** QUICK REFERENCE ***
  271 
  272 // SECTION 1
  273 void init_queue(Queue *q, int elementsize, int duplicates, 
  274         int (*compare)(void *e1, void *e2), int priority_is_tag_only);
  275 void destroy_queue(Queue *q);
  276 void add_to_queue(Queue *q, void *element, int priority);
  277 void remove_from_front(Queue *q, void *element);
  278 int element_in_queue(Queue *q, void *element);
  279 int empty_queue(Queue *q);
  280 int queue_length(Queue *q);
  281 void copy_queue(Queue *q1, Queue *q2);
  282 int equal_queues(Queue q1, Queue *q2);
  283 void merge_queues(Queue *q1, Queue *q2);
  284 
  285 // SECTION 2
  286 
  287 void rewind_queue(Queue *q);
  288 void next_element(Queue *q);
  289 void update_current(Queue *q, void *element);
  290 void peek_at_current(Queue *q, void *element);
  291 void *pointer_to_current(Queue *q);
  292 int current_priority(Queue *q);
  293 void delete_current(Queue *q);
  294 int end_of_queue(Queue *q);
  295 
  296 // SECTION 3
  297 void local_init_context(Queue, *q, Context *ctx);
  298 void local_rewind_queue(Context *ctx);
  299 void local_next_element(Context *ctx);
  300 void local_update_current(Context *ctx, void *element);
  301 void local_peek_at_current(Context *ctx, void *element);
  302 void local_*pointer_to_current(Context *ctx);
  303 int local_current_priority(Context *ctx);
  304 void local_delete_current(Context *ctx);
  305 int local_end_of_queue(Context *ctx);
  306  *** QUICK REFERENCE ***/