Seite 7: Listing

Inhaltsverzeichnis

Listing

// SimpleHeap.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include "stdio.h"
#include "windows.h"
 
typedef struct __HeapHdr__ {
     struct __HeapHdr__          *next;
     struct __HeapHdr__          *prev;
     unsigned int               size;
     unsigned char               used;
     // Nutzdatenbereich ab hier
} HeapHdr_t;
 
HeapHdr_t *Init_SimpleHeap( void *memory, unsigned int initial_size) {
     HeapHdr_t           *root;
 
     root = (HeapHdr_t *) memory;
     root->next = NULL;
     root->prev = NULL;
     root->size = initial_size - sizeof( HeapHdr_t );
     root->used = 0;
 
     return root;
}
 
void *SimpleHeap_alloc( size_t s, HeapHdr_t *root ) {
     HeapHdr_t     *p;
     HeapHdr_t     *np;
 
     p = root;
     // durchlaufe die gesamte Liste von Blöcken bis zum Ende
     while ( NULL != p ) {
 
          // ist dieser Block unbenutzt und groß genug
          if (
               ( 0 == p->used )
               && ( s < p->size + sizeof( HeapHdr_t ) )
               ) {
 
                    // ein neuer Block für den übrigen freien Speicher wird
                    // generiert und hinter dem zu verwendenden in die Liste
                    // eingefügt
                    np = (HeapHdr_t *) ((unsigned char *)p + sizeof( HeapHdr_t ) + s);
                    // der Nachfolger bleibt identisch
                    np->next = p->next;
                    // der Nachfolger des Blockes p muss nun auf den neuen
                    // Block np verweisen, falls es einen Nachfolger gibt
                    if ( NULL != p->next )
                         p->next->prev = np;
                    // Der Vorgänger von np ist p
                    np->prev = p;
                    // der neue Block hat die Groesse des noch freien
                    // Speichers und ist nicht benutzt
                    np->size = p->size - s - sizeof( HeapHdr_t );
                    np->used = 0;
 
                    // nachdem der neue Block für den übrigen Speicher
                    // angelegt wurde, kann der alte Block verwendet werden
                    p->size = s;
                    p->used = 1;
                    p->next = np;
 
                    // der Pointer zum Nutzdatenbereich wird dem User
                    // zurückgegeben
                    return (void*) ((unsigned char*)p + sizeof( HeapHdr_t ) );
               }
 
               // nächsten Block betrachten
               p = p->next;
 
     } // while
 
     // wurde beim Durchlauf kein nutzbarer Block gefunden, gibt
     // die Funktion NULL zurück
     return NULL;
}
 
void SimpleHeap_free( void *userp ) {
     HeapHdr_t     *hdr;
 
     // der vom Benutzer übergebene Zeiger ist eigentlich ein Zeiger
     // auf hdr->usermem. Man erhält den richtigen Zeiger für hdr, indem
     // den Benutzerzeiger um die Größe des Headers nach vorn
     // verschoben wird
     hdr = (HeapHdr_t *) ( (unsigned char *)userp - sizeof( HeapHdr_t ) );
 
     // mit dem folgenden Schritt ist der Speicherbereich schon wieder
     // freigegeben und könnte verwendet werden
     hdr->used = 0;
 
     // Testen, ob der darauffolgende Block auch frei ist
     if ( 0 == hdr->next->used ) {
          // neue Größe dieses Blockes aus der Summe beider
          hdr->size += hdr->next->size + sizeof( HeapHdr_t );
 
          // Nun muss der nachfolgende Block aus der doppelt verketteten
          // Liste entfernt werden. Dazu wird zuerst der prev Zeiger des
          // Nachfolgers des nächsten Blockes auf diesen Block verbogen:
          if ( NULL != hdr->next->next )
               hdr->next->next->prev = hdr->next->prev;
          // Nun wird der aktuelle Nachfolger auf den Nachfolger des
          // nächsten Blockes umgelegt:
          hdr->next = hdr->next->next;
          // Damit ist der Block hdr->next aus der doppelt verketteten
          // Liste entfernt worden
     }
}
 
 
#define HEAP_SIZE          ( 4096 * 1024 )
int _tmain(int argc, _TCHAR* argv[])
{
     void          *myHeap;
     HeapHdr_t     *myRoot;
 
     HANDLE               hFile;
     unsigned int     width, height;
     unsigned int     bytesIn;
     unsigned char     *image;
 
     if ( 2 != argc )
     {
          fprintf( stderr, "Usage: %s <filename>\n", argv[0] );
          return ( -2 );
     }
 
     if ( NULL == ( myHeap = LocalAlloc( LPTR, HEAP_SIZE ) ) )
     {
          fprintf( stderr, "LocalAlloc failed\n");
          return ( -1 );
     }
 
     printf( "Initialisiere den SimpleHeap ...\n" );
     myRoot = Init_SimpleHeap( myHeap, HEAP_SIZE );
 
     //
     // Datei oeffnen
     //
     if ( INVALID_HANDLE_VALUE ==
          ( hFile = CreateFile( argv[1], FILE_READ_DATA, 0, 0, OPEN_EXISTING, 0, 0 ) ) )
     {
          fprintf( stderr, "Failed to open %s\n", argv[1] );
          return ( -3 );
     }
 
     //
     // Die Breite des Bildes lesen
     //
 
     if ( ! ReadFile( hFile, &width, sizeof(width), (LPDWORD) &bytesIn, 0 ) )
     {
          fprintf( stderr, "Failed to read width from file\n" );
          return ( -4 );
     }
 
     //
     // Die Hoehe des Bildes lesen
     //
 
     if ( ! ReadFile( hFile, &height, sizeof( height ), (LPDWORD) &bytesIn, 0 ) ) {
          fprintf( stderr, "Failed to read heigth from file\n" );
          return ( -5 );
     }
 
     //
     // Speicher auf dem SimpleHeap reservieren
     //
 
     printf( "Reserviere Speicher fuer %u x %u Pixel: %u Bytes\n",
          width, height, width * height );
 
     image = ( unsigned char * ) SimpleHeap_alloc( width * height, myRoot );
 
     printf( "Zeiger *image = %p\n", image );
 
     //
     // Bild lesen
     //
     for ( unsigned int i = 0; i < height; i++ ) {
 
          unsigned char     *line;
 
          //
          // Speicher fuer eine Bildzeile reservieren
          //
          printf( "Reserviere %u Bytes fuer eine Bildzeile\n", width );
         
          line = ( unsigned char *) SimpleHeap_alloc( width, myRoot );
 
          printf( "Zeiger *line = %p\n", line );
 
          if ( ! ReadFile( hFile, line, width, (LPDWORD) &bytesIn, 0 ) )
          {
               fprintf( stderr, "Failed to read image line %u\n", i );
               return ( -6 );
          }
 
          //
          // Daten in das Bild kopieren
          //
 
          memcpy( image + ( i * width ), line, bytesIn );
 
          //
          // Speicher wieder freigeben
          //
 
          SimpleHeap_free( line );
 
          if ( bytesIn != width )
          {
               fprintf( stderr, "Short or broken image\n" );
               return ( -7 );
          }
     }
 
     SimpleHeap_free( image );
 
     //
     // ende verwende
     //
 
     LocalFree( (HLOCAL) myHeap );
 
     return 0;
}


(ju)