Ich habe kürzlich mit der Bereinigung meiner Projekte begonnen und beschlossen, ein persönliches Repository mit nützlichen Codebits zu erstellen. Ich habe diesen Bitmap-Code zwischen ihnen gefunden und ihn stark bearbeitet, und ich würde mich freuen, wenn jemand ihn überprüfen könnte, weil ich nicht so an bitweise Operationen und dergleichen gewöhnt bin. Ist der Code portabel genug oder sollten Änderungen vorgenommen werden?
bitmap.h
#ifndef BITMAP__ #define BITMAP__ #define BIT (8*sizeof(byte)) #define BITMAP_NOTFOUND -1 typedef enum{false=0, true} bool; typedef unsigned char byte; bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); #endif bitmap.c
#include "bitmap.h" static bool get (byte, byte); static void set (byte *, byte); static void reset(byte *, byte); /* CAREFUL WITH pos AND BITMAP SIZE! */ bool bitmapGet(byte *bitmap, int pos) { /* gets the value of the bit at pos */ return get(bitmap[pos/BIT], pos%BIT); } void bitmapSet(byte *bitmap, int pos) { /* sets bit at pos to 1 */ set(&bitmap[pos/BIT], pos%BIT); } void bitmapReset(byte *bitmap, int pos) { /* sets bit at pos to 0 */ reset(&bitmap[pos/BIT], pos%BIT); } int bitmapSearch(byte *bitmap, bool n, int size, int start) { /* Finds the first n value in bitmap after start */ /* size is the Bitmap size in bytes */ int i; /* size is now the Bitmap size in bits */ for(i = start+1, size *= BIT; i < size; i++) if(bitmapGet(bitmap,i) == n) return i; return BITMAP_NOTFOUND; } static bool get(byte a, byte pos) { /* pos is something from 0 to 7*/ return (a >> pos) & 1; } static void set(byte *a, byte pos) { /* pos is something from 0 to 7*/ /* sets bit to 1 */ *a |= 1 << pos; } static void reset(byte *a, byte pos) { /* pos is something from 0 to 7*/ /* sets bit to 0 */ *a &= ~(1 << pos); } Kommentare
- Für alle, die diesen Beitrag noch verfolgen, habe ich den Code an github hier übergeben. Ich habe auch alle Ihre Kommentare als Probleme hinzugefügt. Vielen Dank für Ihre Kommentare und ich werde mit der Implementierung beginnen.
Antwort
Wenn Sie erwarten, dass Ihr Code jemals sein wird Wenn Sie C ++ verwenden (was viel C-Code ist), sollten Sie keine Bezeichner mit einem doppelten Unterstrich verwenden.
#ifndef BITMAP__ // ^^ May cause problems in C++ Da dies für die Implementierung reserviert ist in C ++. Auch der Begriff BITMAP ist sehr allgemein gehalten und es ist sehr wahrscheinlich, dass Sie mit anderen Bibliotheken in Konflikt geraten. Versuchen Sie, ihn für Ihr Projekt eindeutiger zu machen.
Sie gehen davon aus, dass ein Zeichen 8 Bit groß ist.
#define BIT (8*sizeof(byte)) Der Standard sagt dies nicht (es sind mindestens 8 Bits), aber es wird tatsächlich über das Makro CHAR_BITS definiert, daher sollten Sie Folgendes verwenden:
#define BIT (CHAR_BITS*sizeof(byte)) In Ihrer Header-Datei sehen die meisten Benutzer Ihren Code zuerst und versuchen zu verstehen, wie er verwendet wird. Daher ist es wahrscheinlich eine gute Idee, die Parameternamen in die Header-Datei einzufügen, da dies zur Dokumentation ihrer Verwendung beiträgt.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Zusätzlich die Aktion von bitmapSearch ist nicht offensichtlich, daher wäre ein Kommentar zur Verwendung im Header wahrscheinlich eine gute Idee. Tatsächlich wäre ein kleiner Klappentext darüber, wie der erste Parameter ein Array sein kann, wahrscheinlich eine gute Idee (da dies ohne Lesen des Codes nicht offensichtlich ist).
Seien Sie vorsichtig mit Kommentaren:
/* pos is something from 0 to 7*/ Dies gilt nur, wenn Sie Annahmen treffen (A: diese Größe von (Byte) == 1 B: Sie multiplizieren dies mit 8). Der Kommentar sollte lauten:
/* pos is a value between [0, BIT) */ Beachten Sie die Verwendung von „[“ links und „)“ rechts. Es ist eine mathematische Notation, die angibt, dass 0 inklusive ist und BIT nicht im Bereich enthalten ist (dies ist in beiden C / C ++ – Dokumentationen üblich).
Antwort
-
Ihre Typen sind nicht erforderlich – verwenden Sie einfach vorzeichenloses Zeichen und int wie in der Standardbibliothek.
-
Zum selben Thema ist Ihr Enum-Bool nicht erforderlich, da in C ungleich Null den wahren Status angibt. Sie bestätigen dies selbst, da get () davon ausgeht, dass der Wert 1 wahr ist. Jeder nimmt dies an und so ist der Typ redundant. Darüber hinaus ist es auch falsch, denn wenn ich Ihre Aufzählung in
typedef enum{true=0, false} bool;ändere, schlägt Ihre Funktion fehl, obwohl dies logischerweise sinnvoll ist.
Wenn Sie einen solchen Bool verwenden möchten, sollten Sie einen seiner Werte explizit zurückgeben:
return ((a >> pos) & 1) ? true : false;, aber das hat wirklich keinen Sinn. Geben Sie einfach ein int zurück, wie es die Standardbibliothek tun würde.
-
bitmapGet (), das einen Bool zurückgibt, scheint mir falsch benannt zu sein. Die Bitmap-Bits haben die Werte 1 und 0, nicht wahr und falsch (obwohl diese derzeit gleich sind). Die Bezeichnung bitmapIsSet () wäre logischer.
-
sizeof (char) ist per Definition 1, sodass BIT durch CHAR_BIT
-
Die Reihenfolge der Parameter für bitmapSearch wäre logischer, wenn die Größe der Sache folgt, auf die sie sich bezieht (Bitmap).
-
Der Startparameter für bitmapSearch ist falsch. Um eine Suche ab Bit 0 anzugeben (sicherlich die häufigste), muss der Aufrufer -1 übergeben !!
-
Warum den Parameter „pos“ als „Byte“ übergeben? Sie haben „Byte“ definiert, um die Bitmap-Bytes darzustellen, und „pos“ ist sicherlich keines davon. Sie erhalten Compiler-Warnungen, wenn diese aktiviert sind (sollten), wenn Argumente mit unterschiedlichen Breiten aufgrund von Prototypen übergeben werden. Wenn Sie „pos“ auf ein Byte beschränken, wird möglicherweise eine zusätzliche Maschinenanweisung hinzugefügt (siehe Assembler), während nichts erreicht wird. Wenn Sie einen Typ pos_t mit dem Bereich 0..7 definieren könnten, den Sie zu wollen scheinen, könnten Sie argumentieren, dass er in irgendeiner Weise korrekt war, aber da Sie dies in C nicht tun können und der Bytewert eindeutig den Bereich 0 hat. 255 ist es nicht besser als ein int.
Das Öffnen von Klammern für Funktionen befindet sich normalerweise in Spalte 0
Antwort
Nicht getan Fragen Sie nach der Leistung, aber Sie können bitmapSearch für spärliche Bitmaps beschleunigen, indem Sie zuerst jeweils ein Byte betrachten. Wenn Sie nach einer 1 suchen, können Sie Bytes überspringen, die 0x00 sind, und wenn Wenn Sie nach einer 0 suchen, können Sie Bytes mit 0xFF überspringen. Danach können Sie die Bits im nächsten Byte scannen oder eine Nachschlagetabelle verwenden.
In Bezug auf die API können Sie
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); hinzufügen, damit sich der Client nicht um die Anzahl der Bytes kümmern muss zuweisen.
Und / oder ein Makro zur Unterstützung der Zuweisung bereitstellen. Ein Makro anstelle einer Funktion, wenn es in Array-Zuordnungen angezeigt werden soll.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) Ich hätte auch bitmapSearch seine Größe als Bitanzahl anstelle einer Byteanzahl. Wenn sich der Client dann beispielsweise nur um 26 Bit für Buchstaben kümmert, muss er sich keine Sorgen machen, dass eine Suche 27 zurückgibt, da die Bitmap wirklich 32 Bit enthält.