ODYNARR.CPP Source File Main Page Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members
ODYNARR.CPP

Go to the documentation of this file.
00001 //Filename    :: ODYNARR.CPP
00002 //Description :: Dynamic Array object
00003 
00004 #include <stdlib.h>
00005 #include <string.h>
00006 
00007 #include <ODYNARR.H>
00008 #include <OFILE.H>
00009 #include <OMISC.H>
00010 
00011 //--------- BEGIN OF FUNCTION DynArray Constructor -------//
00012 //
00013 // <int> eleSize  = size of each element
00014 // [int] blockNum = number of entity of each block of element
00015 //                       increased ( default : 30 )
00016 
00017 DynArray::DynArray(int eleSize,int blockNum) {
00018     ele_size  = eleSize;
00019     block_num = blockNum;
00020 
00021     body_buf = mem_add( ele_size*block_num );
00022 
00023     cur_pos=0;
00024     last_ele=0;
00025     ele_num= block_num;
00026 
00027     sort_offset = -1;
00028 }
00029 
00030 //----------- END OF FUNCTION DynArray Constructor -----//
00031 
00032 //--------- BEGIN OF FUNCTION DynArray Destructor ------//
00033 
00034 DynArray::~DynArray() {
00035     deinit();
00036 }
00037 
00038 //---------- END OF FUNCTION DynArray Destructor --------//
00039 
00040 //--------- BEGIN OF FUNCTION DynArray::deinit ------//
00041 
00042 void DynArray::deinit() {
00043     if( body_buf ) {
00044         mem_del( body_buf );
00045         body_buf = NULL;
00046     }
00047 }
00048 
00049 //---------- END OF FUNCTION DynArray::deinit --------//
00050 
00051 //--------- BEGIN OF FUNCTION DynArray::resize ---------//
00052 //
00053 // change the size of the storage block - this will always be an increase
00054 //
00055 void DynArray::resize( int newNum ) {
00056     //-------------------------------------------------------//
00057     //
00058     // The Mem::resize() and realloc() may not function properly in
00059     // some case when the memory block has a considerable size.
00060     //
00061     // Calling function resize_keep_data will do additional effort
00062     // to preserve the original data.
00063     //
00064     //-------------------------------------------------------//
00065 
00066     // give both the original data size and the new data size
00067     body_buf = mem_resize( body_buf, newNum*ele_size );
00068 
00069     ele_num = newNum;
00070 }
00071 
00072 //--------- END OF FUNCTION DynArray::resize -----------//
00073 
00074 //--------- BEGIN OF FUNCTION DynArray::zap ---------//
00075 //
00076 // Zap the whole dynamic array, clear all elements
00077 //
00078 // [int] resizeFlag - whether resize the array to its initial size
00079 //                                                       or keep its current size.
00080 //                                                       (default:1)
00081 //
00082 void DynArray::zap(int resizeFlag) {
00083     if( resizeFlag ) {
00084         if( ele_num != block_num ) {                  // if the current record no. is already block_num, no resizing needed
00085             ele_num  = block_num;
00086             body_buf = mem_resize(body_buf, ele_size*ele_num );
00087         }
00088     }
00089 
00090     cur_pos=0;
00091     last_ele=0;
00092 }
00093 
00094 //--------- END OF FUNCTION DynArray::zap -----------//
00095 
00096 //---------- BEGIN OF FUNCTION DynArray::linkin -----------//
00097 //
00098 // Link a record at the END of the array
00099 //
00100 // WARNING : After calling linkin() all pointers to the linklist body
00101 //           should be updated, because mem_resize() will move the body memory
00102 //
00103 void DynArray::linkin(void* ent) {
00104     last_ele++;
00105     cur_pos=last_ele;
00106 
00107     if ( last_ele > ele_num )                       // not enough empty element left to hold the new entity
00108         resize( ele_num + block_num );
00109 
00110     if ( ent )
00111         memcpy(body_buf+(cur_pos-1)*ele_size, ent, ele_size );
00112     else
00113         *(body_buf+(cur_pos-1)*ele_size) = NULL;
00114 }
00115 
00116 //---------- END OF FUNCTION DynArray::linkin ------------//
00117 
00118 //---------- BEGIN OF FUNCTION DynArray::linkin_unique -----------//
00119 //
00120 // Linkin - unique mode. If duplicated, don't link into the array.
00121 //
00122 void DynArray::linkin_unique(void* ent) {
00123     int i;
00124 
00125     for( i=0 ; i<last_ele ; i++ ) {
00126         if( memcmp( body_buf+i*ele_size, ent, ele_size )==0 )
00127             return;
00128     }
00129 
00130     linkin(ent);
00131 }
00132 
00133 //---------- END OF FUNCTION DynArray::linkin_unique ------------//
00134 
00135 //---------- BEGIN OF FUNCTION DynArray::insert -----------//
00136 //
00137 // Link into the position BEFORE the current one
00138 //
00139 // Warning : DynArrayB (version B) can't use this function
00140 //
00141 void DynArray::insert(void* ent) {
00142     if( size()==0 ) {
00143         linkin(ent);
00144         return;
00145     }
00146 
00147     last_ele++;
00148 
00149     if ( last_ele > ele_num )                       // not enough empty element left to hold the new entity
00150         resize( ele_num + block_num );
00151 
00152     memmove( body_buf+cur_pos*ele_size,body_buf+(cur_pos-1)*ele_size, (last_ele-cur_pos)*ele_size );
00153 
00154     if ( ent )
00155         memcpy(body_buf+(cur_pos-1)*ele_size, ent, ele_size );
00156     else
00157         *(body_buf+(cur_pos-1)*ele_size) = NULL;
00158 }
00159 
00160 //---------- END OF FUNCTION DynArray::insert ------------//
00161 
00162 //---------- BEGIN OF FUNCTION DynArray::insert_at -----------//
00163 //
00164 // Link into the position BEFORE the current one
00165 //
00166 // Warning : DynArrayB (version B) can't use this function
00167 //
00168 // <int>   insertPos - the recno to insert the new entity.
00169 // <void*> ent             - pointer to the record entity. If NULL, blank record.
00170 //
00171 void DynArray::insert_at(int insertPos, void* ent) {
00172     if( size()==0 || insertPos>last_ele ) {
00173         linkin(ent);
00174         return;
00175     }
00176 
00177     err_when( insertPos<1 || insertPos > last_ele );
00178 
00179     last_ele++;
00180 
00181     if ( last_ele > ele_num )                       // not enough empty element left to hold the new entity
00182         resize( ele_num + block_num );
00183 
00184     memmove( body_buf+insertPos*ele_size, body_buf+(insertPos-1)*ele_size, (last_ele-insertPos)*ele_size );
00185 
00186     if ( ent )
00187         memcpy(body_buf+(insertPos-1)*ele_size, ent, ele_size );
00188     else
00189         *(body_buf+(insertPos-1)*ele_size) = NULL;
00190 }
00191 
00192 //---------- END OF FUNCTION DynArray::insert_at ------------//
00193 
00194 //----------- BEGIN OF FUNCTION DynArray::linkout ---------//
00195 //
00196 // Linkout the current object and then point to next object
00197 //
00198 // [int] delPos = the position (recno) of the item to be deleted
00199 //                ( default : recno() current record no. )
00200 //
00201 void DynArray::linkout(int delPos) {
00202     if( delPos < 0 )
00203         delPos = cur_pos;
00204 
00205     if( delPos == 0 || delPos > last_ele )
00206         return;
00207 
00208     if( delPos != last_ele )
00209         memmove( body_buf+(delPos-1)*ele_size, body_buf+delPos*ele_size, (last_ele-delPos)*ele_size );
00210 
00211     last_ele--;
00212 
00213     if( cur_pos > last_ele )
00214         cur_pos = last_ele;
00215 
00216     if ( last_ele < ele_num - block_num*2 )         // shrink the size if two empty block of element are left
00217         resize( ele_num - block_num );
00218 }
00219 
00220 //------------ END OF FUNCTION DynArray::linkout ----------//
00221 
00222 //---------- BEGIN OF FUNCTION DynArray::update ---------//
00223 //
00224 // <void*> bodyPtr = the pointer to the content body
00225 // [int]   recNo   = no. of the record to be updated
00226 //                   ( default : current record no. )
00227 //
00228 void DynArray::update(void* bodyPtr, int recNo) {
00229     if( recNo < 0 )
00230         recNo = cur_pos;
00231 
00232     if( recNo <= 0 )
00233         return;
00234 
00235     if( bodyPtr )
00236         memcpy(body_buf+(recNo-1)*ele_size, bodyPtr, ele_size );
00237     else
00238         *(body_buf+(recNo-1)*ele_size) = NULL;
00239 }
00240 
00241 //----------- END OF FUNCTION DynArray::update ---------//
00242 
00243 //---------- BEGIN OF FUNCTION DynArray::add_blank -----------//
00244 //
00245 // Add a specified number of blank records at the END of the array
00246 //
00247 // <int> blankNum = no. of blank records
00248 //
00249 void DynArray::add_blank(int blankNum) {
00250     cur_pos=last_ele+1;
00251     last_ele+=blankNum;
00252 
00253     if ( last_ele > ele_num )                       // not enough empty element left to hold the new entity
00254         resize( last_ele+block_num );
00255 
00256     memset( body_buf+(cur_pos-1)*ele_size, 0, blankNum*ele_size );
00257 }
00258 
00259 //---------- END OF FUNCTION DynArray::add_blank ------------//
00260 
00261 //------ BEGIN OF FUNCTION DynArray::scan_whole ----------//
00262 //
00263 // Description : scan a sorted or unsorted link list for matching
00264 //               the Whole Structure
00265 //
00266 // Syntax      : scan(<void*>)
00267 //
00268 // <void*> = pointer to the data structure
00269 //
00270 // Return : 0 if not found
00271 //          if found, return the position found
00272 //
00273 int DynArray::scan_whole(void* structPtr) {
00274     for ( cur_pos=1 ; cur_pos<=last_ele ; cur_pos++ ) {
00275         if( memcmp( structPtr, get(), ele_size ) == 0 )
00276             return cur_pos;
00277     }
00278 
00279     return 0;
00280 }
00281 
00282 //-------- END OF FUNCTION DynArray::scan_whole ----------//
00283 
00284 //------ BEGIN OF FUNCTION DynArray::scan ----------//
00285 //
00286 // Description : scan a sorted or unsorted link list for matching
00287 //               the specified element in the structure
00288 //
00289 // Syntax      : scan(<void*>,<int>,<char>,[int])
00290 //
00291 // <void*> = the data to be scanned for
00292 // <int>   = the offset of the structure containing the variable to be compared
00293 // <char>  = the type of the variable in the structure
00294 //           'C' = char[]
00295 //           'P' = char*
00296 //           'd' = double
00297 //           'i' = integer
00298 //           'c' = char
00299 // [int]  = restore the original position      ( default : FALSE )
00300 //
00301 // Return : 0 if not found
00302 //          if found, return the position found
00303 //
00304 int DynArray::scan(void* varChar,int varOff,char varType,int restPos) {
00305     int oldPos,ret;
00306 
00307     oldPos = cur_pos;
00308 
00309     for ( cur_pos=1 ; cur_pos<=last_ele ; cur_pos++ ) {
00310         if ( compare(varChar,varOff,varType) ) {
00311             ret = cur_pos;
00312             if (restPos)
00313                 cur_pos = oldPos;
00314             return ret;
00315         }
00316     }
00317 
00318     return 0;
00319 }
00320 
00321 //-------- END OF FUNCTION DynArray::scan ----------//
00322 
00323 //------- BEGIN OF FUNCTION DynArray::compare --------//
00324 //
00325 // <char*> = the character string to be scanned for
00326 // <int>   = the offset of the structure containing the variable to be compared
00327 // <char>  = the type of the variable in the structure
00328 //           'C' = char[]
00329 //           'P' = char*
00330 //           'd' = double
00331 //           'i' = integer
00332 //           'c' = char
00333 
00334 int DynArray::compare(void* varChar,int varOff,char varType) {
00335     char *bodyPtr,*bodyStr;
00336 
00337     bodyPtr = (char*) get();
00338 
00339     switch( varType ) {
00340     case 'C' :
00341     case 'P' :
00342         if ( varType == 'C' )
00343             bodyStr = bodyPtr + varOff;
00344         else
00345             bodyStr = *( (char**)(bodyPtr+varOff) );
00346 
00347         if( bodyStr == (char*) varChar )            // the pointer is the same
00348             return 1;
00349         else
00350             // m1strcmp with exact set off
00351             return m.str_cmp(bodyStr, (char*) varChar);
00352 
00353     case 'c' :
00354         return *(bodyPtr + varOff ) == *((char*)varChar);
00355 
00356     case 'i' :
00357         return *((int*)(bodyPtr+varOff)) == *((int*)varChar);
00358 
00359     case 'd' :
00360         return *((double*)(bodyPtr+varOff)) == *((double*)varChar);
00361     }
00362 
00363     return NULL;
00364 }
00365 
00366 //-------- END OF FUNCTION DynArray::compare ----------//
00367 
00368 //---------- BEGIN OF FUNCTION DynArray::clean_up --------------//
00369 //
00370 // Description : clear up the whole dynamic array
00371 //
00372 // Syntax      : clean_up(<int[]>)
00373 //
00374 // <int[]> = the array of offset of the char*
00375 //
00376 
00377 void DynArray::clean_up(int *stringOffset) {
00378     if ( stringOffset ) {
00379         int i;
00380 
00381         for ( i = 0 ; i<last_ele ; i++ )
00382             free_ptr( body_buf+i*ele_size, stringOffset );
00383     }
00384 
00385     last_ele=0;
00386     cur_pos =0;
00387 
00388     resize( block_num );
00389 }
00390 
00391 //---------- END OF FUNCTION DynArray::clean_up ---------//
00392 
00393 //------- BEGIN OF FUNCTION DynArray::free_ptr ----------//
00394 
00395 void DynArray::free_ptr( void* freebody, int *stringOffset ) {
00396     int    i,stringNum;
00397     char** ptrPtr;
00398     char*  charPtr;
00399 
00400     stringNum = stringOffset[0];
00401 
00402     for(i=1 ; i<=stringNum ; i++) {                 // write char* allocated string
00403         ptrPtr  = (char**) ( (char*)freebody + stringOffset[i] );
00404         charPtr = (char*)  *ptrPtr;
00405 
00406         if ( charPtr )
00407             mem_del(charPtr);
00408     }
00409 
00410 }
00411 
00412 //----------- END OF FUNCTION DynArray::free_ptr -------------//
00413 
00414 //---------- Begin of function DynArray::quick_sort -------------//
00420 void DynArray::quick_sort( int(*cmpFun)(const void*, const void*) ) {
00421     qsort( body_buf, last_ele, ele_size, cmpFun );
00422 }
00423 
00424 //------------- End of function DynArray::quick_sort --------------//
00425 
00426 //---------- Begin of function DynArray::bubble_sort -------------//
00432 void DynArray::bubble_sort( int(*cmpFun)(const void*, const void*) ) {
00433     char *tmp;
00434     tmp=mem_add(ele_size);
00435 
00436     for(int i=0;i<last_ele;i++)
00437         for(int j=i+1;j<last_ele;j++) {
00438             void *p,*q;                                   //swapping
00439             p=get(i+1);
00440             q=get(j+1);
00441             if(cmpFun(p,q)>0) {
00442                 memcpy(tmp,p,ele_size);
00443                 memcpy(p,q,ele_size);
00444                 memcpy(q,tmp,ele_size);
00445             }
00446         }
00447     mem_del(tmp);
00448 }
00449 
00450 //------------- End of function DynArray::bubble_sort --------------//
00451 
00452 //---------- Begin of function DynArray::write_file --  -----------//
00462 int DynArray::write_file(File* filePtr) {
00463     if( !filePtr->file_write( this, sizeof(DynArray) ) )
00464         return 0;
00465 
00466     if( last_ele > 0 ) {
00467         if( !filePtr->file_write( body_buf, ele_size*last_ele ) )
00468             return 0;
00469     }
00470 
00471     return 1;
00472 }
00473 
00474 //------------- End of function DynArray::write_file --------------//
00475 
00476 //---------- Begin of function DynArray::read_file -------------//
00485 int DynArray::read_file(File* filePtr) {
00486     char* bodyBuf = body_buf;                       // preserve body_buf which has been allocated
00487 
00488     if( !filePtr->file_read( this, sizeof(DynArray) ) )
00489         return 0;
00490 
00491     body_buf = mem_resize( bodyBuf, ele_num*ele_size );
00492 
00493     if( last_ele > 0 ) {
00494         if( !filePtr->file_read( body_buf, ele_size*last_ele ) )
00495             return 0;
00496     }
00497 
00498     start();                                        // go top
00499 
00500     return 1;
00501 }
00502 
00503 //------------- End of function DynArray::read_file --------------//
00504 
00505 //--------- Begin of function DynArray::init_sort ---------//
00516 void DynArray::init_sort(int sortOffset, char sortType) {
00517     sort_offset = sortOffset;
00518     sort_type   = sortType;
00519 }
00520 
00521 //----------- End of function DynArray::init_sort ---------//
00522 
00523 //------ BEGIN OF FUNCTION DynArray::linkin_sort_scan_from_bottom ----------//
00524 //
00525 // Description : linkin a entry to a sorted link list
00526 //
00527 // Note    : init_sort() must be called first, before using sorting function
00528 // Warning : DynArrayB (version B) can't use this function
00529 //
00530 // Syntax      : linkin_sort_scan_from_bottom(<void*>,<int>,<char>)
00531 //
00532 // <void*> = the structure buffer pointer
00533 //
00534 // Note : use DynArray::seek() to search quickly if the whole DynArray is
00535 //        built up with linkin_sort_scan_from_bottom()
00536 //
00537 // WARNING : After calling linkin() all pointers to the linklist body
00538 //           should be updated, because mem_resize() will move the body memory
00539 //
00540 void DynArray::linkin_sort_scan_from_bottom(void* varPtr) {
00541     err_when( sort_offset < 0 );
00542 
00543     int   cmpRet;
00544     char* varData,*bodyChar;
00545 
00546     for( int recNo=last_ele ; recNo>0 ; recNo-- ) {
00547         //-------- comparsion ---------//
00548 
00549         switch( sort_type ) {
00550         case SORT_INT:                              // <int>
00551             cmpRet   = *((int*)((char*)varPtr+sort_offset)) >
00552                 *((int*)((char*)get()+sort_offset));
00553             break;
00554 
00555         case SORT_SHORT:                            // <short>
00556             cmpRet   = *((short*)((char*)varPtr+sort_offset)) >
00557                 *((short*)((char*)get()+sort_offset));
00558             break;
00559 
00560         case SORT_CHAR:                             // <char>
00561             cmpRet   = *((char*)((char*)varPtr+sort_offset)) >
00562                 *((char*)((char*)get()+sort_offset));
00563             break;
00564 
00565         case SORT_CHAR_PTR:                         // <char*>
00566             varData  = *( (char**)((char*)varPtr + sort_offset) );
00567             bodyChar = *( (char**)((char*)get() + sort_offset) );
00568 
00569             err_when( !varData || !bodyChar );
00570 
00571             cmpRet   = strcmp( varData, bodyChar );
00572             break;
00573 
00574         case SORT_CHAR_STR:                         // <char[]>
00575             varData  = (char*)varPtr + sort_offset ;
00576             bodyChar = (char*)get() + sort_offset ;
00577 
00578             err_when( !varData || !bodyChar );
00579 
00580             cmpRet   = strcmp( varData, bodyChar );
00581             break;
00582         }
00583 
00584         //---- if equal then linkin -----------//
00585 
00586         if( cmpRet >= 0 ) {
00587             insert_at( last_ele+1, varPtr) ;
00588             return;
00589         }
00590     }
00591 
00592     insert_at( 1, varPtr);                          // insert at the top
00593 }
00594 
00595 //--------- END OF FUNCTION DynArray::linkin_sort_scan_from_bottom ---------//
00596 
00597 /* this function has bugs and is commented out.
00598 
00599 //------ BEGIN OF FUNCTION DynArray::linkin_sort ----------//
00600 //
00601 // Description : linkin a entry to a sorted link list
00602 //
00603 // Note    : init_sort() must be called first, before using sorting function
00604 // Warning : DynArrayB (version B) can't use this function
00605 //
00606 // Syntax      : linkin_sort(<void*>,<int>,<char>)
00607 //
00608 // <void*> = the structure buffer pointer
00609 //
00610 // Note : use DynArray::seek() to search quickly if the whole DynArray is
00611 //        built up with linkin_sort()
00612 //
00613 // WARNING : After calling linkin() all pointers to the linklist body
00614 //           should be updated, because mem_resize() will move the body memory
00615 //
00616 void DynArray::linkin_sort(void* varPtr)
00617 {
00618 err_when( sort_offset < 0 );
00619 
00620 register int jumpStep,cmpRet;
00621 
00622 char* lastVar,*lastVar2;
00623 char* varData,*bodyChar;
00624 
00625 jumpStep=last_ele/2+1;
00626 
00627 go(jumpStep);
00628 
00629 lastVar = lastVar2 = NULL;
00630 
00631 //------- for binary comparsion linkin_sort -------------//
00632 
00633 for (;; )
00634 {
00635 //-------- comparsion ---------//
00636 
00637 switch( sort_type )
00638 {
00639 case 'I':
00640 cmpRet   = *((int*)((char*)varPtr+sort_offset)) ==
00641 *((int*)((char*)get()+sort_offset));
00642 break;
00643 
00644 case 'P':       // char*
00645 varData  = *( (char**)((char*)varPtr + sort_offset) );
00646 bodyChar = *( (char**)((char*)get() + sort_offset) );
00647 
00648 err_when( !varData || !bodyChar );
00649 
00650 cmpRet   = strcmp( varData, bodyChar );
00651 break;
00652 
00653 case 'C':
00654 varData  = (char*)varPtr + sort_offset ;
00655 bodyChar = (char*)get() + sort_offset ;
00656 
00657 err_when( !varData || !bodyChar );
00658 
00659 cmpRet   = strcmp( varData, bodyChar );
00660 break;
00661 }
00662 
00663 //---- if equal then linkin -----------//
00664 
00665 if ( cmpRet ==0 )
00666 {
00667 linkin(varPtr) ;
00668 break;
00669 }
00670 
00671 //----- reach the end of the binary tree ----//
00672 
00673 if ( lastVar2 == bodyChar )
00674 {
00675 if ( cmpRet < 0 )
00676 bkwd();
00677 linkin(varPtr);
00678 break;
00679 }
00680 
00681 //----- search through the binary tree -----//
00682 
00683 if ( jumpStep%2 == 1 )
00684 jumpStep=jumpStep/2+1;
00685 else
00686 jumpStep/=2;
00687 
00688 if ( jumpStep < 1 )
00689 jumpStep = 1;
00690 
00691 if ( cmpRet < 0 )
00692 jump( -jumpStep );
00693 else
00694 jump( jumpStep );
00695 
00696 lastVar2 = lastVar;
00697 lastVar  = bodyChar;
00698 }
00699 
00700 }
00701 //--------- END OF FUNCTION DynArray::linkin_sort ---------//
00702 
00703 //---------- Begin of function DynArray::resort -------------//
00710 void DynArray::resort(int resortRecno)
00711 {
00712     linkin_sort(get(resortRecno));       // linkin the record for a second time, for sorting
00713 
00714     go(resortRecno);             // delete the original record
00715     linkout(resortRecno);
00716 }
00717 //------------- End of function DynArray::resort --------------//
00718 
00719 */
Generated on Fri Aug 23 01:37:26 2002 for VirtualU by
1.2.17