base
gml_DynamicArray_T.h

00001 // gml_DynamicArray_T.h --
00002 //
00003 //    See "gmlDynamicArray.h".
00004 //
00005 //  Copyright (c) 1998-2004 CLIPS-IMAG
00006 //
00007 //  See the file "gml_LicenseTerms.txt" for information on usage and redistribution
00008 //  of this file, and for a DISCLAIMER OF ALL WARRANTIES.
00009 //
00010 //  Created on August 29, 1998 (FB).
00011 
00012 #include "gml/base/gml_DynamicArray.h"
00013 
00014 #include "gml/base/gml_Alloc.h"
00015 
00016 
00017 static const int cWordBits     = 32;                // Number of bits per word in the bitmap
00018                                                     //   of used slots.
00019 static const int cWordSize     = cWordBits / 8;     // Size (in bytes) of a word.
00020 static const UInt32 cWordMask  = (UInt32) (~ 0);    // A word with all bits set.
00021 
00022 
00023 
00024 // gml_TDynamicArray::Init --
00025 
00026 template <class T>
00027 gml_TError gml_TDynamicArray<T>::Init  (gml_TBlockSize    nbElem,
00028                                         gml_TBlockSize    nbIncrease)
00029 {
00030   gml_TError   err         = gml_cNoError;
00031 
00032   // init data members
00033   fNbIncrease   = nbIncrease;
00034 
00035   fMem          = (T*)NULL;
00036   fNbElem       = 0;
00037   fInUse        = 0;
00038 
00039   fBitmap       = (UInt32*)NULL;
00040   fBMSize       = 0;
00041 
00042   err = this->Allocate (nbElem);
00043 
00044   if (err != gml_cNoError)
00045     this->Dispose ();
00046 
00047   return err;
00048 }
00049 
00050 
00051 
00052 // gml_TDynamicArray::Dispose --
00053 
00054 template <class T>
00055 void gml_TDynamicArray<T>::Dispose ()
00056 {
00057   gml_TestAndFree (fMem);
00058   fNbElem = 0;
00059   fInUse  = 0;
00060 
00061   gml_TestAndFree (fBitmap);
00062   fBMSize = 0;
00063 }
00064 
00065 
00066 
00067 // gml_TDynamicArray::GetElem --
00068 
00069 template <class T>
00070 T* gml_TDynamicArray<T>::GetElem (gml_TBlockSize* index)
00071 {
00072   gml_TError        err = gml_cNoError;
00073 
00074   int               i         = 0;
00075   gml_TBlockSize    j         = 0;
00076   gml_TBlockSize    theIndex;
00077   UInt32*           bmWord;
00078   UInt32            theWord;
00079 
00080   if (fInUse == fNbElem)
00081     err = this->Allocate (fNbElem + fNbIncrease);
00082   
00083   if (err != gml_cNoError)
00084     return (T*)NULL;
00085 
00086   bmWord = fBitmap;
00087   while ((j < fBMSize) && (*bmWord == cWordMask)) {
00088     bmWord++;
00089     j += 1;
00090   }
00091 
00092   theWord = *bmWord;
00093   while (theWord & ((UInt32)1 << i))
00094     i++;
00095 
00096   // Mark this slot as "used" in the bitmap
00097 
00098   *bmWord = theWord | ((UInt32)1 << i);
00099   fInUse ++;
00100 
00101   theIndex = (j * cWordBits + i);
00102   if (index != (gml_TBlockSize*)NULL)
00103     *index = theIndex;
00104 
00105   return fMem + theIndex;
00106 }
00107 
00108 
00109 
00110 // gml_TDynamicArray::ReleaseElem --
00111 
00112 template <class T>
00113 void gml_TDynamicArray<T>::ReleaseElem (T* elem)
00114 {
00115   gml_TBlockSize  elemInd   = elem - fMem;
00116   UInt32          j         = elemInd / cWordBits;
00117   UInt32          i         = elemInd % cWordBits;
00118 
00119   fBitmap[j]  &= ~((UInt32)1 << i);
00120   fInUse --;
00121 }
00122 
00123 
00124 
00125 
00126 // gml_TDynamicArray::Allocate --
00127 
00128 template <class T>
00129 gml_TError gml_TDynamicArray<T>::Allocate (gml_TBlockSize nbElem)
00130 {
00131   gml_TError        err;
00132   T*                mem         = (T*)NULL;
00133   UInt32*           bitmap      = (UInt32*)NULL;
00134   gml_TBlockSize    bmSize;
00135   int               div, mod;
00136 
00137   if (nbElem == 0)
00138     return gml_cNoError;
00139 
00140   // Allocate the new memory blocks for the array and the bitmap of used slots.
00141   
00142   if ((err = gml_MallocAndZero (mem, nbElem)) != gml_cNoError)
00143     goto error;
00144 
00145     bmSize  = (nbElem - 1) / cWordBits + 1;
00146   if ((err = gml_MallocAndZero (bitmap, bmSize)) != gml_cNoError)
00147     goto error;
00148 
00149     bzero ((void*)bitmap, bmSize * cWordSize);
00150 
00151   // If number of elements in the new array is not a multiple of
00152   //  the number of bits in a bitmap word, then set the last (unused)
00153   //  bits to "slot in use" (bit = 1).
00154 
00155     mod = nbElem % cWordBits;
00156     if (mod != 0)
00157       *(bitmap + (nbElem / cWordBits)) = (cWordMask << mod);
00158 
00159     // Copy the old values if necessary (i.e. if this is not the first allocation),
00160     //  and free the previous buffers.
00161     // We use memcpy because we know that the buffers don't overlap.
00162 
00163     if (fMem != (T*)NULL) {
00164       memcpy ((void*)mem, (void*)fMem, fNbElem * sizeof(T));
00165 
00166       div = fNbElem / cWordBits;
00167       mod = fNbElem % cWordBits;
00168       memcpy ((void*)bitmap, (void*)fBitmap, div * cWordSize);
00169 
00170       // If number of elements in the previous array is not a multiple of
00171       //  the number of bits in a bitmap word, then clear the unused
00172       //  bits while copying the last word.
00173 
00174       if (mod != 0)
00175         *(bitmap + div) |= ((*(fBitmap + div)) & (cWordMask >> (cWordBits - mod)));
00176       
00177       gml_Free (fMem);
00178       gml_Free (fBitmap);
00179     }
00180 
00181     fMem      = mem;
00182     fNbElem   = nbElem;
00183 
00184     fBitmap   = bitmap;
00185     fBMSize   = bmSize;
00186 
00187   return err;
00188 
00189 error:
00190   // error handling
00191     gml_TestAndFree (mem);
00192     gml_TestAndFree (bitmap);
00193 
00194   return err;
00195 }
00196