refactoring priority queue.

activesys · Nov 11, 2012 · 98951a8 · 98951a8
1 parent 0ec8db2
commit 98951a8
Show file tree

Hide file tree

Showing 11 changed files with 967 additions and 129 deletions.
diff --git a/cstl/cstl_priority_queue.h b/cstl/cstl_priority_queue.h
@@ -29,52 +29,106 @@ extern "C" {
 /** include section **/
 
 /** constant declaration and macro section **/
-/* create new priority queue */
+/**
+ * Create priority queue adaptor.
+ * @param ...    type name.
+ * @return priority queue adaptor pointer, if create queue successfully, else return NULL.
+ * @remarks if s_typename == NULL, the behavior is undefined. s_typename must be c builtin type, libcstl builtin type or
+ *          user defined type, otherwise creation will be failure.
+ */
 #define create_priority_queue(...) _create_priority_queue(#__VA_ARGS__)
-/* push */
-#define priority_queue_push(pt_pqueue, elem)\
-    _priority_queue_push((pt_pqueue), (elem))
+
+/**
+ * Add specificed element at the back of priority queue. 
+ * @param ppque_pqueue    priority queue adaptor.
+ * @param elem            specificed element.
+ * @return void.
+ * @remarks if ppque_pqueue == NULL or priority queue is uninitialized, then the behavior is undefined. the type of specificed
+ *          element and priority queue element type must be same, otherwise the behavior is undefined. the first specificed is
+ *          in use, others are not in use.
+ */
+#define priority_queue_push(ppque_pqueue, elem) _priority_queue_push((ppque_pqueue), (elem))
 
 /** data type declaration and struct, union, enum section **/
 
 /** exported global variable declaration section **/
 
 /** exported function prototype section **/
+/**
+ * Initialize an empty priority queue adaptor
+ * @param ppque_pqueue   priority queue adaptor.
+ * @return void.
+ * @remarks if ppque_pqueue == NULL, then the behavior is undefined. pque_queue must be created by create_priority_queue(), otherwise
+ *          the behavior is undefine.
+ */
+extern void priority_queue_init(priority_queue_t* ppque_pqueue);
 
-/* priority queue */
-/*
- * Initialization and destroy operation functions.
+/**
+ * Initialize an empty priority queue adaptor with user define priority rule.
+ * @param ppque_pqueue   priority queue adaptor.
+ * @param bfun_op        priority rule.
+ * @return void.
+ * @remarks if ppque_pqueue == NULL, then the behavior is undefined. pque_queue must be created by create_priority_queue(), otherwise
+ *          the behavior is undefine.
+ */
+extern void priority_queue_init_ex(priority_queue_t* ppque_pqueue, binary_function_t bfun_op);
+
+/**
+ * Initialize an priority queue adaptor from an exist priority queue.
+ * @param ppque_dest    destination priority queue adaptor.
+ * @param ppque_src     source priority queue_adaptor.
+ * @return void.
+ * @remarks destination and source priority queue adaptor must be valid, and must be have same element type, otherwise the behavior is undefined.
+ */
+extern void priority_queue_init_copy(priority_queue_t* ppque_dest, const priority_queue_t* cppque_src);
+
+/**
+ * Initialize an priority queue adaptor from an exist range.
+ * @param ppque_dest    destination priority queue adaptor.
+ * @param it_first      An iterator addressing the first element in the reange.
+ * @param it_last       An iterator addressing the last element in the range.
+ * @return void.
+ * @remarks destination priority queue adaptor and source range must be valid, and must be have same element type, otherwise the behavior is undefined.
+ */
+extern void priority_queue_init_copy_range(priority_queue_t* ppque_dest, input_iterator_t it_first, input_iterator_t it_last);
+
+/**
+ * Initialize an priority queue adaptor from an exist range with user define priority rule.
+ * @param ppque_dest    destination priority queue adaptor.
+ * @param it_first      An iterator addressing the first element in the reange.
+ * @param it_last       An iterator addressing the last element in the range.
+ * @param bfun_op       User defined priority rule.
+ * @return void.
+ * @remarks destination priority queue adaptor and source range must be valid, and must be have same element type, otherwise the behavior is undefined.
+ */
+extern void priority_queue_init_copy_range_ex(priority_queue_t* ppque_dest, input_iterator_t it_first, input_iterator_t it_last, binary_function_t bfun_op);
+
+/**
+ * Destroy priority queue adaptor.
+ * @param ppque_pqueue   priority queue adaptor.
+ * @return void.
+ * @remraks if ppque_pqueue == NULLL, then the behavior is undefined. ppque_pqueue must be initialized or created by
+ *          create_priority_queue(), otherwise the behavior is undefined.
  */
-extern void priority_queue_init(priority_queue_t* pt_pqueue);
-extern void priority_queue_init_ex(
-    priority_queue_t* pt_pqueue, binary_function_t t_binary_op);
-extern void priority_queue_destroy(priority_queue_t* pt_pqueue);
-extern void priority_queue_init_copy(
-    priority_queue_t* pt_pqueuedest, const priority_queue_t* cpt_pqueuesrc);
-extern void priority_queue_init_copy_range(
-    priority_queue_t* pt_pqueuedest,
-    random_access_iterator_t t_first, random_access_iterator_t t_last);
-extern void priority_queue_init_copy_range_ex(
-    priority_queue_t* pt_pqueuedest, random_access_iterator_t t_first,
-    random_access_iterator_t t_last, binary_function_t t_binary_op);
+extern void priority_queue_destroy(priority_queue_t* ppque_pqueue);
 
 /*
  * Assign operator functions.
  */
 extern void priority_queue_assign(
-    priority_queue_t* pt_pqueuedest, const priority_queue_t* cpt_pqueuesrc);
+    priority_queue_t* ppque_pqueuedest, const priority_queue_t* cppque_pqueuesrc);
 
 /*
  * priority_queue_t size operation functions.
  */
-extern bool_t priority_queue_empty(const priority_queue_t* cpt_pqueue);
-extern size_t priority_queue_size(const priority_queue_t* cpt_pqueue);
-extern void* priority_queue_top(const priority_queue_t* cpt_pqueue);
+extern bool_t priority_queue_empty(const priority_queue_t* cppque_pqueue);
+extern size_t priority_queue_size(const priority_queue_t* cppque_pqueue);
+extern void* priority_queue_top(const priority_queue_t* cppque_pqueue);
 
 /*
  * Element access functions.
  */
-extern void priority_queue_pop(priority_queue_t* pt_pqueue);
+extern void priority_queue_pop(priority_queue_t* ppque_pqueue);
 
 #ifdef __cplusplus
 }

diff --git a/cstl/cstl_priority_queue_private.h b/cstl/cstl_priority_queue_private.h
@@ -31,7 +31,6 @@ extern "C" {
 /** constant declaration and macro section **/
 
 /** data type declaration and struct, union, enum section **/
-
 typedef struct _tagpriority_queue
 {
     vector_t          _t_vector;
@@ -41,19 +40,44 @@ typedef struct _tagpriority_queue
 /** exported global variable declaration section **/
 
 /** exported function prototype section **/
-
-/*
- * Create the new priority queue.
+/**
+ * Create priority queue adaptor.
+ * @param s_typename    type name.
+ * @return priority queue adaptor pointer, if create queue successfully, else return NULL.
+ * @remarks if s_typename == NULL, the behavior is undefined. s_typename must be c builtin type, libcstl builtin type or
+ *          user defined type, otherwise creation will be failure.
  */
 extern priority_queue_t* _create_priority_queue(const char* s_typename);
-extern bool_t _create_priority_queue_auxiliary(
-    priority_queue_t* pt_pqueue, const char* s_typename);
-extern void _priority_queue_destroy_auxiliary(priority_queue_t* pt_queue);
 
-/*
- * Append a copy of element at the top.
+/**
+ * Create priority queue adaptor auxiliary function.
+ * @param ppque_pqueue      priority queue adaptor.
+ * @param s_typename        type name.
+ * @return true if create priority queue adaptor successfully, otherwise return false.
+ * @remarks if ppque_pqueue == NULL or s_typename == NULL, the behavior is undefined. s_typename must be c builtin type,
+ *          libcstl builtin type or user defined type, otherwise creation will be failure.
+ */
+extern bool_t _create_priority_queue_auxiliary(priority_queue_t* ppque_pqueue, const char* s_typename);
+
+/**
+ * Destroy priority queue adaptor auxiliary function.
+ * @param ppque_pqueue   priority queue adaptor.
+ * @return void.
+ * @remarks if ppque_pqueue == NULL, then the behavior is undefined. priority queue adaptor must be initialized or created by
+ *          create_queue, otherwise the behavior is undefined.
+ */
+extern void _priority_queue_destroy_auxiliary(priority_queue_t* ppque_pqueue);
+
+/**
+ * Add specificed element at the back of priority queue. 
+ * @param ppque_pqueue    priority queue adaptor.
+ * @param ...             specificed element.
+ * @return void.
+ * @remarks if ppque_pqueue == NULL or priority queue is uninitialized, then the behavior is undefined. the type of specificed
+ *          element and priority queue element type must be same, otherwise the behavior is undefined. the first specificed is
+ *          in use, others are not in use.
  */
-extern void _priority_queue_push(priority_queue_t* pt_pqueue, ...);
+extern void _priority_queue_push(priority_queue_t* ppque_pqueue, ...);
 
 #ifdef __cplusplus
 }

diff --git a/src/cstl_priority_queue.c b/src/cstl_priority_queue.c
@@ -38,110 +38,112 @@
 /** local global variable definition section **/
 
 /** exported function implementation section **/
-
-void priority_queue_init(priority_queue_t* pt_pqueue)
+/**
+ * Initialize an empty priority queue adaptor
+ */
+void priority_queue_init(priority_queue_t* ppque_pqueue)
 {
-    priority_queue_init_ex(pt_pqueue, NULL);
+    priority_queue_init_ex(ppque_pqueue, NULL);
 }
 
-void priority_queue_init_ex(priority_queue_t* pt_pqueue, binary_function_t t_binary_op)
+/**
+ * Initialize an empty priority queue adaptor with user define priority rule.
+ */
+void priority_queue_init_ex(priority_queue_t* ppque_pqueue, binary_function_t t_binary_op)
 {
-    assert(pt_pqueue != NULL);
+    assert(ppque_pqueue != NULL);
 
-    vector_init(&pt_pqueue->_t_vector);
-    pt_pqueue->_t_binary_op = t_binary_op;
+    vector_init(&ppque_pqueue->_t_vector);
+    ppque_pqueue->_t_binary_op = t_binary_op;
 }
 
-void priority_queue_destroy(priority_queue_t* pt_pqueue)
+/**
+ * Destroy priority queue adaptor.
+ */
+void priority_queue_destroy(priority_queue_t* ppque_pqueue)
 {
-    _priority_queue_destroy_auxiliary(pt_pqueue);
-    free(pt_pqueue);
+    _priority_queue_destroy_auxiliary(ppque_pqueue);
+    free(ppque_pqueue);
 }
 
-void priority_queue_init_copy(
-    priority_queue_t* pt_pqueuedest, const priority_queue_t* cpt_pqueuesrc)
+/**
+ * Initialize an priority queue adaptor from an exist priority queue.
+ */
+void priority_queue_init_copy(priority_queue_t* ppque_dest, const priority_queue_t* cppque_src)
 {
-    assert(pt_pqueuedest != NULL && cpt_pqueuesrc != NULL);
+    assert(ppque_dest != NULL);
+    assert(cppque_src != NULL);
 
-    vector_init_copy(&pt_pqueuedest->_t_vector, &cpt_pqueuesrc->_t_vector);
-    pt_pqueuedest->_t_binary_op = cpt_pqueuesrc->_t_binary_op;
+    vector_init_copy(&ppque_dest->_t_vector, &cppque_src->_t_vector);
+    ppque_dest->_t_binary_op = cppque_src->_t_binary_op;
 }
 
-void priority_queue_init_copy_range(
-    priority_queue_t* pt_pqueuedest,
-    random_access_iterator_t t_first, random_access_iterator_t t_last)
+/**
+ * Initialize an priority queue adaptor from an exist range.
+ */
+void priority_queue_init_copy_range(priority_queue_t* ppque_dest, input_iterator_t it_first, input_iterator_t it_last)
 {
-    priority_queue_init_copy_range_ex(pt_pqueuedest, t_first, t_last, NULL);
+    priority_queue_init_copy_range_ex(ppque_dest, it_first, it_last, NULL);
 }
 
-void priority_queue_init_copy_range_ex(
-    priority_queue_t* pt_pqueuedest, random_access_iterator_t t_first,
-    random_access_iterator_t t_last, binary_function_t t_binary_op)
+/**
+ * Initialize an priority queue adaptor from an exist range with user define priority rule.
+ */
+void priority_queue_init_copy_range_ex(priority_queue_t* ppque_dest, input_iterator_t it_first, input_iterator_t it_last, binary_function_t bfun_op)
 {
-    assert(pt_pqueuedest != NULL);
+    assert(ppque_dest != NULL);
 
-    vector_init_copy_range(&pt_pqueuedest->_t_vector, t_first, t_last);
-    pt_pqueuedest->_t_binary_op = t_binary_op;
-
-    if(pt_pqueuedest->_t_binary_op == NULL)
-    {
-        algo_make_heap(
-            vector_begin(&pt_pqueuedest->_t_vector), vector_end(&pt_pqueuedest->_t_vector));
-    }
-    else
-    {
-        algo_make_heap_if(
-            vector_begin(&pt_pqueuedest->_t_vector), vector_end(&pt_pqueuedest->_t_vector),
-            pt_pqueuedest->_t_binary_op);
-    }
+    vector_init_copy_range(&ppque_dest->_t_vector, it_first, it_last);
+    ppque_dest->_t_binary_op = bfun_op;
+    algo_make_heap_if(vector_begin(&ppque_dest->_t_vector), vector_end(&ppque_dest->_t_vector), ppque_dest->_t_binary_op);
 }
 
 void priority_queue_assign(
-    priority_queue_t* pt_pqueuedest, const priority_queue_t* cpt_pqueuesrc)
+    priority_queue_t* ppque_pqueuedest, const priority_queue_t* cppque_pqueuesrc)
 {
-    assert(pt_pqueuedest != NULL && cpt_pqueuesrc != NULL);
+    assert(ppque_pqueuedest != NULL && cppque_pqueuesrc != NULL);
 
-    vector_assign(&pt_pqueuedest->_t_vector, &cpt_pqueuesrc->_t_vector);
-    pt_pqueuedest->_t_binary_op = cpt_pqueuesrc->_t_binary_op;
+    vector_assign(&ppque_pqueuedest->_t_vector, &cppque_pqueuesrc->_t_vector);
+    ppque_pqueuedest->_t_binary_op = cppque_pqueuesrc->_t_binary_op;
 }
 
-bool_t priority_queue_empty(const priority_queue_t* cpt_pqueue)
+bool_t priority_queue_empty(const priority_queue_t* cppque_pqueue)
 {
-    assert(cpt_pqueue != NULL);
+    assert(cppque_pqueue != NULL);
 
-    return vector_empty(&cpt_pqueue->_t_vector);
+    return vector_empty(&cppque_pqueue->_t_vector);
 }
 
-size_t priority_queue_size(const priority_queue_t* cpt_pqueue)
+size_t priority_queue_size(const priority_queue_t* cppque_pqueue)
 {
-    assert(cpt_pqueue != NULL);
+    assert(cppque_pqueue != NULL);
 
-    return vector_size(&cpt_pqueue->_t_vector);
+    return vector_size(&cppque_pqueue->_t_vector);
 }
 
-void* priority_queue_top(const priority_queue_t* cpt_pqueue)
+void* priority_queue_top(const priority_queue_t* cppque_pqueue)
 {
-    assert(cpt_pqueue != NULL);
+    assert(cppque_pqueue != NULL);
 
-    return vector_front(&cpt_pqueue->_t_vector);
+    return vector_front(&cppque_pqueue->_t_vector);
 }
 
-void priority_queue_pop(priority_queue_t* pt_pqueue)
+void priority_queue_pop(priority_queue_t* ppque_pqueue)
 {
-    assert(pt_pqueue != NULL);
+    assert(ppque_pqueue != NULL);
 
-    if(pt_pqueue->_t_binary_op == NULL)
+    if(ppque_pqueue->_t_binary_op == NULL)
     {
         algo_pop_heap(
-            vector_begin(&pt_pqueue->_t_vector), vector_end(&pt_pqueue->_t_vector));
+            vector_begin(&ppque_pqueue->_t_vector), vector_end(&ppque_pqueue->_t_vector));
     }
     else
     {
         algo_pop_heap_if(
-            vector_begin(&pt_pqueue->_t_vector), vector_end(&pt_pqueue->_t_vector),
-            pt_pqueue->_t_binary_op);
+            vector_begin(&ppque_pqueue->_t_vector), vector_end(&ppque_pqueue->_t_vector),
+            ppque_pqueue->_t_binary_op);
     }
-    vector_pop_back(&pt_pqueue->_t_vector);
+    vector_pop_back(&ppque_pqueue->_t_vector);
 }
 
 /** local function implementation section **/