C++: Ich brauche einige Anleitung, wie man dynamische Bitmaps erstellen

Question

Ich versuche, ein einfaches DBMS zu erstellen, und obwohl ich viel darüber gelesen habe und das System bereits entworfen habe, habe ich einige Probleme mit der Implementierung.

Ich muss wissen, was die beste Methode in C++ ist, eine Reihe von Bits zu verwenden, deren Länge dynamisch sein wird. Diese Reihe von Bits wird gespeichert, um herauszufinden, welche Seiten in den Dateien frei und nicht frei sind. Für eine einzelne Datei wird die Anzahl der verwendeten Seiten festgelegt, so dass ich wahrscheinlich ein Bitset dafür verwenden kann. Die Anzahl der Datensätze pro Seite UND Datei wird jedoch nicht festgelegt. Also ich denke nicht, Bitset wäre der beste Weg, dies zu tun.

Ich dachte vielleicht, nur eine Folge von Zeichen zu verwenden, da jedes Zeichen 1 Byte = 8 Bits ist, vielleicht wenn ich ein Array von ihnen benutze, wäre ich in der Lage, die Bitmap zu erstellen, die ich will.

Ich musste nie Bits auf solch einem niedrigen Niveau manipulieren, also weiß ich nicht wirklich, ob es eine andere bessere Methode gibt, oder ob diese Methode überhaupt funktionieren würde.

Dank im Voraus

Answer 1

Wenn Sie nur die Grundlagen der Bit-Twiddling wollen, ist das folgende eine Möglichkeit, es mit einer Reihe von Zeichen zu tun.

Angenommen, Sie für die Bits ein Array haben (die Länge muss (totalitems/8) sein):

unsigned char *bits; // this of course needs to be allocated somewhere 

Sie können den Index in das Array berechnen und das spezifische Bit innerhalb dieser Position wie folgt:

// compute array position 
int pos = item/8; // 8 bits per byte 
// compute the bit within the byte. Could use "item & 7" for the same 
// result, however modern compilers will typically already make 
// that optimization. 
int bit = item % 8; 

Und Sie können dann prüfen, ob etwas mit der folgenden gesetzt (übernimmt nullbasierte Indexierung):

if (bits[pos] & (1 << bit)) 
    return 1; // it is set 
else 
    return 0; // it is not set 

Im Folgenden wird ein bestimmtes Bit gesetzt:

bits[pos] |= (1 << bit); 

Und ein bestimmtes Bit löschen können folgende verwendet werden:

bits[pos] &= ~(1 << bit); 

Answer 2

ich eine Wrapper-Klasse implementieren würde und einfach speichern Sie Ihre Bitmap in einer verknüpften Liste von Datenblöcken, wobei jeder Chunk eine feste Größe Array halten würde (würde ich einen stdint Typ wie uint32_t verwenden eine gegebene, um sicherzustellen, Anzahl von Bits), dann fügen Sie einfach Links zu Ihrer Liste hinzu, um sie zu erweitern. Ich werde dem Leser Kontraktionen als Übung überlassen.