Jag började nyligen städa upp mina projekt och bestämde mig för att skapa ett personligt arkiv med användbara kodbitar. Jag hittade den här bitmappskoden mellan dem och redigerade den kraftigt och jag skulle uppskatta om någon kunde granska den, för jag är inte så van vid bitvis operationer och sådant. Är koden bärbar nog, eller bör det ändras?
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); } Kommentarer
- Till alla som fortfarande följer det här inlägget, åtog jag koden till github här . Jag lade också till alla dina kommentarer som problem. Tack för dina kommentarer så börjar jag implementera dem.
Svar
Om du förväntar dig att din kod någonsin kommer att bli används från C ++ (som mycket C-kod är) ska du inte använda några identifierare med dubbel understrykning.
#ifndef BITMAP__ // ^^ May cause problems in C++ Eftersom detta är reserverat för implementeringen i C ++. Termen BITMAP är också mycket generisk och det är mycket troligt att du kolliderar med andra bibliotek, försök att göra det mer unikt för ditt projekt.
Du antar att en char är 8 bitar.
#define BIT (8*sizeof(byte)) Standarden säger inte detta (det är minst 8 bitar) men det definieras faktiskt via makrot CHAR_BITS så du bör använda:
#define BIT (CHAR_BITS*sizeof(byte)) Din rubrikfil är hur de flesta först ser din kod och försöker förstå hur du använder den. Att sätta parameternamnen i rubrikfilen är förmodligen en bra idé eftersom det hjälper till att dokumentera deras användning.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Ytterligare åtgärden för bitmapSearch är inte uppenbart, så en kommentar om dess användning i rubriken skulle förmodligen vara en bra idé. Egentligen skulle en liten blurb om hur den första parametern kan vara en array troligen vara en bra idé (eftersom det inte är uppenbart utan att läsa koden).
Var försiktig med kommentarer:
/* pos is something from 0 to 7*/ Detta gäller bara om du gör antaganden (A: den storleken på (byte) == 1 B: du multiplicerar detta med 8). Kommentaren borde ha varit:
/* pos is a value between [0, BIT) */ Notera användningen av ”[” till vänster och ”) till höger. Det är en matematisk notation som indikerar att 0 är inkluderande och att BIT inte ingår i intervallet (det är vanligt i båda C / C ++ -dokumentationen).
Svar
-
Dina typer är onödiga – använd bara osignerad char och int som standardbiblioteket skulle göra.
-
I samma ämne är din enum bool onödig eftersom i C inte-noll anger det verkliga tillståndet. Du bekräftar det själv eftersom get () antar att värdet 1 är sant. Alla antar detta och så är typen överflödig. Dessutom är det också fel för om jag ändrar ditt antal till
typedef enum{true=0, false} bool;misslyckas din funktion, även om det logiskt sett är en rimlig sak att göra.
Om du vill använda en sådan bool ska du uttryckligen returnera ett av dess värden:
return ((a >> pos) & 1) ? true : false;men det finns egentligen ingen mening med det. Skicka bara ett int som standardbiblioteket skulle göra.
-
bitmapGet () att returnera en bool verkar felaktigt benämnd för mig. Bitmappsbitarna har värdena 1 och 0, inte sanna och falska (även om de är för närvarande samma). Att kalla det bitmapIsSet () skulle vara mer logiskt.
-
sizeof (char) är 1 per definition, så BIT kan ersättas med CHAR_BIT
-
Öppningsfästen för funktioner finns normalt i kolumn 0
-
Parametrarnas ordning för bitmapSearch skulle vara mer logisk är storleken följt den sak den refererar till (bitmap).
-
Startparametern för bitmapSearch är fel. För att ange en sökning som börjar från bit 0 (utan tvekan den vanligaste) måste den som ringer passera -1 !!
-
Varför skicka ”pos” -parametern som en ”byte”? Du har definierat ”byte” för att representera bitmappsbyte och ”pos” är verkligen inte en av dem. Du får kompilatorvarningar om de är aktiverade (de borde vara) om att skicka argument med olika bredder på grund av prototyper. Och att begränsa ”pos” till en byte kan lägga till en extra maskininstruktion (titta på monteraren) samtidigt som man inte uppnår något. Om du kunde definiera en typ pos_t med intervallet 0..7 som du verkar vilja kan du argumentera för att det på något sätt var korrekt, men eftersom du inte kan göra det i C och tydligt har bytevärdet intervallet 0 .. 255, det är inte bättre än att använda ett int.
Svar
Gick inte ”t fråga om prestanda, men du kan påskynda bitmapSearch för glesa bitmappar genom att först titta på en byte åt gången. Om du letar efter en 1 kan du hoppa över byte som är 0x00, och om letar du efter ett 0 kan du hoppa över byte som är 0xFF. Därefter kan du skanna bitarna på nästa byte eller använda en uppslagstabell på den.
När det gäller API: et kan du lägga till
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); så att klienten inte behöver oroa sig för hur många byte som ska allokera.
Och / eller ge ett makro för att hjälpa till med allokeringar. Ett makro istället för en funktion om du vill att det ska visas i arrayallokeringar.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) Jag skulle också ha bitmapSearch ta storleken som ett bitantal istället för ett byteantal. Om klienten bara bryr sig om, säg, 26 bitar för bokstäver, behöver de inte oroa sig för en sökning som returnerar 27 eftersom bitmappen verkligen har 32 bitar i sig.