Thursday, July 26, 2018

Where Things go - Unix bin/ series

Where things go when packages are installed?


/bin, /usr/bin, /usr/local/bin


Unix shell script is all about "executing a program".  In general, program is designed to do a certain thing very well with versatile option switches.  For example, "-l" switch for "/bin/ls".  "Executing a program" is not limited to CLI or shell activity.  In heart of Unix, a system is composed by a unit of "Process", which is a memory image of an executable program.
The executables are placed in many places.  The standard locations are /bin, /usr/bin, and /usr/local/bin.  Each are just conventions.  For example, if we install firefox on a Linux system, usually it will be placed in /usr/bin/firefox.  If someone decided to put it in /bin, that's okay.  This doesn't break the system.  The search path is defined in a shell variable called "PATH".  Most programming languages will have similar config variable for searching.  For example, Java has CLASSPATH and Golang has GOPATH.  Python has PYTHONPATH, which will be prepended to sys.path list when an interpreter initiates.  Unix PATH usually contains minimum "/bin" and "/usr/bin".   There are also /sbin, /usr/sbin, and /usr/local/sbin.  But, sbin directory is only for privileged purpose.  Normal user might be able to execute this in read-only fashion.

Why so many "bin" (binary) directories?  As a matter of fact, the distinction between these directories became blurred.  For example, modern Fedora symlinks /bin to /usr/bin.  But, let's visit what was the "intention" of each bin/ directories.

/bin


/bin is core executable of a unix operating system.  The biggest role of /bin is to provide minimum binaries for boot and recovery mode.  Therefore, the convention of /bin is part of "/" partition where boot is mounting.  The binary files in this directory will be always available in whichever environment the process is in.  The best example is /bin/ls.  We can always assume that "ls" command is available in any situation.  Usually, packages named binutils and coreutils will deploy binaries into /bin.

/usr/bin


/usr/bin is for distribution's binary files.  When a distro organizes packages, the binaries part of OS distro will be placed into /usr/bin directory.  So, from our first questions specific to my favorite editor Emacs, "yum install emacs" will place Emacs binary into /usr/bin as /usr/bin/emacs, and other parts (libraries, elisp files) into different directories, called /usr/lib.  We will visit this soon.

/usr/local/bin


This directory is for local system.  This directory is for any software which are not part of distro.  For example, if we download a source code of tmux, patch something on our own for unknown feature, and install on the system, then most likely it will be placed into /usr/local/bin.  The GNU build system assumes "--prefix" config to "/usr/local" if not specified.  Doing so, we can distinguish tmux binary from our source compilation and distro installed tmux binary.  The former binary will be /usr/local/bin/tmux, and the latter binary will be /usr/bin/tmux.

/lib, /usr/lib, and /usr/local/lib


We only handled /bin series.  But an executable file commonly comes with multiple files for many reasons.  /lib supports other files for an executable. 

/lib directories are for supporting files for executables in /bin.  Anything which makes executable file useful, but which is not executable by itself, will be placed in /lib series directory.  The convention is, executable files for /bin will find libraries from /lib or /lib64.  The same convention applies to /usr/bin searching /usr/lib or /usr/lib64.  And, the same rule for /usr/local/bin.

To complete the conversation, let me mention more directories.  There are even more important directories in Unix system.
The first level is the top level, which is '/'.  For '/' level, /bin, /sbin/, and /lib are the main directories for binary files.  As modern systems become 64 bit CPU, modern systems include /lib64 directory.  We know /bin and /sbin.  These are for executable files.  /lib and /lib64 are library binary files, or linkable binary files.  Most of them are C libraries, which other languages will stub-in with their libc interfacing.  There are two important special directories, /etc and /var.  In my opinion, /etc/ is named incorrect.  /etc is one of the most important directory in the system, which contains all config files for the OS.  These are mostly text files.  /var is variable content directory.  The most popular directory is /var/log, which contains system logs.  /var contains mostly data files, either in plain text or binary format.  /proc, /dev, /sys won't be covered here.

The next level is the /usr level.  On this level, /usr/include, /usr/bin, /usr/sbin, /usr/lib, /usr/lib64, and /usr/share will be placed.  We know /usr/bin and /usr/sbin.  These are for executable files.  /usr/lib and /usr/lib64 can be guessed from previous level.  These are linkable C libraries.  (Some are written in assembly, but both asm/c are ended up elf/elf64 kind of binary format, which are treated as the same way. )  /usr/include is where C header files are placed.  /usr/share will have other stuff like man pages, fonts for Graphics system, etc.
The next level is /usr/local.  This is similar to /usr level.  /usr/local/include, /usr/local/bin, /usr/local/sbin, /usr/local/lib, /usr/local/lib64, /usr/local/share.   They behave the same as /usr level, but these directories are from my local system installation, not from the distro.


Back to our question:  Where things go?


At this point, we can dig a further detail about file layout laid by yum package manager.  When we want to install mysql server, (thanks to Oracle, opensource group had to rename/fork mysql to mariadb), we issue "yum install mariadb-server" on RHEL or CentOS server.  In Fedora system, dnf is used instead of yum.  "dnf install mariadb-server".
To look what files were installed, we can use following command.  "rpm -ql" will list files in a given package.  As we can see, mysql server provided /etc config, /usr/bin/ executables including the MySQL server itself(/usr/bin/mysqld_safe), mysql libraries (*.so files) under /usr/lib64 directory, document and manpages under /usr/share, and /var/lib/mysql directory for run-variable (such as mysql.sock socket file), and logs in /var/log/mariadb.

$ rpm -ql mariadb-server
/etc/logrotate.d/mariadb
/etc/my.cnf.d/mariadb-server.cnf
/run/mariadb
/usr/bin/aria_chk
/usr/bin/aria_dump_log
/usr/bin/aria_ftdump
/usr/bin/aria_pack
/usr/bin/aria_read_log
/usr/bin/innochecksum
/usr/bin/mariadb-service-convert
/usr/bin/my_print_defaults
/usr/bin/myisam_ftdump
/usr/bin/myisamchk
/usr/bin/myisamlog
/usr/bin/myisampack
/usr/bin/mysql_install_db
/usr/bin/mysql_secure_installation
/usr/bin/mysql_tzinfo_to_sql
/usr/bin/mysqld_safe
/usr/bin/replace
/usr/bin/resolve_stack_dump
/usr/bin/resolveip
/usr/bin/wsrep_sst_common
/usr/bin/wsrep_sst_mariabackup
/usr/bin/wsrep_sst_mysqldump
/usr/bin/wsrep_sst_rsync
/usr/bin/wsrep_sst_rsync_wan
/usr/bin/wsrep_sst_xtrabackup
/usr/bin/wsrep_sst_xtrabackup-v2
/usr/lib/.build-id
/usr/lib/.build-id/07
/usr/lib/.build-id/07/69bc37f26a1a41c25db627ca6e741f3674283d
/usr/lib/.build-id/0d
/usr/lib/.build-id/0d/5e64382cb9d8547a4f39e7ecb6e9230c15d2a4
/usr/lib/.build-id/13
/usr/lib/.build-id/13/9d378f787c7458ed20cca0f08725a4b46d95d6
/usr/lib/.build-id/18
/usr/lib/.build-id/18/6a7a4263fdddaa04c6d56d8fc53bbadc0b222b
/usr/lib/.build-id/1a
/usr/lib/.build-id/1a/330e5f506700544e7e83f80a006fbea60f0b44
/usr/lib/.build-id/2a
/usr/lib/.build-id/2a/1c3ed5bbdcfa8f3c59a8b1b05deabbce96299d
/usr/lib/.build-id/2b
/usr/lib/.build-id/2b/4e76a3395d841de367654ab85a917279544eae
/usr/lib/.build-id/33
/usr/lib/.build-id/33/b4f714be5c7263f95fecefca2dd38310698abe
/usr/lib/.build-id/3c
/usr/lib/.build-id/3c/57f6bbf6229fec7b31309f410cfa59d7beb437
/usr/lib/.build-id/40
/usr/lib/.build-id/40/9a5555811260c669ea0b31a058f8d30f4efb16
/usr/lib/.build-id/44
/usr/lib/.build-id/44/82b8a2fb5bccca1933b4b8fa880ca073101afe
/usr/lib/.build-id/46
/usr/lib/.build-id/46/82dfb2855b2eb003064b83670d826fbde6e81b
/usr/lib/.build-id/47
/usr/lib/.build-id/47/90d0a4ca19e94d3e78ad02eeb05bc4089e6516
/usr/lib/.build-id/47/d6829933e751e57b260bc4d97967a31c087627
/usr/lib/.build-id/4d
/usr/lib/.build-id/4d/31eee35b4eee0d8227a1dafa9fadc288664e02
/usr/lib/.build-id/4e
/usr/lib/.build-id/4e/cc3b0a86f73a81a3e3d5830e77b502bed91d31
/usr/lib/.build-id/5d
/usr/lib/.build-id/5d/ac50185e31b8abc7c6f16327c3672bf26d88e4
/usr/lib/.build-id/6f
/usr/lib/.build-id/6f/2c3669f8fdace052898056be49ab6c71204d38
/usr/lib/.build-id/71
/usr/lib/.build-id/71/feb118b050b1cc5f0877c1baa52c1b2334a04d
/usr/lib/.build-id/7e
/usr/lib/.build-id/7e/4b4db940f84e46030047474fa1f41aec479005
/usr/lib/.build-id/80
/usr/lib/.build-id/80/566468a3aff5645b767a5e33c01b23f5dafff1
/usr/lib/.build-id/81
/usr/lib/.build-id/81/465a1473bca6964e37b113a65a36ba8e36b127
/usr/lib/.build-id/85
/usr/lib/.build-id/85/9c4e8b5a76fc8634e47fb6e1a29daf8852ae80
/usr/lib/.build-id/8c
/usr/lib/.build-id/8c/e93602c48bc7741dc2bdd55e951c3410acf828
/usr/lib/.build-id/92
/usr/lib/.build-id/92/af0abffd118bcf996c2c4e481ec1c4c6755887
/usr/lib/.build-id/98
/usr/lib/.build-id/98/111fa7869cde6147379b588e1498956107c978
/usr/lib/.build-id/99
/usr/lib/.build-id/99/1d896e56841cdc26a4e298a131bd52567d8a0d
/usr/lib/.build-id/99/f16a0e66d86dc25ea303fbed84c35e4adc2183
/usr/lib/.build-id/9a
/usr/lib/.build-id/9a/b2090934eb1d9bd032bb94d9098619e5cd1442
/usr/lib/.build-id/a0
/usr/lib/.build-id/a0/2bfc59270525407437f5bf547729ba373ba177
/usr/lib/.build-id/a1/9445b256e54f196a3829aac58bf4f49139ea15
/usr/lib/.build-id/a5
/usr/lib/.build-id/a5/9c430c85514065863c75479fe59da1c94a06f5
/usr/lib/.build-id/a6
/usr/lib/.build-id/a6/c8a9ef59973e71c7a29615e08c4e1fdd5b70e4
/usr/lib/.build-id/a9
/usr/lib/.build-id/a9/4e72d1427370d03a8e109a63b6e6140ce0ab18
/usr/lib/.build-id/a9/58baafa7fe7f982ad021ce48ee35bde00d8563
/usr/lib/.build-id/b7
/usr/lib/.build-id/b7/130c3f36369abcd1d75842fc4ebbece80e03fa
/usr/lib/.build-id/b7/753b47f584a4983191b630d200a334074b682e
/usr/lib/.build-id/cc
/usr/lib/.build-id/cc/87a3e8c2f36c89c280d2692062aae3411a542e
/usr/lib/.build-id/cc/d75921ce1f4dd7ac4b3ac66ca1c1cf2c609474
/usr/lib/.build-id/d0
/usr/lib/.build-id/d0/067e264e038dbb9c4d3bbee4ca72dd12903e57
/usr/lib/.build-id/d7
/usr/lib/.build-id/d7/b5038105ded94b48755e280d81555617958a1a
/usr/lib/.build-id/d7/ba029b8a789fcca13d63bdda97756101892879
/usr/lib/.build-id/dd
/usr/lib/.build-id/dd/078cf99fab7a9691a9a1a101b21cfc5a2ad29d
/usr/lib/.build-id/de
/usr/lib/.build-id/de/7ae341fae7425fb1b8978b2449f6e50d205ac2
/usr/lib/.build-id/e0
/usr/lib/.build-id/e0/9cb5aceb9840b18587045be3cf8ee3d77b452d
/usr/lib/.build-id/e2
/usr/lib/.build-id/e2/ec917cfe902b2fe429a888116bbed6b52cfcca
/usr/lib/.build-id/e5
/usr/lib/.build-id/e5/fe58c64cd71b7a2fcd04abe029645073fd1cc0
/usr/lib/.build-id/ef
/usr/lib/.build-id/ef/f1f5c65d204ca96466a4e233456a6b91e2fd89
/usr/lib/.build-id/f1
/usr/lib/.build-id/f1/b465d2f347bd8337da0ee4312435d4da89ad82
/usr/lib/.build-id/f1/fb93f74645872fdd9e36870cd0848f5df2f62c
/usr/lib/.build-id/f3
/usr/lib/.build-id/f3/8547cd11777ed1603839ed0d10c25033f95ba7
/usr/lib/.build-id/f5
/usr/lib/.build-id/f5/4fa57dad5a3e13acc200e9b4a8b0f7cded62f1
/usr/lib/.build-id/fb
/usr/lib/.build-id/fb/6af65f1e7ad9b6654a40a58f904541c49d0dee
/usr/lib/.build-id/fe
/usr/lib/.build-id/fe/890bedf4a0381a9ab37a38af7a4c1704f06452
/usr/lib/.build-id/ff
/usr/lib/.build-id/ff/c16ecade55664771bf1e11541a0aaee5ad73ac
/usr/lib/.build-id/ff/c1ae2e0dbf80dc1715863264d7c328c106a93c
/usr/lib/systemd/system/mariadb.service
/usr/lib/systemd/system/mariadb.service.d
/usr/lib/systemd/system/mariadb.service.d/tokudb.conf
/usr/lib/systemd/system/mariadb@.service
/usr/lib/systemd/system/mariadb@bootstrap.service.d
/usr/lib/systemd/system/mariadb@bootstrap.service.d/use_galera_new_cluster.conf
/usr/lib/sysusers.d/mariadb.conf
/usr/lib/tmpfiles.d/mariadb.conf
/usr/lib64/mariadb
/usr/lib64/mariadb/INFO_BIN
/usr/lib64/mariadb/INFO_SRC
/usr/lib64/mariadb/plugin
/usr/lib64/mariadb/plugin/adt_null.so
/usr/lib64/mariadb/plugin/auth_0x0100.so
/usr/lib64/mariadb/plugin/auth_ed25519.so
/usr/lib64/mariadb/plugin/auth_gssapi.so
/usr/lib64/mariadb/plugin/auth_pam.so
/usr/lib64/mariadb/plugin/auth_socket.so
/usr/lib64/mariadb/plugin/auth_test_plugin.so
/usr/lib64/mariadb/plugin/client_ed25519.so
/usr/lib64/mariadb/plugin/daemon_example.ini
/usr/lib64/mariadb/plugin/debug_key_management.so
/usr/lib64/mariadb/plugin/dialog_examples.so
/usr/lib64/mariadb/plugin/disks.so
/usr/lib64/mariadb/plugin/example_key_management.so
/usr/lib64/mariadb/plugin/file_key_management.so
/usr/lib64/mariadb/plugin/ha_example.so
/usr/lib64/mariadb/plugin/ha_federated.so
/usr/lib64/mariadb/plugin/ha_mroonga.so
/usr/lib64/mariadb/plugin/ha_spider.so
/usr/lib64/mariadb/plugin/ha_test_sql_discovery.so
/usr/lib64/mariadb/plugin/handlersocket.so
/usr/lib64/mariadb/plugin/libdaemon_example.so
/usr/lib64/mariadb/plugin/locales.so
/usr/lib64/mariadb/plugin/metadata_lock_info.so
/usr/lib64/mariadb/plugin/mypluglib.so
/usr/lib64/mariadb/plugin/qa_auth_client.so
/usr/lib64/mariadb/plugin/qa_auth_interface.so
/usr/lib64/mariadb/plugin/qa_auth_server.so
/usr/lib64/mariadb/plugin/query_cache_info.so
/usr/lib64/mariadb/plugin/query_response_time.so
/usr/lib64/mariadb/plugin/semisync_master.so
/usr/lib64/mariadb/plugin/semisync_slave.so
/usr/lib64/mariadb/plugin/server_audit.so
/usr/lib64/mariadb/plugin/simple_password_check.so
/usr/lib64/mariadb/plugin/sql_errlog.so
/usr/lib64/mariadb/plugin/wsrep_info.so
/usr/libexec/mysql-check-socket
/usr/libexec/mysql-check-upgrade
/usr/libexec/mysql-prepare-db-dir
/usr/libexec/mysql-scripts-common
/usr/libexec/mysqld
/usr/share/doc/mariadb-server
/usr/share/doc/mariadb-server/README.mysql-cnf
/usr/share/groonga-normalizer-mysql/README.md
/usr/share/groonga-normalizer-mysql/lgpl-2.0.txt
/usr/share/groonga/COPYING
/usr/share/groonga/README.md
/usr/share/man/man1/aria_chk.1.gz
/usr/share/man/man1/aria_dump_log.1.gz
/usr/share/man/man1/aria_ftdump.1.gz
/usr/share/man/man1/aria_pack.1.gz
/usr/share/man/man1/aria_read_log.1.gz
/usr/share/man/man1/galera_new_cluster.1.gz
/usr/share/man/man1/galera_recovery.1.gz
/usr/share/man/man1/innochecksum.1.gz
/usr/share/man/man1/mariadb-service-convert.1.gz
/usr/share/man/man1/my_print_defaults.1.gz
/usr/share/man/man1/myisam_ftdump.1.gz
/usr/share/man/man1/myisamchk.1.gz
/usr/share/man/man1/myisamlog.1.gz
/usr/share/man/man1/myisampack.1.gz
/usr/share/man/man1/mysql.server.1.gz
/usr/share/man/man1/mysql_install_db.1.gz
/usr/share/man/man1/mysql_secure_installation.1.gz
/usr/share/man/man1/mysql_tzinfo_to_sql.1.gz
/usr/share/man/man1/mysqld_safe.1.gz
/usr/share/man/man1/mysqld_safe_helper.1.gz
/usr/share/man/man1/replace.1.gz
/usr/share/man/man1/resolve_stack_dump.1.gz
/usr/share/man/man1/resolveip.1.gz
/usr/share/man/man1/wsrep_sst_common.1.gz
/usr/share/man/man1/wsrep_sst_mysqldump.1.gz
/usr/share/man/man1/wsrep_sst_rsync.1.gz
/usr/share/man/man1/wsrep_sst_xtrabackup-v2.1.gz
/usr/share/man/man1/wsrep_sst_xtrabackup.1.gz
/usr/share/man/man8/mysqld.8.gz
/usr/share/mariadb/fill_help_tables.sql
/usr/share/mariadb/install_spider.sql
/usr/share/mariadb/maria_add_gis_sp.sql
/usr/share/mariadb/maria_add_gis_sp_bootstrap.sql
/usr/share/mariadb/mroonga/AUTHORS
/usr/share/mariadb/mroonga/COPYING
/usr/share/mariadb/mroonga/install.sql
/usr/share/mariadb/mroonga/uninstall.sql
/usr/share/mariadb/my-huge.cnf
/usr/share/mariadb/my-innodb-heavy-4G.cnf
/usr/share/mariadb/my-large.cnf
/usr/share/mariadb/my-medium.cnf
/usr/share/mariadb/my-small.cnf
/usr/share/mariadb/mysql_performance_tables.sql
/usr/share/mariadb/mysql_system_tables.sql
/usr/share/mariadb/mysql_system_tables_data.sql
/usr/share/mariadb/mysql_test_data_timezone.sql
/usr/share/mariadb/mysql_to_mariadb.sql
/usr/share/mariadb/policy
/usr/share/mariadb/policy/selinux
/usr/share/mariadb/policy/selinux/README
/usr/share/mariadb/policy/selinux/mariadb-server.fc
/usr/share/mariadb/policy/selinux/mariadb-server.te
/usr/share/mariadb/policy/selinux/mariadb.pp
/usr/share/mariadb/policy/selinux/mariadb.te
/usr/share/mariadb/systemd/mariadb.service
/usr/share/mariadb/systemd/mariadb@.service
/usr/share/mariadb/wsrep.cnf
/usr/share/mariadb/wsrep_notify
/var/lib/mysql
/var/log/mariadb
/var/log/mariadb/mariadb.log





Where Things go - Intro

Where things go when packages are installed?

Introduction


When we issue "yum install package-name", before we know the inside, these look magic.  With the magic "install" command, nice things happen without our understanding of "what just happened."  That's the purpose of package manager software such as yum, apt, brew, or even language specific pip.  Thanks to the open source developers' hard works and great contributions, we can just enjoy the magic they designed.
Sometimes, we wonder the details of what these package managers do.  Where do thing go after magic?  How these things available like magic after just one simple command?  Knowing about this is also useful sometimes.  For example, when libraries conflicted, or packages are installed, but libraries are not found, the details of packages will help to resolve the situations.
In summary, packages are composed of files, and package manager places them to be visible by convention or provided config.  The convention starts from old Unix convention.  This convention evolved while Linux has been modernized.  The conventions are not only for OS distro, but also languages set up their own.  Here Distro means the community packaging the OS.  For rexample, Fedora Linux and Ubuntu Linux are the two most popular Linux distro.  Python pip has certain rules to search libraries, for instance.   Each package manager will lay out package files differently, but they resemble each other.

This topic will be covered in multiple posts.  We will start with Unix executable paths and library paths.  Then, we will case study several package managers, and conclude with summary.

Wednesday, December 31, 2014

Maze Generating in C (like Lumosity Penguin Pursuit)

Playing lumosity is fun. Among one of their games, there is a cute maze game.
lumosity game
In that game, however, the goal is not about solving the maze, but about adjusting the direction when the screen flips or rotates.  The point is, generating this kind of maze has computer science theories.  Wikipedia has a great reference (Maze_generation_algorithm).  This fun algorithmic problem is implemented using C.  I used back-trace method, and here it is.
sample output



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

#define WIDTH   6
#define HEIGHT  6

struct node {
    int north_wall;
    int west_wall;
    int visited;
    int x;
    int y;
};

void printMaze(int cnt, struct node *cells)
{
    int y,x;
    for (y=0; y<HEIGHT; ++y) {
        for (x=0; x<WIDTH; ++x) {
            struct node *c = cells + ( x + y*WIDTH );
            printf("+");
            if (c->north_wall) {
                if (c->x == 0 && c->y == 0) 
                    printf("  ");
                else
                    printf("--");
            }
            else 
                printf("  ");
        }
        printf("+\n");

        for (x=0; x<WIDTH; ++x) {
            struct node *c = cells + (x + y*WIDTH) ;
            if (c->west_wall) 
                printf("|  ");
            else
                printf("   ");
        }
        printf("|\n");
    }
    
    for (x=0; x<WIDTH-1; ++x) {
        printf("+--");
    }
    printf("+  +\n\n");
}

// rtn is a pointer array.  NWES.
int neighbor(struct node *cells, struct node *cur, struct node **rtn)
{
    int x = cur->x;
    int y = cur->y;
    rtn[0] = rtn[1] = rtn[2] = rtn[3] = NULL;

    if (y-1 >= 0) rtn[0] = cells + (x + (y-1)*WIDTH);
    if (x-1 >= 0) rtn[1] = cells + ((x-1) + y*WIDTH);
    if (x+1 < WIDTH)  rtn[2] = cells + ((x+1) + y*WIDTH);
    if (y+1 < HEIGHT) rtn[3] = cells + (x + (y+1)*WIDTH);

    return rtn[0] != NULL || rtn[1] != NULL ||
           rtn[2] != NULL || rtn[3] != NULL;
}

void shuffle(struct node **array, size_t n) {    
    struct timeval tv;
    gettimeofday(&tv, NULL);
    int usec = tv.tv_usec;
    srand48(usec);

    if (n > 1) {
        size_t i;
        for (i = n - 1; i > 0; i--) {
            size_t j = (unsigned int) (drand48()*(i+1));
            struct node  *t = array[j];
            array[j] = array[i];
            array[i] = t;
        }
    }
}

void punchWall(struct node *node1, struct node *node2)
{
    int x1 = node1->x;
    int y1 = node1->y;
    int x2 = node2->x;
    int y2 = node2->y;

    if (x1 < x2 && y1 == y2)
        node2->west_wall =0;
    if (x2 < x1 && y1 == y2)
        node1->west_wall =0;

    if (y1 > y2 && x1 == x2)
        node1->north_wall =0;
    if (y2 > y1 && x1 == x2)
        node2->north_wall =0;
        
}

void genMaze(struct node *cells, struct node *cur)
{
    int i;
    if (cur->visited == 0) {
        struct node *nei[4];

        cur->visited = 1;
        if (neighbor( cells, cur, nei)) {
            shuffle(nei, 4);
            for (i=0; i<4; ++i) {
                if (nei[i] && nei[i]->visited==0) {
                    punchWall(cur, nei[i]);
                    genMaze(cells, nei[i]);
                }
            }
        }
    }
}

int main(int argc, char **argv) {
    int i;
    struct node cells[ WIDTH * HEIGHT ];

    // Initialize Cells
    for (i=0; i < WIDTH*HEIGHT; ++i) {
        cells[i].north_wall = cells[i].west_wall = 1;
        cells[i].visited = 0;
        cells[i].x = i % WIDTH;
        cells[i].y = i / WIDTH;
    }
    genMaze(cells, &cells[0]);
    printMaze(WIDTH * HEIGHT, cells);
    return 0;
}


Thursday, December 25, 2014

Quick Example of Red Black Tree.

In previous articles, FreeBSD AVL tree is ported to Linux and a usage example is presented.
Linux uses red-black tree instead of AVL.  Just searching for rbtree.h in Linux kernel returned so many components such as ext4.  But, rbtree can't be used in user space in kernel source form.  Luckily there is user-space ported rbtree in here.

That code contains a test code.  Here, I post one more example.  My example is the same test written in AVL test code (here).

By the way, using these codes have advantage of efficiency.
Enjoy.



#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include "rbtree.h"
#include "rbtree_test.h"


void printTree(RBRootType *root)
{
 int count = 0;
 Person *data, *rootdata;
 RBNodeType *cur;

 rootdata = container_of( root->rb_node, Person, node);
 printf("Root node: %s\n", rootdata->name);
 
 cur = rb_first(root);
 while (cur) {
  data = container_of( cur, Person, node);
  printf("%d : %s(%s)\n", count, data->name, data->phone);
  cur = rb_next(cur);
  count++;
 }
 printf("Total nodes in tree: %d\n", count);
 printf("---------------------------------------------------------------------\n");

}

Person* searchPerson(RBRootType *root, char *name)
{
 RBNodeType *curnode = root->rb_node;
 while (curnode) {
  Person *data = container_of(curnode, Person, node);
  int result;

  result = strcmp(name, data->name);

  if (result < 0)
   curnode = curnode->rb_left;
  else if (result > 0)
   curnode = curnode->rb_right;
  else
   return data;
 }
 return NULL;
}

int insertPerson(RBRootType *root, Person *data)
{
 RBNodeType **new = &(root->rb_node), *parent = NULL;
 while (*new) {
  Person *cur = container_of(*new, Person, node);
  int result = strcmp(data->name, cur->name);
  
  parent = *new;
  if (result < 0)
   new = &((*new)->rb_left);
  else if (result > 0)
   new = &((*new)->rb_right);
  else 
   return 0;
 }
 
 // New node
 rb_link_node(&(data->node), parent, new);
 rb_insert_color(&(data->node), root);

 return 1;
}


int main(int argc, char **argv)
{
 RBRootType mytree = RB_ROOT;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 insertPerson(&mytree, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 insertPerson(&mytree, &b);
 
 
 Person *srch = NULL;
 printTree(&mytree);
 
 if ( (srch = searchPerson(&mytree, "Micheal Smith")) != NULL ) 
  printf("Micheal found: %s\n", srch->phone);
 else
  printf("Micheal not found.\n");

 if ( (srch = searchPerson(&mytree, "Jack Stuart")) != NULL ) 
  printf("Jack found: %s\n", srch->phone);
 else
  printf("Jack not found.\n");
 printf("--------------------------------------------------\n");
 
 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 insertPerson(&mytree, &c);

 //traverse!!  root must be Jack.
 printTree(&mytree);

 
 return 0;
}

Monday, December 8, 2014

Sample Usage of AVL, quick and dirty.

So, previous article ported FreeBSD AVL into Linux AVL. (AVL Tree in C )
Here is quick and dirty way of how to use it.
It will be straightforward, except one thing.

Your data struct must be divided into two pieces.  Data part and avl_node_t part.  The Data part size must be multiple of 8.  If not, there will be a puzzling assert((offset & 0x7) == 0).  Here is the usage.  For convinience, I put the link part the first.  This will easy to cast type between (avl_node_t) and (struct person) with the same pointer.


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <stdint.h>
#include "avl.h"

#define NAME_LEN 36
#define PHONE_LEN 10

// assuming dtype has a link member as node type (avl_node_t)
#define OFFSETOF(data) 0

typedef struct person {
 avl_node_t  my_link; 
 char name[ NAME_LEN + 1];
 char phone[ PHONE_LEN + 1];
} Person;

int comparePerson(const void *a, const void *b) 
{
 Person *_a = (Person *)a;
 Person *_b = (Person *)b;
 if ( strncmp(_a->name, _b->name, NAME_LEN) < 0 )
  return -1;
 else if ( strncmp(_a->name, _b->name, NAME_LEN) > 0 )
  return 1;
 return 0;
}

Person* searchByName(avl_tree_t *tree, const char *name)
{
 Person *cur = AVL_NODE2DATA(tree->avl_root, tree->avl_offset);
 avl_node_t *p;
 while (cur) {
  if (strcmp(cur->name, name) == 0)
   return cur;
  else if (strcmp(name, cur->name) <0) {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[0];
  }
  else {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[1];
  }
  cur = p ? AVL_NODE2DATA( p, tree->avl_offset) : NULL;
 }
 return NULL;
}

void printTree(avl_tree_t *tree)
{
 int i = 0;
 Person *cur;

 printf("Total nodes in tree: %ld\n", avl_numnodes(tree));
 printf("Root: %s\n", ((Person *)(AVL_NODE2DATA( tree->avl_root, tree->avl_offset)))->name);

 cur = avl_first(tree);
 while (cur) {
  printf("%d : %s(%s)\n", i, cur->name, cur->phone);
  cur = AVL_NEXT(tree, cur);
  i++;
 }
 printf("---------------------------------------------------------------------\n");
}

int main(int argc, char **argv)
{
 avl_tree_t avl;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 avl_create(&avl, comparePerson, sizeof(Person), OFFSETOF(&a));
 avl_add(&avl, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 avl_add(&avl, &b);

 //traverse 
 printTree(&avl);

 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 avl_add(&avl, &c);

 //traverse!!  root must be Jack.
 printTree(&avl);

 // Searching.
 Person *search;
 search = searchByName(&avl, "Jack Stuart");
 if (search) 
  printf("Jack found: %s\n", search->name);
 else
  printf("Jack not found\n");

 search = searchByName(&avl, "lalalalala");
 if (search)
  printf("lala found:\n");
 else
  printf("lala not found\n");

 return 0;
}

AVL Tree in C

I ported FreeBSD avl implementation into Linux users pace version.
Code is here(github link).

Practically speaking, we don't need AVL tree these days in high level languages like Python.  There are good alternatives in general.  In algorithm perspective, there is a Red Black Tree, the rival of AVL tree.  They mostly serve for the similar purpose.  RBTree is easier to implement, but size is factor of 2 vs. AVL is 1.4.  Linux uses RBTree internally, and FreeBSD had AVL.  (Linux RBTree article)

Well, in day to day life, modern languages provide their own version of "List".  In Python case, we just stuff data into the list, and later call it by index.  For efficient search, we use bisect module.  If we need sort, Python list takes very "Intelligent" approach to be efficient.  I will discuss this later, but listsort.txt in Python source can be referenced.

But, then, why bother AVL tree?
First, it's mentioned more in different algorithm books probably thanks to BST (Binary Search Tree).  And, AVL is a good subject to introduce concepts of algorithm, "let's cover the weakness of a given algorithm."  Second, it's personal.  I just like it with no reason.

When I searched AVL written in C, I found many pages.  First, GNU libavl is an overkill.  Other small projects are not mature enough.  Either it's "not generic", or data allocation logic is "malloc".  This will cost performance.  Modern days, C is chosen by performance in many cases.  So, too many or individual malloc is a bigger penalty.

Interestingly, FreeBSD has avl implementation and they still include it even today.  Probably, former SunOS used avl for kernel data.  This is small.  This only implements AVL algorithm, but comparator is a function pointer which I can attach.  AVL node does not bother the data, but my data suppose to embed avl_node_t.  And, AVL algorithm doesn't do high-level search.  So, I have to provide the high level search, like searchByName(const char *key).  I liked the design  because it is more flexible.  Unfortunately, it's not directly usable in Linux.  So, I tweaked and made it usable in Linux.  There are two files (avl.h and avl.c).  Enjoy.


Friday, December 27, 2013