busybox使用bsearch二分法、折半查找库函数完成对所有命令的快速查找

busybox使用bsearch二分法、折半查找库函数完成对所有命令的快速查找


《改进busybox查找命令和执行命令对应函数的方法》

#include <stdlib.h>
#include <stdio.h>

#define ALIGN1 __attribute__((aligned(1)))
#define ALIGN2 __attribute__((aligned(2)))
#define APPLET_NAME(i) (applet_names + applet_nameofs[i])
#define ARRAY_SIZE(x) ((unsigned)(sizeof(x) / sizeof((x)[0])))

const unsigned short applet_nameofs[];//每个命令对应的偏移表,这是busybox查找命令的核心所在.

const char applet_names[];
void *lbsearch(const void *key, const void *base0, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));


static int applet_name_compare(const void *name, const void *v)
{
    int i = (const char *)v - applet_names;//将当前打算比较第几个的序号通过计算拿出来,赋值给i
    return strcmp(name, APPLET_NAME(i));
//APPLET_NAME(i)用来取出第i个命令对应的命令字符串,然后比较,
//于是bsearch将可以根据结果来使用二分法,具体往哪个方向进行下一次折半计算[luther.gliethttp].
}

int main(int argc, char *argv[])
{
    const char *p;
    int i;
    if(argc < 2)
    {
        printf("luther name2find0 name2find1 name2find2 ...\n");
        return 0;
    }
    for(i = 1;i < argc;i++)
    {
        p = lbsearch(argv[i], applet_names, 288/*ARRAY_SIZE(applet_main)*/, 1, applet_name_compare);
        if(p)
        {
            int index = p - applet_names;
            printf("%-20s,found at %d\n", APPLET_NAME(index), index);
        }
        else
        {
            printf("%-20s,not found,sorry\n", argv[i]);
        }
    }
    return 0;
}


void *
lbsearch(const void *key, const void *base0, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *))
{
    const char *base = base0;
    int lim, cmp;
    const void *p;

    for (lim = nmemb; lim != 0; lim >>= 1) {
        p = base + (lim >> 1) * size;
        cmp = (*compar)(key, p);
        if (cmp == 0)
            return ((void *)p);
        if (cmp > 0) {    /* key > p: move right */
            base = (char *)p + size;
            lim--;
        } /* else move left */
    }
    return (NULL);
}


const char applet_names[] ALIGN1 = ""
"[" "\0"
"[[" "\0"
"addgroup" "\0"
"adduser" "\0"
"adjtimex" "\0"
"ar" "\0"
"arp" "\0"
"arping" "\0"
"ash" "\0"
"awk" "\0"
"basename" "\0"
"brctl" "\0"
"bunzip2" "\0"
"bzcat" "\0"
"bzip2" "\0"
"cal" "\0"
"cat" "\0"
"catv" "\0"
"chat" "\0"
"chattr" "\0"
"chgrp" "\0"
"chmod" "\0"
"chown" "\0"
"chpasswd" "\0"
"chpst" "\0"
"chroot" "\0"
"chrt" "\0"
"chvt" "\0"
"cksum" "\0"
"clear" "\0"
"cmp" "\0"
"comm" "\0"
"cp" "\0"
"cpio" "\0"
"crond" "\0"
"crontab" "\0"
"cryptpw" "\0"
"cut" "\0"
"date" "\0"
"dc" "\0"
"dd" "\0"
"deallocvt" "\0"
"delgroup" "\0"
"deluser" "\0"
"depmod" "\0"
"df" "\0"
"dhcprelay" "\0"
"diff" "\0"
"dirname" "\0"
"dmesg" "\0"
"dnsd" "\0"
"dos2unix" "\0"
"du" "\0"
"dumpkmap" "\0"
"dumpleases" "\0"
"echo" "\0"
"ed" "\0"
"egrep" "\0"
"eject" "\0"
"env" "\0"
"envdir" "\0"
"envuidgid" "\0"
"ether-wake" "\0"
"expand" "\0"
"expr" "\0"
"fakeidentd" "\0"
"false" "\0"
"fbset" "\0"
"fbsplash" "\0"
"fdflush" "\0"
"fdformat" "\0"
"fdisk" "\0"
"fetchmail" "\0"
"fgrep" "\0"
"find" "\0"
"fold" "\0"
"free" "\0"
"freeramdisk" "\0"
"fsck" "\0"
"fsck.minix" "\0"
"ftpget" "\0"
"ftpput" "\0"
"fuser" "\0"
"getopt" "\0"
"getty" "\0"
"grep" "\0"
"gunzip" "\0"
"gzip" "\0"
"halt" "\0"
"hdparm" "\0"
"head" "\0"
"hexdump" "\0"
"hostid" "\0"
"hostname" "\0"
"httpd" "\0"
"hwclock" "\0"
"id" "\0"
"ifconfig" "\0"
"ifdown" "\0"
"ifenslave" "\0"
"ifup" "\0"
"inetd" "\0"
"init" "\0"
"inotifyd" "\0"
"insmod" "\0"
"install" "\0"
"ip" "\0"
"ipaddr" "\0"
"ipcalc" "\0"
"ipcrm" "\0"
"ipcs" "\0"
"iplink" "\0"
"iproute" "\0"
"iprule" "\0"
"iptunnel" "\0"
"kbd_mode" "\0"
"kill" "\0"
"killall" "\0"
"killall5" "\0"
"klogd" "\0"
"last" "\0"
"length" "\0"
"less" "\0"
"linux32" "\0"
"linux64" "\0"
"linuxrc" "\0"
"ln" "\0"
"loadfont" "\0"
"loadkmap" "\0"
"logger" "\0"
"login" "\0"
"logname" "\0"
"logread" "\0"
"losetup" "\0"
"lpd" "\0"
"lpq" "\0"
"lpr" "\0"
"ls" "\0"
"lsattr" "\0"
"lsmod" "\0"
"lzmacat" "\0"
"makedevs" "\0"
"man" "\0"
"md5sum" "\0"
"mdev" "\0"
"mesg" "\0"
"microcom" "\0"
"mkdir" "\0"
"mkfifo" "\0"
"mkfs.minix" "\0"
"mknod" "\0"
"mkswap" "\0"
"mktemp" "\0"
"modprobe" "\0"
"more" "\0"
"mount" "\0"
"mountpoint" "\0"
"mt" "\0"
"mv" "\0"
"nameif" "\0"
"nc" "\0"
"netstat" "\0"
"nice" "\0"
"nmeter" "\0"
"nohup" "\0"
"nslookup" "\0"
"od" "\0"
"openvt" "\0"
"passwd" "\0"
"patch" "\0"
"pgrep" "\0"
"pidof" "\0"
"ping" "\0"
"ping6" "\0"
"pipe_progress" "\0"
"pivot_root" "\0"
"pkill" "\0"
"poweroff" "\0"
"printenv" "\0"
"printf" "\0"
"ps" "\0"
"pscan" "\0"
"pwd" "\0"
"raidautorun" "\0"
"rdate" "\0"
"rdev" "\0"
"readahead" "\0"
"readlink" "\0"
"readprofile" "\0"
"realpath" "\0"
"reboot" "\0"
"renice" "\0"
"reset" "\0"
"resize" "\0"
"rm" "\0"
"rmdir" "\0"
"rmmod" "\0"
"route" "\0"
"rpm" "\0"
"rpm2cpio" "\0"
"rtcwake" "\0"
"run-parts" "\0"
"runlevel" "\0"
"runsv" "\0"
"runsvdir" "\0"
"rx" "\0"
"script" "\0"
"sed" "\0"
"sendmail" "\0"
"seq" "\0"
"setarch" "\0"
"setconsole" "\0"
"setfont" "\0"
"setkeycodes" "\0"
"setlogcons" "\0"
"setsid" "\0"
"setuidgid" "\0"
"sh" "\0"
"sha1sum" "\0"
"showkey" "\0"
"slattach" "\0"
"sleep" "\0"
"softlimit" "\0"
"sort" "\0"
"split" "\0"
"start-stop-daemon" "\0"
"stat" "\0"
"strings" "\0"
"stty" "\0"
"su" "\0"
"sulogin" "\0"
"sum" "\0"
"sv" "\0"
"svlogd" "\0"
"swapoff" "\0"
"swapon" "\0"
"switch_root" "\0"
"sync" "\0"
"sysctl" "\0"
"syslogd" "\0"
"tac" "\0"
"tail" "\0"
"tar" "\0"
"taskset" "\0"
"tcpsvd" "\0"
"tee" "\0"
"telnet" "\0"
"telnetd" "\0"
"test" "\0"
"tftp" "\0"
"tftpd" "\0"
"time" "\0"
"top" "\0"
"touch" "\0"
"tr" "\0"
"traceroute" "\0"
"true" "\0"
"tty" "\0"
"ttysize" "\0"
"udhcpc" "\0"
"udhcpd" "\0"
"udpsvd" "\0"
"umount" "\0"
"uname" "\0"
"uncompress" "\0"
"unexpand" "\0"
"uniq" "\0"
"unix2dos" "\0"
"unlzma" "\0"
"unzip" "\0"
"uptime" "\0"
"usleep" "\0"
"uudecode" "\0"
"uuencode" "\0"
"vconfig" "\0"
"vi" "\0"
"vlock" "\0"
"watch" "\0"
"watchdog" "\0"
"wc" "\0"
"wget" "\0"
"which" "\0"
"who" "\0"
"whoami" "\0"
"xargs" "\0"
"yes" "\0"
"zcat" "\0"
"zcip" "\0"
;

const unsigned short applet_nameofs[] ALIGN2 = {
0x0000,
0x0002,
0x0005,
0x000e,
0x0016,
0x001f,
0x0022,
0x0026,
0x002d,
0x0031,
0x0035,
0x003e,
0x0044,
0x004c,
0x0052,
0x0058,
0x005c,
0x0060,
0x0065,
0x006a,
0x0071,
0x0077,
0x007d,
0x0083,
0x008c,
0x0092,
0x0099,
0x009e,
0x00a3,
0x00a9,
0x00af,
0x00b3,
0x00b8,
0x00bb,
0x00c0,
0x80c6,
0x00ce,
0x00d6,
0x00da,
0x00df,
0x00e2,
0x00e5,
0x00ef,
0x00f8,
0x0100,
0x0107,
0x010a,
0x0114,
0x0119,
0x0121,
0x8127,
0x012c,
0x0135,
0x0138,
0x0141,
0x014c,
0x0151,
0x0154,
0x015a,
0x0160,
0x0164,
0x016b,
0x0175,
0x0180,
0x0187,
0x018c,
0x0197,
0x019d,
0x01a3,
0x01ac,
0x01b4,
0x01bd,
0x01c3,
0x01cd,
0x01d3,
0x01d8,
0x01dd,
0x01e2,
0x01ee,
0x01f3,
0x01fe,
0x0205,
0x020c,
0x0212,
0x0219,
0x021f,
0x0224,
0x022b,
0x0230,
0x0235,
0x023c,
0x0241,
0x0249,
0x0250,
0x0259,
0x025f,
0x0267,
0x026a,
0x0273,
0x027a,
0x0284,
0x0289,
0x028f,
0x0294,
0x029d,
0x02a4,
0x02ac,
0x02af,
0x02b6,
0x82bd,
0x82c3,
0x02c8,
0x02cf,
0x02d7,
0x02de,
0x02e7,
0x02f0,
0x02f5,
0x02fd,
0x0306,
0x030c,
0x0311,
0x0318,
0x031d,
0x0325,
0x032d,
0x0335,
0x0338,
0x0341,
0x034a,
0x8351,
0x0357,
0x035f,
0x0367,
0x036f,
0x0373,
0x0377,
0x037b,
0x037e,
0x0385,
0x038b,
0x0393,
0x039c,
0x03a0,
0x03a7,
0x03ac,
0x03b1,
0x03ba,
0x03c0,
0x03c7,
0x03d2,
0x03d8,
0x03df,
0x03e6,
0x03ef,
0x03f4,
0x03fa,
0x0405,
0x0408,
0x040b,
0x0412,
0x0415,
0x041d,
0x0422,
0x0429,
0x042f,
0x0438,
0x043b,
0x8442,
0x0449,
0x044f,
0x0455,
0x445b,
0x0460,
0x0466,
0x0474,
0x047f,
0x0485,
0x048e,
0x0497,
0x049e,
0x04a1,
0x04a7,
0x04ab,
0x04b7,
0x04bd,
0x04c2,
0x04cc,
0x04d5,
0x04e1,
0x04ea,
0x04f1,
0x04f8,
0x04fe,
0x0505,
0x0508,
0x050e,
0x0514,
0x051a,
0x051e,
0x0527,
0x052f,
0x0539,
0x0542,
0x0548,
0x0551,
0x0554,
0x055b,
0x055f,
0x0568,
0x056c,
0x0574,
0x057f,
0x0587,
0x0593,
0x059e,
0x05a5,
0x05af,
0x05b2,
0x05ba,
0x05c2,
0x05cb,
0x05d1,
0x05db,
0x05e0,
0x05e6,
0x05f8,
0x05fd,
0x0605,
0x860a,
0x060d,
0x0615,
0x0619,
0x061c,
0x0623,
0x062b,
0x0632,
0x063e,
0x0643,
0x064a,
0x0652,
0x0656,
0x065b,
0x065f,
0x0667,
0x066e,
0x0672,
0x0679,
0x0681,
0x0686,
0x068b,
0x0691,
0x0696,
0x069a,
0x06a0,
0x46a3,
0x06ae,
0x06b3,
0x06b7,
0x06bf,
0x06c6,
0x06cd,
0x06d4,
0x06db,
0x06e1,
0x06ec,
0x06f5,
0x06fa,
0x0703,
0x070a,
0x0710,
0x0717,
0x071e,
0x0727,
0x0730,
0x0738,
0x873b,
0x0741,
0x0747,
0x0750,
0x0753,
0x0758,
0x075e,
0x0762,
0x0769,
0x076f,
0x0773,
0x0778,
};

执行一下看看测试结果:
[luther@gp tmp]$ ./luther ls list vi pwd echo ash find ps top
ls                  ,found at 137
list                ,not found,sorry
vi                  ,found at 275
pwd                 ,found at 182
echo                ,found at 55
ash                 ,found at 8
find                ,found at 74
ps                  ,found at 180
top                 ,found at 252