多层位图查表法

在嵌入式操作体系中，特别是实时操作体系中常常选用位图法处理使命的安排妥当以及查找最高优先级的快速办法，即经过对一切的或许性选用查表的方法即可完成关于uC/OS-II这种64（ 2^8）个优先级使命的小体系，能够经过求取x,y,得到对应的最高优先级值，并且在查表的过程中，只要256种或许性，经过简略的查表就能快速的完成，可是当使命的优先级数大于64个时，那又该怎么让完成呢？由于此刻的查表不在那么简单，比存在16个bit时，2^16=65536，也便是存在65536种或许性，这个数据表格太大因而不是咱们考虑的方法，那么怎么确认呢，此刻选用分层的方法就能比较快速的完成，在64个使命时首要能够选用一个安排妥当表每一个bit代表一个使命优先级，别的预备一个标志变量，每一个bit表明详细的某一个组，每一组八个数据，经过这种x,y的方法能够快速的完成查找。当使命关于64个时，咱们能够测验多添加一维z的方法表明不同的使命，也便是完成分层，总共分成了三层，这样就能经过这种多层的方法，经过同一个查询表（256种或许性）的运用而快速的确认x,y,z,从而得到最高的优先级号。这种三层的方法最多能够支撑512个优先级号的操作体系。当多于这种状况时，就需求再次添加层数。

详细的完成如下：

z的每一个bit对应着1个y。也便是总共对应8个y。

y的每一个bit对应着一个x，也便是总共对应着8*8个x。

每一个x刚好也就对应着8个使命优先级号。这样就能够经过x,y,z设置优先级。

因而能够选用下面的方法界说一个结构体：

#ifndef __HIGH_BITMAP_H_H__
#define __HIGH_BITMAP_H_H__

#define LENGTH_HIGHLAYER 8
#define LENGTH_BYTE 8
typedef unsigned char Byte;

typedef struct
{
Byte high_Layer;
Byte mid_Layer[LENGTH_HIGHLAYER];
Byte low_Layer[LENGTH_HIGHLAYER*LENGTH_BYTE];
}BitMaps;

#ifdef __cplusplus
extern “C”
{
#endif

void inital_bitmap(BitMaps *bitmap);
void set_bitmap(BitMaps *bitmap,int prio);
int calculate_high_prio(BitMaps *bitmap);

#ifdef __cplusplus
}
#endif

#endif

根本的操作函数如下：

#include”high_bitmap.h”
#include

int const OSUnMapTbl[256] = {
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x00 to 0x0F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x10 to 0x1F */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x20 to 0x2F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x30 to 0x3F */
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x40 to 0x4F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x50 to 0x5F */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x60 to 0x6F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x70 to 0x7F */
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x80 to 0x8F */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0x90 to 0x9F */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xA0 to 0xAF */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xB0 to 0xBF */
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xC0 to 0xCF */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xD0 to 0xDF */
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, /* 0xE0 to 0xEF */
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 /* 0xF0 to 0xFF */
};

void inital_bitmap(BitMaps *bitmap)
{
int i = 0;
if(NULL == bitmap)
{
return ;
}

bitmap->high_Layer = 0x00;
for(; i < sizeof(bitmap->mid_Layer); ++ i)
{
bitmap->mid_Layer[i] = 0x00;
}

for (i = 0; i < sizeof(bitmap->low_Layer); ++ i)
{
bitmap->low_Layer[i] = 0x00;
}
}

void set_bitmap(BitMaps *bitmap,int prio)
{
int x,y,z;
if(NULL == bitmap || prio >= 512)
{
return ;
}

z = (prio >> 6)& 0x7;
bitmap->high_Layer |= 1<> 3) & 0x7;
bitmap->mid_Layer[z] |= 1<

x = prio & 0x7;
bitmap->low_Layer[z*8+y] |= 1< }

int calculate_high_prio(BitMaps *bitmap)
{
int x,y,z;

if(NULL == bitmap)
{
return -1;
}

z = OSUnMapTbl[bitmap->high_Layer];
y = OSUnMapTbl[bitmap->mid_Layer[z]];
x = OSUnMapTbl[bitmap->low_Layer[(z << 3)+y]];

z = (z << 6) + (y << 3) + x;

return z;
}

这种分层的完成方法能够便利的处理位图中多种或许性问题，经过分层能够使得各个变量x,y,z都能过运用查询表（256种或许），处理了超大或许性的问题。当然这种方法也不是仅有的，可是确实是一种可行的计划，同享查询表的。

文章查询的思路uC/OS-II中查询的方法相同，也便是当对应的使命需求安排妥当时，能够经过设置对应的x,y,z对应的bit为1即可。