git.ozlabs.org Git - ccan/blob - junkcode/dongre.avinash@gmail.com-clibutils/src/c_deque.c

   1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **\r
   2  *  This file is part of clib library\r
   3  *  Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )\r
   4  *\r
   5  *  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   6  *  of this software and associated documentation files (the "Software"), to deal\r
   7  *  in the Software without restriction, including without limitation the rights\r
   8  *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   9  *  copies of the Software, and to permit persons to whom the Software is\r
  10  *  furnished to do so, subject to the following conditions:\r
  11  * \r
  12  *  The above copyright notice and this permission notice shall be included in\r
  13  *  all copies or substantial portions of the Software.\r
  14  * \r
  15  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  16  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  17  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  18  *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  19  *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  20  *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\r
  21  *  THE SOFTWARE.\r
  22  ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/\r
  23 \r
  24 #include "c_lib.h"\r
  25 \r
  26 #include <string.h>\r
  27 \r
  28 #define CLIB_DEQUE_INDEX(x)  ((char *)(pDeq)->pElements + (sizeof(struct clib_object) * (x)))\r
  29 \r
  30 static clib_error \r
  31 insert_clib_deque ( struct clib_deque *pDeq, int index, void *elem,size_t elem_size) {\r
  32     clib_error rc           = CLIB_ERROR_SUCCESS;\r
  33     struct clib_object* pObject = new_clib_object ( elem, elem_size );\r
  34     if ( ! pObject )\r
  35         return CLIB_ARRAY_INSERT_FAILED;\r
  36 \r
  37     pDeq->pElements[index] = pObject;\r
  38     pDeq->no_of_elements++;\r
  39     return rc;\r
  40 }\r
  41 \r
  42 static struct clib_deque*\r
  43 grow_deque ( struct clib_deque *pDeq ) {\r
  44 \r
  45         pDeq->no_max_elements = pDeq->no_max_elements * 2;\r
  46     pDeq->pElements        = (struct clib_object**) realloc ( pDeq->pElements, \r
  47                                  pDeq->no_max_elements * sizeof ( struct clib_object*));\r
  48     return pDeq;\r
  49 \r
  50 }\r
  51 struct clib_deque*  \r
  52 new_clib_deque( int deq_size , clib_compare fn_c, clib_destroy fn_d) {\r
  53 \r
  54     struct clib_deque *pDeq = (struct clib_deque*)malloc(sizeof(struct clib_deque));\r
  55         if ( pDeq == (struct clib_deque*)0 )\r
  56                 return (struct clib_deque*)0;\r
  57 \r
  58     pDeq->no_max_elements  = deq_size < 8 ? 8 : deq_size;\r
  59     pDeq->pElements = (struct clib_object**) malloc(pDeq->no_max_elements * sizeof(struct clib_object*));\r
  60 \r
  61         if ( pDeq == (struct clib_deque*)0 )\r
  62                 return (struct clib_deque*)0;\r
  63 \r
  64     pDeq->compare_fn      = fn_c;\r
  65     pDeq->destruct_fn     = fn_d;\r
  66     pDeq->head            = (int)pDeq->no_max_elements / 2;\r
  67     pDeq->tail            = pDeq->head + 1;\r
  68     pDeq->no_of_elements  = 0;    \r
  69 \r
  70     return pDeq;\r
  71 }\r
  72 clib_error \r
  73 push_back_clib_deque(struct clib_deque *pDeq, void *elem, size_t elem_size) {\r
  74         if ( pDeq == (struct clib_deque*)0 )\r
  75                 return CLIB_DEQUE_NOT_INITIALIZED;\r
  76 \r
  77     if ( pDeq->tail == pDeq->no_max_elements )\r
  78         pDeq = grow_deque(pDeq);\r
  79 \r
  80     insert_clib_deque(pDeq, pDeq->tail, elem, elem_size);\r
  81     pDeq->tail++;\r
  82 \r
  83     return CLIB_ERROR_SUCCESS;\r
  84 }\r
  85 clib_error \r
  86 push_front_clib_deque(struct clib_deque *pDeq, void *elem,size_t elem_size) {\r
  87     clib_error rc = CLIB_ERROR_SUCCESS; \r
  88     int to        = 0;\r
  89     int from      = 0;\r
  90     int count     = 0;\r
  91 \r
  92     if ( pDeq->head == 0 ) {\r
  93         pDeq = grow_deque(pDeq);\r
  94         to    = (pDeq->no_max_elements - pDeq->no_of_elements)/2;\r
  95         from  = pDeq->head + 1;\r
  96         count = pDeq->tail - from + 1;\r
  97         memmove (&(pDeq->pElements[to]), &(pDeq->pElements[from]), count * sizeof (struct clib_object*));\r
  98         pDeq->head = to - 1;\r
  99         pDeq->tail  = pDeq->head + count;\r
 100     }\r
 101     insert_clib_deque(pDeq, pDeq->head, elem, elem_size);\r
 102     pDeq->head--;\r
 103     return rc;\r
 104 }\r
 105 \r
 106 clib_error     \r
 107 front_clib_deque (struct clib_deque *pDeq, void *elem) {\r
 108         if ( pDeq == (struct clib_deque*)0 )\r
 109                 return CLIB_DEQUE_NOT_INITIALIZED;\r
 110     element_at_clib_deque ( pDeq, pDeq->head + 1, elem );\r
 111     return CLIB_ERROR_SUCCESS;\r
 112 }\r
 113 \r
 114 clib_error \r
 115 back_clib_deque (struct clib_deque *pDeq, void *elem) {\r
 116         if ( pDeq == (struct clib_deque*)0 )\r
 117                 return CLIB_DEQUE_NOT_INITIALIZED;\r
 118     element_at_clib_deque ( pDeq, pDeq->tail - 1, elem );\r
 119     return CLIB_ERROR_SUCCESS;\r
 120 }\r
 121 \r
 122 clib_error     \r
 123 pop_back_clib_deque (struct clib_deque *pDeq) {\r
 124         if ( pDeq == (struct clib_deque*)0 )\r
 125                 return CLIB_DEQUE_NOT_INITIALIZED;\r
 126 \r
 127     if ( pDeq->destruct_fn ) {\r
 128         void *elem;\r
 129         if ( element_at_clib_deque( pDeq, pDeq->tail - 1, &elem ) == CLIB_ERROR_SUCCESS ) \r
 130             pDeq->destruct_fn(elem);\r
 131     }\r
 132     delete_clib_object(pDeq->pElements[pDeq->tail - 1]);\r
 133     pDeq->tail--;\r
 134     pDeq->no_of_elements--;\r
 135 \r
 136     return CLIB_ERROR_SUCCESS;\r
 137 \r
 138 }\r
 139 \r
 140 clib_error     \r
 141 pop_front_clib_deque(struct clib_deque *pDeq) {\r
 142     \r
 143         if ( pDeq == (struct clib_deque*)0 )\r
 144                 return CLIB_DEQUE_NOT_INITIALIZED;\r
 145 \r
 146     if ( pDeq->destruct_fn ) {\r
 147         void *elem;\r
 148         if ( element_at_clib_deque( pDeq, pDeq->head + 1, &elem ) == CLIB_ERROR_SUCCESS ) \r
 149             pDeq->destruct_fn(elem);\r
 150     }\r
 151     delete_clib_object(pDeq->pElements[pDeq->head + 1]);\r
 152 \r
 153     pDeq->head++;\r
 154     pDeq->no_of_elements--;\r
 155 \r
 156     return CLIB_ERROR_SUCCESS;\r
 157 }\r
 158 clib_bool      \r
 159 empty_clib_deque (struct clib_deque *pDeq) {\r
 160         if ( pDeq == (struct clib_deque*)0 )\r
 161                 return clib_true;\r
 162 \r
 163     return pDeq->no_of_elements == 0 ? clib_true : clib_false;\r
 164 }\r
 165 int \r
 166 size_clib_deque( struct clib_deque *pDeq ) {\r
 167         if ( pDeq == (struct clib_deque*)0 )\r
 168                 return clib_true;\r
 169 \r
 170     return pDeq->no_of_elements - 1;\r
 171 }\r
 172 \r
 173 clib_error \r
 174 element_at_clib_deque (struct clib_deque *pDeq, int index, void**elem) {\r
 175 \r
 176     clib_error rc = CLIB_ERROR_SUCCESS;\r
 177 \r
 178     if ( ! pDeq )\r
 179         return CLIB_DEQUE_NOT_INITIALIZED;\r
 180 \r
 181     get_raw_clib_object ( pDeq->pElements[index], elem );\r
 182     return rc;\r
 183 }\r
 184 \r
 185 clib_error\r
 186 delete_clib_deque ( struct clib_deque *pDeq ) {\r
 187     int i = 0;\r
 188 \r
 189         if ( pDeq == (struct clib_deque*)0 )\r
 190                 return CLIB_ERROR_SUCCESS;\r
 191 \r
 192     if ( pDeq->destruct_fn ) {\r
 193         for ( i = pDeq->head + 1; i < pDeq->tail; i++ ){\r
 194             void *elem;\r
 195             if ( element_at_clib_deque( pDeq, i, &elem ) == CLIB_ERROR_SUCCESS ) {\r
 196                 pDeq->destruct_fn(elem);\r
 197             }\r
 198         }\r
 199     }\r
 200     for ( i = pDeq->head + 1; i < pDeq->tail; i++ ){\r
 201         delete_clib_object(pDeq->pElements[i]);\r
 202     }\r
 203     free ( pDeq->pElements);\r
 204     free ( pDeq );\r
 205 \r
 206     return CLIB_ERROR_SUCCESS;\r
 207 }\r
 208 void \r
 209 for_each_clib_deque ( struct clib_deque *pDeq, void (*fn)(void*)) {\r
 210         int index = 0;\r
 211         for ( index = pDeq->head + 1; index < pDeq->tail; index++ ){\r
 212                 void *elem;\r
 213                 if ( element_at_clib_deque( pDeq, index, &elem ) == CLIB_ERROR_SUCCESS ) {\r
 214                         (fn)(elem);\r
 215                         free ( elem );\r
 216                 }\r
 217         }\r
 218 }\r