From Developer Community

When you remove many elements from a dynamic array, you may need to (a) move all existing elements to the beginning of the array (in other words, pack or compact the array) and (b) release extra memory at the end of the array. This sample demonstrates how to do both (a) and (b). It consists of 3 source files, COMPACT.C, NWDYNARC.H and NWDYNARC.C.

COMPACT.C

#include <nwdynarr.h>
#include <stdio.h>
#include <stdlib.h>

#include "nwdynarc.h"

GEN_DYNARRAY_BLOCK( int, DynArrTest, DEFINE( realloc, 3));

static void disp_dyn_arr( struct DynArrTestStruct* p_DynArrTest) {
   size_t i;
   printf( "DABnumSlots = %d, DABnumEntries = %d, DABarrayP =",
      p_DynArrTest -> DABnumSlots,
      p_DynArrTest -> DABnumEntries);
   for ( i = 0; i < p_DynArrTest -> DABnumEntries; ++i) {
      printf( " %d", p_DynArrTest -> DABarrayP[ i]);
   }
   puts( "");
}
int main() {
   int i;
   /* add 5 elements to the array */
   puts( "Adding ...");
   for ( i = 0; i < 5; ++i) {
      int index = AllocateDynArrayEntry( &DynArrTest);
      if ( index != -1) DynArrTest.DABarrayP[ index] = i + 1;
   }
   disp_dyn_arr( &DynArrTest);
   /* remove 2 elements from the array */
   puts( "Deleting ...");
   for ( i = 0; i < 5; ++i) {
      if ( i % 2 != 0) {
         DeallocateDynArrayEntry( &DynArrTest, i);
      }
   }
   disp_dyn_arr( &DynArrTest);
   /* compact the array */
   puts( "Compacting ...");
   printf( "%d elements compactedn", CompactDynArray(( T_DYNARRAY_BLOCK*) &DynArrTest));
   disp_dyn_arr( &DynArrTest);
   /* free extra memory from the end of the array */
   puts( "Shrinking ...");
   DynArrTest.DABarrayP = DynArrTest.DABrealloc( DynArrTest.DABarrayP,
      ( DynArrTest.DABnumSlots = DynArrTest.DABnumEntries) *
      ( unsigned int) DynArrTest.DABelementSize);
   disp_dyn_arr( &DynArrTest);
   free( DynArrTest.DABarrayP);
   return EXIT_SUCCESS;
}

NWDYNARC.C

#include <nwdynarr.h>
#include <string.h>

#include "nwdynarc.h"

int CompactDynArray( T_DYNARRAY_BLOCK* dabP) {
   int   elements_compacted = 0;
   int   element_size;
   char* cur_entry_raw_p;
   if ( dabP == NULL || ( element_size = dabP -> DABelementSize) == 0) {
      return -1;
   }
   if (( cur_entry_raw_p = dabP -> DABarrayP) != NULL) {
      int number_of_entries = dabP -> DABnumEntries;
      int cur_entry_index   = 0;
      while ( cur_entry_index < number_of_entries) {
         if ( *( int*)( cur_entry_raw_p) == 0) { /* 4 zero bytes at the beginning */
            char* next_entry_raw_p = cur_entry_raw_p;
            do { /* this loop tries to find next not empty entry */
               ++elements_compacted;
               --number_of_entries;
               next_entry_raw_p += element_size;
            }
            while ( cur_entry_index < number_of_entries &&
               *( int*)( next_entry_raw_p) == 0);
            if ( cur_entry_index < number_of_entries) {
               memmove( cur_entry_raw_p, next_entry_raw_p,
                  ( unsigned int)( number_of_entries - cur_entry_index) * element_size);
            }
            dabP -> DABnumEntries = number_of_entries;
         }
         else {
            ++cur_entry_index;
            cur_entry_raw_p += element_size;
         }
      }
   }
   return elements_compacted;
}

NWDYNARC.H

#include <nwdynarr.h>

int CompactDynArray( T_DYNARRAY_BLOCK* dabP);

--Dmitry Mityugov

• Article
• Discussion
• Edit
• History

Personal tools