1 /** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
\r
2 * This file is part of clib library
\r
3 * Copyright (C) 2011 Avinash Dongre ( dongre.avinash@gmail.com )
\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
12 * The above copyright notice and this permission notice shall be included in
\r
13 * all copies or substantial portions of the Software.
\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
22 ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **/
\r
28 #define CLIB_DEQUE_INDEX(x) ((char *)(pDeq)->pElements + (sizeof(struct clib_object) * (x)))
\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
35 return CLIB_ARRAY_INSERT_FAILED;
\r
37 pDeq->pElements[index] = pObject;
\r
38 pDeq->no_of_elements++;
\r
42 static struct clib_deque*
\r
43 grow_deque ( struct clib_deque *pDeq ) {
\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
52 new_clib_deque( int deq_size , clib_compare fn_c, clib_destroy fn_d) {
\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
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
61 if ( pDeq == (struct clib_deque*)0 )
\r
62 return (struct clib_deque*)0;
\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
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
77 if ( pDeq->tail == pDeq->no_max_elements )
\r
78 pDeq = grow_deque(pDeq);
\r
80 insert_clib_deque(pDeq, pDeq->tail, elem, elem_size);
\r
83 return CLIB_ERROR_SUCCESS;
\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
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
101 insert_clib_deque(pDeq, pDeq->head, elem, elem_size);
\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
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
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
127 if ( pDeq->destruct_fn ) {
\r
129 if ( element_at_clib_deque( pDeq, pDeq->tail - 1, &elem ) == CLIB_ERROR_SUCCESS )
\r
130 pDeq->destruct_fn(elem);
\r
132 delete_clib_object(pDeq->pElements[pDeq->tail - 1]);
\r
134 pDeq->no_of_elements--;
\r
136 return CLIB_ERROR_SUCCESS;
\r
141 pop_front_clib_deque(struct clib_deque *pDeq) {
\r
143 if ( pDeq == (struct clib_deque*)0 )
\r
144 return CLIB_DEQUE_NOT_INITIALIZED;
\r
146 if ( pDeq->destruct_fn ) {
\r
148 if ( element_at_clib_deque( pDeq, pDeq->head + 1, &elem ) == CLIB_ERROR_SUCCESS )
\r
149 pDeq->destruct_fn(elem);
\r
151 delete_clib_object(pDeq->pElements[pDeq->head + 1]);
\r
154 pDeq->no_of_elements--;
\r
156 return CLIB_ERROR_SUCCESS;
\r
159 empty_clib_deque (struct clib_deque *pDeq) {
\r
160 if ( pDeq == (struct clib_deque*)0 )
\r
163 return pDeq->no_of_elements == 0 ? clib_true : clib_false;
\r
166 size_clib_deque( struct clib_deque *pDeq ) {
\r
167 if ( pDeq == (struct clib_deque*)0 )
\r
170 return pDeq->no_of_elements - 1;
\r
174 element_at_clib_deque (struct clib_deque *pDeq, int index, void**elem) {
\r
176 clib_error rc = CLIB_ERROR_SUCCESS;
\r
179 return CLIB_DEQUE_NOT_INITIALIZED;
\r
181 get_raw_clib_object ( pDeq->pElements[index], elem );
\r
186 delete_clib_deque ( struct clib_deque *pDeq ) {
\r
189 if ( pDeq == (struct clib_deque*)0 )
\r
190 return CLIB_ERROR_SUCCESS;
\r
192 if ( pDeq->destruct_fn ) {
\r
193 for ( i = pDeq->head + 1; i < pDeq->tail; i++ ){
\r
195 if ( element_at_clib_deque( pDeq, i, &elem ) == CLIB_ERROR_SUCCESS ) {
\r
196 pDeq->destruct_fn(elem);
\r
200 for ( i = pDeq->head + 1; i < pDeq->tail; i++ ){
\r
201 delete_clib_object(pDeq->pElements[i]);
\r
203 free ( pDeq->pElements);
\r
206 return CLIB_ERROR_SUCCESS;
\r
209 for_each_clib_deque ( struct clib_deque *pDeq, void (*fn)(void*)) {
\r
211 for ( index = pDeq->head + 1; index < pDeq->tail; index++ ){
\r
213 if ( element_at_clib_deque( pDeq, index, &elem ) == CLIB_ERROR_SUCCESS ) {
\r