--- /dev/null
+/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
+ * This file is part of clib library\r
+ * Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
+ *\r
+ * Permission is hereby granted, free of charge, to any person obtaining a copy\r
+ * of this software and associated documentation files (the "Software"), to deal\r
+ * in the Software without restriction, including without limitation the rights\r
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
+ * copies of the Software, and to permit persons to whom the Software is\r
+ * furnished to do so, subject to the following conditions:\r
+ * \r
+ * The above copyright notice and this permission notice shall be included in\r
+ * all copies or substantial portions of the Software.\r
+ * \r
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
+ * THE SOFTWARE.\r
+ ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
+\r
+#include "c_lib.h"\r
+\r
+#include <string.h>\r
+\r
+#define CLIB_DEQUE_INDEX(x) ((char *)(pDeq)->pElements + (sizeof(struct clib_object) * (x)))\r
+\r
+static clib_error \r
+insert_clib_deque ( struct clib_deque *pDeq, int index, void *elem,size_t elem_size) {\r
+ clib_error rc = CLIB_ERROR_SUCCESS;\r
+ struct clib_object* pObject = new_clib_object ( elem, elem_size );\r
+ if ( ! pObject )\r
+ return CLIB_ARRAY_INSERT_FAILED;\r
+\r
+ pDeq->pElements[index] = pObject;\r
+ pDeq->no_of_elements++;\r
+ return rc;\r
+}\r
+\r
+static struct clib_deque*\r
+grow_deque ( struct clib_deque *pDeq ) {\r
+\r
+ pDeq->no_max_elements = pDeq->no_max_elements * 2;\r
+ pDeq->pElements = (struct clib_object**) realloc ( pDeq->pElements, \r
+ pDeq->no_max_elements * sizeof ( struct clib_object*));\r
+ return pDeq;\r
+\r
+}\r
+struct clib_deque* \r
+new_clib_deque( int deq_size , clib_compare fn_c, clib_destroy fn_d) {\r
+\r
+ struct clib_deque *pDeq = (struct clib_deque*)malloc(sizeof(struct clib_deque));\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return (struct clib_deque*)0;\r
+\r
+ pDeq->no_max_elements = deq_size < 8 ? 8 : deq_size;\r
+ pDeq->pElements = (struct clib_object**) malloc(pDeq->no_max_elements * sizeof(struct clib_object*));\r
+\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return (struct clib_deque*)0;\r
+\r
+ pDeq->compare_fn = fn_c;\r
+ pDeq->destruct_fn = fn_d;\r
+ pDeq->head = (int)pDeq->no_max_elements / 2;\r
+ pDeq->tail = pDeq->head + 1;\r
+ pDeq->no_of_elements = 0; \r
+\r
+ return pDeq;\r
+}\r
+clib_error \r
+push_back_clib_deque(struct clib_deque *pDeq, void *elem, size_t elem_size) {\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return CLIB_DEQUE_NOT_INITIALIZED;\r
+\r
+ if ( pDeq->tail == pDeq->no_max_elements )\r
+ pDeq = grow_deque(pDeq);\r
+\r
+ insert_clib_deque(pDeq, pDeq->tail, elem, elem_size);\r
+ pDeq->tail++;\r
+\r
+ return CLIB_ERROR_SUCCESS;\r
+}\r
+clib_error \r
+push_front_clib_deque(struct clib_deque *pDeq, void *elem,size_t elem_size) {\r
+ clib_error rc = CLIB_ERROR_SUCCESS; \r
+ int to = 0;\r
+ int from = 0;\r
+ int count = 0;\r
+\r
+ if ( pDeq->head == 0 ) {\r
+ pDeq = grow_deque(pDeq);\r
+ to = (pDeq->no_max_elements - pDeq->no_of_elements)/2;\r
+ from = pDeq->head + 1;\r
+ count = pDeq->tail - from + 1;\r
+ memmove (&(pDeq->pElements[to]), &(pDeq->pElements[from]), count * sizeof (struct clib_object*));\r
+ pDeq->head = to - 1;\r
+ pDeq->tail = pDeq->head + count;\r
+ }\r
+ insert_clib_deque(pDeq, pDeq->head, elem, elem_size);\r
+ pDeq->head--;\r
+ return rc;\r
+}\r
+\r
+clib_error \r
+front_clib_deque (struct clib_deque *pDeq, void *elem) {\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return CLIB_DEQUE_NOT_INITIALIZED;\r
+ element_at_clib_deque ( pDeq, pDeq->head + 1, elem );\r
+ return CLIB_ERROR_SUCCESS;\r
+}\r
+\r
+clib_error \r
+back_clib_deque (struct clib_deque *pDeq, void *elem) {\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return CLIB_DEQUE_NOT_INITIALIZED;\r
+ element_at_clib_deque ( pDeq, pDeq->tail - 1, elem );\r
+ return CLIB_ERROR_SUCCESS;\r
+}\r
+\r
+clib_error \r
+pop_back_clib_deque (struct clib_deque *pDeq) {\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return CLIB_DEQUE_NOT_INITIALIZED;\r
+\r
+ if ( pDeq->destruct_fn ) {\r
+ void *elem;\r
+ if ( element_at_clib_deque( pDeq, pDeq->tail - 1, &elem ) == CLIB_ERROR_SUCCESS ) \r
+ pDeq->destruct_fn(elem);\r
+ }\r
+ delete_clib_object(pDeq->pElements[pDeq->tail - 1]);\r
+ pDeq->tail--;\r
+ pDeq->no_of_elements--;\r
+\r
+ return CLIB_ERROR_SUCCESS;\r
+\r
+}\r
+\r
+clib_error \r
+pop_front_clib_deque(struct clib_deque *pDeq) {\r
+ \r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return CLIB_DEQUE_NOT_INITIALIZED;\r
+\r
+ if ( pDeq->destruct_fn ) {\r
+ void *elem;\r
+ if ( element_at_clib_deque( pDeq, pDeq->head + 1, &elem ) == CLIB_ERROR_SUCCESS ) \r
+ pDeq->destruct_fn(elem);\r
+ }\r
+ delete_clib_object(pDeq->pElements[pDeq->head + 1]);\r
+\r
+ pDeq->head++;\r
+ pDeq->no_of_elements--;\r
+\r
+ return CLIB_ERROR_SUCCESS;\r
+}\r
+clib_bool \r
+empty_clib_deque (struct clib_deque *pDeq) {\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return clib_true;\r
+\r
+ return pDeq->no_of_elements == 0 ? clib_true : clib_false;\r
+}\r
+int \r
+size_clib_deque( struct clib_deque *pDeq ) {\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return clib_true;\r
+\r
+ return pDeq->no_of_elements - 1;\r
+}\r
+\r
+clib_error \r
+element_at_clib_deque (struct clib_deque *pDeq, int index, void**elem) {\r
+\r
+ clib_error rc = CLIB_ERROR_SUCCESS;\r
+\r
+ if ( ! pDeq )\r
+ return CLIB_DEQUE_NOT_INITIALIZED;\r
+\r
+ get_raw_clib_object ( pDeq->pElements[index], elem );\r
+ return rc;\r
+}\r
+\r
+clib_error\r
+delete_clib_deque ( struct clib_deque *pDeq ) {\r
+ int i = 0;\r
+\r
+ if ( pDeq == (struct clib_deque*)0 )\r
+ return CLIB_ERROR_SUCCESS;\r
+\r
+ if ( pDeq->destruct_fn ) {\r
+ for ( i = pDeq->head + 1; i < pDeq->tail; i++ ){\r
+ void *elem;\r
+ if ( element_at_clib_deque( pDeq, i, &elem ) == CLIB_ERROR_SUCCESS ) {\r
+ pDeq->destruct_fn(elem);\r
+ }\r
+ }\r
+ }\r
+ for ( i = pDeq->head + 1; i < pDeq->tail; i++ ){\r
+ delete_clib_object(pDeq->pElements[i]);\r
+ }\r
+ free ( pDeq->pElements);\r
+ free ( pDeq );\r
+\r
+ return CLIB_ERROR_SUCCESS;\r
+}\r
+void \r
+for_each_clib_deque ( struct clib_deque *pDeq, void (*fn)(void*)) {\r
+ int index = 0;\r
+ for ( index = pDeq->head + 1; index < pDeq->tail; index++ ){\r
+ void *elem;\r
+ if ( element_at_clib_deque( pDeq, index, &elem ) == CLIB_ERROR_SUCCESS ) {\r
+ (fn)(elem);\r
+ free ( elem );\r
+ }\r
+ }\r
+}\r