core/complib/cl_ptr_vector.c

   1 /*\r
   2  * Copyright (c) 2005 SilverStorm Technologies.  All rights reserved.\r
   3  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved. \r
   4  *\r
   5  * This software is available to you under the OpenIB.org BSD license\r
   6  * below:\r
   7  *\r
   8  *     Redistribution and use in source and binary forms, with or\r
   9  *     without modification, are permitted provided that the following\r
  10  *     conditions are met:\r
  11  *\r
  12  *      - Redistributions of source code must retain the above\r
  13  *        copyright notice, this list of conditions and the following\r
  14  *        disclaimer.\r
  15  *\r
  16  *      - Redistributions in binary form must reproduce the above\r
  17  *        copyright notice, this list of conditions and the following\r
  18  *        disclaimer in the documentation and/or other materials\r
  19  *        provided with the distribution.\r
  20  *\r
  21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,\r
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF\r
  23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND\r
  24  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS\r
  25  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN\r
  26  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
  27  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  28  * SOFTWARE.\r
  29  *\r
  30  * $Id$\r
  31  */\r
  32 \r
  33 \r
  34 /*\r
  35  * Abstract:\r
  36  *      This file contains ivector and isvector implementations.\r
  37  *\r
  38  * Environment:\r
  39  *      All\r
  40  */\r
  41 \r
  42 \r
  43 #include <complib/cl_ptr_vector.h>\r
  44 #include <complib/cl_memory.h>\r
  45 \r
  46 \r
  47 void\r
  48 cl_ptr_vector_construct(\r
  49         IN      cl_ptr_vector_t* const  p_vector )\r
  50 {\r
  51         CL_ASSERT( p_vector );\r
  52 \r
  53         cl_memclr( p_vector, sizeof(cl_ptr_vector_t) );\r
  54 \r
  55         p_vector->state = CL_UNINITIALIZED;\r
  56 }\r
  57 \r
  58 \r
  59 cl_status_t\r
  60 cl_ptr_vector_init(\r
  61         IN      cl_ptr_vector_t* const  p_vector,\r
  62         IN      const size_t                    min_cap,\r
  63         IN      const size_t                    grow_size )\r
  64 {\r
  65         cl_status_t     status = CL_SUCCESS;\r
  66 \r
  67         CL_ASSERT( p_vector );\r
  68 \r
  69         cl_ptr_vector_construct( p_vector );\r
  70 \r
  71         p_vector->grow_size = grow_size;\r
  72 \r
  73         /*\r
  74          * Set the state to initialized so that the call to set_size\r
  75          * doesn't assert.\r
  76          */\r
  77         p_vector->state = CL_INITIALIZED;\r
  78 \r
  79         /* get the storage needed by the user */\r
  80         if( min_cap )\r
  81         {\r
  82                 status = cl_ptr_vector_set_capacity( p_vector, min_cap );\r
  83                 if( status != CL_SUCCESS )\r
  84                         cl_ptr_vector_destroy( p_vector );\r
  85         }\r
  86 \r
  87         return( status );\r
  88 }\r
  89 \r
  90 \r
  91 void\r
  92 cl_ptr_vector_destroy(\r
  93         IN      cl_ptr_vector_t* const  p_vector )\r
  94 {\r
  95         CL_ASSERT( p_vector );\r
  96         CL_ASSERT( cl_is_state_valid( p_vector->state ) );\r
  97 \r
  98         /* Call the user's destructor for each element in the array. */\r
  99         if( p_vector->state == CL_INITIALIZED )\r
 100         {\r
 101                 /* Destroy the page vector. */\r
 102                 if( p_vector->p_ptr_array )\r
 103                 {\r
 104                         cl_free( (void*)p_vector->p_ptr_array );\r
 105                         p_vector->p_ptr_array = NULL;\r
 106                 }\r
 107         }\r
 108 \r
 109         p_vector->state = CL_UNINITIALIZED;\r
 110 }\r
 111 \r
 112 \r
 113 cl_status_t\r
 114 cl_ptr_vector_at(\r
 115         IN      const cl_ptr_vector_t* const    p_vector,\r
 116         IN      const size_t                                    index,\r
 117         OUT     void** const                                    p_element )\r
 118 {\r
 119         CL_ASSERT( p_vector );\r
 120         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 121 \r
 122         /* Range check */\r
 123         if( index >= p_vector->size )\r
 124                 return( CL_INVALID_PARAMETER );\r
 125 \r
 126         *p_element = cl_ptr_vector_get( p_vector, index );\r
 127         return( CL_SUCCESS );\r
 128 }\r
 129 \r
 130 \r
 131 cl_status_t\r
 132 cl_ptr_vector_set(\r
 133         IN      cl_ptr_vector_t* const  p_vector,\r
 134         IN      const size_t                    index,\r
 135         IN      const void* const               element )\r
 136 {\r
 137         cl_status_t     status;\r
 138 \r
 139         CL_ASSERT( p_vector );\r
 140         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 141 \r
 142         /* Determine if the vector has room for this element. */\r
 143         if( index >= p_vector->size )\r
 144         {\r
 145                 /* Resize to accomodate the given index. */\r
 146                 status = cl_ptr_vector_set_size( p_vector, index + 1 );\r
 147 \r
 148                 /* Check for failure on or before the given index. */\r
 149                 if( (status != CL_SUCCESS) && (p_vector->size < index) )\r
 150                         return( status );\r
 151         }\r
 152 \r
 153         /* At this point, the array is guaranteed to be big enough */\r
 154         p_vector->p_ptr_array[index] = element;\r
 155 \r
 156         return( CL_SUCCESS );\r
 157 }\r
 158 \r
 159 \r
 160 void*\r
 161 cl_ptr_vector_remove(\r
 162         IN      cl_ptr_vector_t* const  p_vector,\r
 163         IN      const size_t                    index )\r
 164 {\r
 165         size_t          src;\r
 166         const void      *element;\r
 167 \r
 168         CL_ASSERT( p_vector );\r
 169         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 170         CL_ASSERT( p_vector->size > index );\r
 171 \r
 172         /* Store a copy of the element to return. */\r
 173         element = p_vector->p_ptr_array[index];\r
 174         /* Shift all items above the removed item down. */\r
 175         if( index < --p_vector->size )\r
 176         {\r
 177                 for( src = index; src < p_vector->size; src++ )\r
 178                         p_vector->p_ptr_array[src] = p_vector->p_ptr_array[src + 1];\r
 179         }\r
 180         /* Clear the entry for the element just outside of the new upper bound. */\r
 181         p_vector->p_ptr_array[p_vector->size] = NULL;\r
 182 \r
 183         return( (void*)element );\r
 184 }\r
 185 \r
 186 \r
 187 cl_status_t\r
 188 cl_ptr_vector_set_capacity(\r
 189         IN      cl_ptr_vector_t* const  p_vector,\r
 190         IN      const size_t                    new_capacity )\r
 191 {\r
 192         void                    *p_new_ptr_array;\r
 193 \r
 194         CL_ASSERT( p_vector );\r
 195         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 196 \r
 197         /* Do we have to do anything here? */\r
 198         if( new_capacity <= p_vector->capacity )\r
 199         {\r
 200                 /* Nope */\r
 201                 return( CL_SUCCESS );\r
 202         }\r
 203 \r
 204         /* Allocate our pointer array. */\r
 205         p_new_ptr_array = cl_zalloc( new_capacity * sizeof(void*) );\r
 206         if( !p_new_ptr_array )\r
 207                 return( CL_INSUFFICIENT_MEMORY );\r
 208 \r
 209         if( p_vector->p_ptr_array )\r
 210         {\r
 211                 /* Copy the old pointer array into the new. */\r
 212                 cl_memcpy( p_new_ptr_array, p_vector->p_ptr_array,\r
 213                         p_vector->capacity * sizeof(void*) );\r
 214 \r
 215                 /* Free the old pointer array. */\r
 216                 cl_free( (void*)p_vector->p_ptr_array );\r
 217         }\r
 218 \r
 219         /* Set the new array. */\r
 220         p_vector->p_ptr_array = p_new_ptr_array;\r
 221 \r
 222         /* Update the vector with the new capactity. */\r
 223         p_vector->capacity = new_capacity;\r
 224 \r
 225         return( CL_SUCCESS );\r
 226 }\r
 227 \r
 228 \r
 229 cl_status_t\r
 230 cl_ptr_vector_set_size(\r
 231         IN      cl_ptr_vector_t* const  p_vector,\r
 232         IN      const size_t                    size )\r
 233 {\r
 234         cl_status_t     status;\r
 235         size_t          new_capacity;\r
 236 \r
 237         CL_ASSERT( p_vector );\r
 238         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 239 \r
 240         /* Check to see if the requested size is the same as the existing size. */\r
 241         if( size == p_vector->size )\r
 242                 return( CL_SUCCESS );\r
 243 \r
 244         /* Determine if the vector has room for this element. */\r
 245         if( size > p_vector->capacity )\r
 246         {\r
 247                 if( !p_vector->grow_size )\r
 248                         return( CL_INSUFFICIENT_MEMORY );\r
 249 \r
 250                 /* Calculate the new capacity, taking into account the grow size. */\r
 251                 new_capacity = size;\r
 252                 if( size % p_vector->grow_size )\r
 253                 {\r
 254                         /* Round up to nearest grow_size boundary. */\r
 255                         new_capacity += p_vector->grow_size -\r
 256                                 (size % p_vector->grow_size);\r
 257                 }\r
 258 \r
 259                 status = cl_ptr_vector_set_capacity( p_vector, new_capacity );\r
 260                 if( status != CL_SUCCESS )\r
 261                         return( status );\r
 262         }\r
 263 \r
 264         p_vector->size = size;\r
 265         return( CL_SUCCESS );\r
 266 }\r
 267 \r
 268 \r
 269 cl_status_t\r
 270 cl_ptr_vector_set_min_size(\r
 271         IN      cl_ptr_vector_t* const  p_vector,\r
 272         IN      const size_t                    min_size )\r
 273 {\r
 274         CL_ASSERT( p_vector );\r
 275         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 276 \r
 277         if( min_size > p_vector->size )\r
 278         {\r
 279                 /* We have to resize the array */\r
 280                 return( cl_ptr_vector_set_size( p_vector, min_size ) );\r
 281         }\r
 282 \r
 283         /* We didn't have to do anything */\r
 284         return( CL_SUCCESS );\r
 285 }\r
 286 \r
 287 \r
 288 void\r
 289 cl_ptr_vector_apply_func(\r
 290         IN      const cl_ptr_vector_t* const    p_vector,\r
 291         IN      cl_pfn_ptr_vec_apply_t                  pfn_callback,\r
 292         IN      const void* const                               context )\r
 293 {\r
 294         size_t  i;\r
 295 \r
 296         CL_ASSERT( p_vector );\r
 297         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 298         CL_ASSERT( pfn_callback );\r
 299 \r
 300         for( i = 0; i < p_vector->size; i++ )\r
 301                 pfn_callback( i, (void*)p_vector->p_ptr_array[i], (void*)context );\r
 302 }\r
 303 \r
 304 \r
 305 size_t\r
 306 cl_ptr_vector_find_from_start(\r
 307         IN      const cl_ptr_vector_t* const    p_vector,\r
 308         IN      cl_pfn_ptr_vec_find_t                   pfn_callback,\r
 309         IN      const void* const                               context )\r
 310 {\r
 311         size_t  i;\r
 312 \r
 313         CL_ASSERT( p_vector );\r
 314         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 315         CL_ASSERT( pfn_callback );\r
 316 \r
 317         for( i = 0; i < p_vector->size; i++ )\r
 318         {\r
 319                 /* Invoke the callback */\r
 320                 if( pfn_callback( i, (void*)p_vector->p_ptr_array[i],\r
 321                         (void*)context ) == CL_SUCCESS )\r
 322                 {\r
 323                         break;\r
 324                 }\r
 325         }\r
 326         return( i );\r
 327 }\r
 328 \r
 329 \r
 330 size_t\r
 331 cl_ptr_vector_find_from_end(\r
 332         IN      const cl_ptr_vector_t* const    p_vector,\r
 333         IN      cl_pfn_ptr_vec_find_t                   pfn_callback,\r
 334         IN      const void* const                               context )\r
 335 {\r
 336         size_t  i;\r
 337 \r
 338         CL_ASSERT( p_vector );\r
 339         CL_ASSERT( p_vector->state == CL_INITIALIZED );\r
 340         CL_ASSERT( pfn_callback );\r
 341 \r
 342         i = p_vector->size;\r
 343 \r
 344         while( i )\r
 345         {\r
 346                 /* Invoke the callback for the current element. */\r
 347                 if( pfn_callback( i, (void*)p_vector->p_ptr_array[--i],\r
 348                         (void*)context ) == CL_SUCCESS )\r
 349                 {\r
 350                         return( i );\r
 351                 }\r
 352         }\r
 353 \r
 354         return( p_vector->size );\r
 355 }\r
 356 \r
 357 \r