Recentemente ho iniziato a ripulire i miei progetti e ho deciso di creare un repository personale di bit di codice utili. Ho trovato questo codice bitmap tra di loro e lho modificato pesantemente e apprezzerei se qualcuno potesse rivederlo, perché non sono abituato a operazioni bit a bit e simili. Il codice è abbastanza portabile o dovrebbero essere apportate modifiche?
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); } Commenti
- A chiunque stia ancora seguendo questo post, ho affidato il codice a github qui . Ho anche aggiunto tutti i tuoi commenti come problemi. Grazie per i tuoi commenti e inizierò a implementarli.
Rispondi
Se prevedi che il tuo codice sarà mai usato da C ++ (che è un sacco di codice C) quindi non dovresti usare alcun identificatore con un doppio trattino basso.
#ifndef BITMAP__ // ^^ May cause problems in C++ Poiché questo è riservato per limplementazione in C ++. Anche il termine BITMAP è molto generico ed è molto probabile che ti scontrerai con altre librerie cercando di renderlo più unico per il tuo progetto.
Stai assumendo che un carattere sia 8 bit.
#define BIT (8*sizeof(byte)) Lo standard non lo dice (è almeno 8 bit) ma in realtà è definito tramite la macro CHAR_BITS quindi dovresti usare:
#define BIT (CHAR_BITS*sizeof(byte)) Il tuo file di intestazione è il modo in cui la maggior parte delle persone vedrà il tuo codice per la prima volta e cercherà di capire come usarlo. Pertanto, inserire i nomi dei parametri nel file di intestazione è probabilmente una buona idea in quanto aiuta a documentarne lutilizzo.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Aggiunge lazione di bitmapSearch non è ovvio quindi un commento sul suo utilizzo nellintestazione sarebbe probabilmente una buona idea. In realtà una piccola descrizione di come il primo parametro può essere un array sarebbe probabilmente una buona idea (poiché non è ovvio senza leggere il codice).
Fai attenzione ai commenti:
/* pos is something from 0 to 7*/ Questo è vero solo se fai delle ipotesi (A: quella dimensione di (byte) == 1 B: la moltiplichi per 8). Il commento avrebbe dovuto essere:
/* pos is a value between [0, BIT) */ Nota luso di “[” a sinistra e “)” a destra. È una notazione matematica che indica che 0 è inclusivo e BIT non è incluso nellintervallo (è comune nella documentazione C / C ++).
Risposta
-
I tuoi tipi non sono necessari – usa solo char e int senza segno come farebbe la libreria standard.
-
Sullo stesso argomento, il tuo enum bool non è necessario perché in C diverso da zero indica lo stato vero. Lo confermi tu stesso perché get () presume che il valore 1 sia vero. Tutti lo presumono e quindi il tipo è ridondante. Inoltre è anche sbagliato perché se cambio la tua enum in
typedef enum{true=0, false} bool;la tua funzione fallisce, anche se logicamente è una cosa ragionevole da fare.
Se vuoi usare un bool come questo, dovresti restituire esplicitamente uno dei suoi valori:
return ((a >> pos) & 1) ? true : false;ma non ha davvero senso in questo. Restituisci semplicemente un int come farebbe la libreria standard.
-
bitmapGet () che restituisce un bool mi sembra errato. I bit bitmap hanno valori 1 e 0, non vero e falso (anche se attualmente sono gli stessi). Chiamarlo bitmapIsSet () sarebbe più logico.
-
sizeof (char) è 1 per definizione, quindi BIT può essere sostituito con CHAR_BIT
-
Le parentesi di apertura per le funzioni sono normalmente nella colonna 0
-
Lordine dei parametri per bitmapSearch sarebbe più logico se fosse la dimensione seguita dalla cosa a cui si riferisce (bitmap).
-
Il parametro iniziale per bitmapSearch è sbagliato. Per specificare una ricerca a partire dal bit 0 (sicuramente il più comune) il chiamante deve passare -1 !!
-
Perché passare il parametro “pos” come “byte”? Hai definito “byte” per rappresentare i byte bitmap e “pos” non è certamente uno di quelli. Riceverai gli avvisi del compilatore se sono abilitati (dovrebbero esserlo) sul passaggio di argomenti con larghezze diverse a causa dei prototipi. E restringere “pos” a un byte può aggiungere unistruzione macchina extra (guarda lassembler) senza ottenere nulla. Se potessi definire un tipo pos_t con lintervallo 0..7 che sembri desiderare, potresti sostenere che in qualche modo è corretto, ma poiché non puoi farlo in C e chiaramente il valore del byte ha lintervallo 0 .. 255, non è meglio che usare un int.
Risposta
Non “t chiedere informazioni sulle prestazioni, ma puoi velocizzare bitmapSearch per bitmap sparse osservando prima un byte alla volta. Se cerchi un 1, puoi saltare i byte 0x00 e se cercando uno 0, puoi saltare i byte che sono 0xFF, dopodiché puoi scansionare i bit sul byte successivo o usare una tabella di ricerca su di esso.
Per quanto riguarda lAPI, potresti aggiungere
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); in modo che il client non debba “preoccuparsi di quanti byte allocare.
E / o fornire una macro per facilitare le allocazioni. Una macro invece di una funzione se si desidera che appaia nelle allocazioni di array.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) Devo anche bitmapSearch prendere la sua dimensione come un conteggio di bit invece che come un conteggio di byte. Quindi, se il client si preoccupa solo, diciamo, di 26 bit per le lettere, non deve preoccuparsi che una ricerca restituisca 27 perché la bitmap contiene in realtà 32 bit.