12月 17, 2020
Articles
コメントはまだありません

ビットマップの実装

最近プロジェクトのクリーンアップを開始し、有用なコードの個人リポジトリを作成することにしました。私はそれらの間にこのビットマップコードを見つけ、それを大幅に編集しました。私はビット単位の操作などに慣れていないので、誰かがそれをレビューしていただければ幸いです。コードは十分に移植可能ですか、それとも変更が必要ですか？

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); }

コメント

  • この投稿をまだフォローしている人には、コードをgithub ここにコミットしました。また、すべてのコメントを問題として追加しました。コメントありがとうございます。実装を開始します。

回答

コードがC ++（多くのCコード）から使用する場合は、二重下線付きの識別子を使用しないでください。

#ifndef BITMAP__ // ^^ May cause problems in C++

これは実装用に予約されているため、 C ++で。また、ビットマップという用語は非常に一般的であり、他のライブラリと衝突する可能性が非常に高く、プロジェクトに固有のものにしようとします。

charは8ビットであると想定しています。

#define BIT (8*sizeof(byte))

標準ではこれは示されていません（少なくとも8ビットです）が、実際にはマクロCHAR_BITSを介して定義されているため、次を使用する必要があります。

#define BIT (CHAR_BITS*sizeof(byte))

ヘッダーファイルは、ほとんどの人が最初にコードを見て、その使用方法を理解しようとする方法です。したがって、パラメータ名をヘッダーファイルに入れることは、それらの使用法を文書化するのに役立つため、おそらく良い考えです。

bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int);

は明らかではないため、ヘッダーでの使用法についてのコメントはおそらく良い考えです。実際には、最初のパラメーターを配列にする方法についての小さな宣伝文句がおそらく良い考えです（コードを読まないと明らかではないため）。

コメントに注意してください：

/* pos is something from 0 to 7*/

これは、仮定を行う場合にのみ当てはまります（A：そのsizeof（byte）== 1 B：これに8を掛けます）。コメントは次のようになっているはずです。

/* pos is a value between [0, BIT) */

左側の「[」と右側の「）」の使用に注意してください。これは、0が含まれ、BITが範囲に含まれないことを示す数学表記です（C / C ++の両方のドキュメントで一般的です）。

回答

  1. 型は不要です。標準ライブラリと同じようにunsignedcharとintを使用してください。

  2. 同じトピックで、Cではゼロ以外の値が真の状態を示すため、列挙型ブール値は不要です。 get（）は値1が真であると想定しているため、自分で確認します。誰もがこれを想定しているため、タイプは冗長です。さらに、列挙型を

    typedef enum{true=0, false} bool;

    に変更すると、論理的には合理的なことですが、関数が失敗するため、これも間違っています。

    そのようなブール値を使用する場合は、その値の1つを明示的に返す必要があります：

    return ((a >> pos) & 1) ? true : false;

    しかし、これには実際には意味がありません。標準ライブラリと同じようにintを返すだけです。

  3. boolを返すbitmapGet（）は、私には間違った名前が付けられているようです。ビットマップビットの値は1と0であり、trueとfalseではありません（これらは現在同じですが）。これをbitmapIsSet（）と呼ぶ方が論理的です。

  4. sizeof（char）は定義上1であるため、BITをCHAR_BITに置き換えることができます

  5. 関数の開き括弧は通常、列0にあります

  6. ビットマップ検索のパラメーターの順序は、参照するもの（ビットマップ）に従ったサイズであるほど論理的です。

  7. bitmapSearchの開始パラメータが間違っています。ビット0（確かに最も一般的）から始まる検索を指定するには、呼び出し元は-1を渡す必要があります!!

  8. 「pos」パラメーターを「バイト」として渡すのはなぜですか？ビットマップバイトを表すために「byte」を定義しましたが、「pos」は確かにそれらの1つではありません。プロトタイプのために異なる幅の引数を渡すことについて有効になっている場合（有効になっている必要があります）、コンパイラの警告が表示されます。また、「pos」をバイトに制限すると、何も達成せずに追加のマシン命令（アセンブラを参照）が追加される場合があります。必要と思われる範囲0..7でタイプpos_tを定義できる場合、それは何らかの方法で正しいと主張するかもしれませんが、Cではそれを行うことができず、明らかにバイト値の範囲は0です。 255、intを使用するよりも良い方法ではありません。

回答

しませんでしたパフォーマンスについて質問しますが、最初に1バイトずつ調べることで、スパースビットマップのbitmapSearchを高速化できます。1を探す場合は、0x00のバイトをスキップできます。 0を探す場合は、0xFFのバイトをスキップできます。その後、次のバイトのビットをスキャンするか、そのバイトでルックアップテーブルを使用できます。

APIに関する限り、追加することができます

byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap);

クライアントがバイト数を気にする必要がないように、 割り当てます。

割り当てを支援するマクロを提供します。配列の割り当てに表示する場合は、関数ではなくマクロを提供します。

#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT)

bitmapSearchもそのサイズをバイトカウントではなくビットカウントとして取得します。 次に、クライアントがたとえば文字の26ビットのみを気にする場合、ビットマップには実際には32ビットが含まれているため、検索で27が返されることを心配する必要はありません。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です