10+ Years in /dev/null

Except for 2 recent posts (8 years ago) to help my friend understand Linux, it's been over 10 years since I wrote my last blog posts.

During the recent 10+ years, many dramatic things happened. I would say, my life wasn't normal. Let's just say things have been dramatic, but I'm getting through it.

One lucky thing is, I am still in the software industry, doing my favorite things as my job. This is a blessing.

And suddenly I thought of my blog, and don't want to abandon it. This place will be my somewhat write-only space. :)

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.

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

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

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.

Bach, again.

My youtube #12,

Pushing scale practice doesn't help improvising.

I used to have this problem in my first year playing guitar.  My first ultimate goal was "Far beyond the sun" by Yngwie Malmsteen.  Pretty ambitious for a beginner.  Accomplishing song by song, picking speed went up, left finger maneuver became fluent.  However, Yngwie Malmsteen style is pretty challenging.  If I remember that time, I practiced different scales in metronome.  One day, I could play "far beyond the sun."  However, the speed I play for Yngwie Malmsteen didn't help other songs.  I was puzzled.

Big Question. "I could cover fastest genre of the music, but other than his music, I am still struggling with other pieces.  Why? "

Having 10 years of gap without playing guitar, I can't play Yngwie Malmsteen as I did.  But, I can enjoy more music than back then I used to play.  Here is my answer about the question.

Improvising has two modes.  "Controlled progression" and "Shredding".  Controlled progression relies on current musical context.  What is the key signature/main scale?  What is the beat signature/and main rhythm? More importantly, controlled progression much relies on the brain, the most important tool for music.  Muscle movement works together with the brain.  Do you see that the limiter is "the brain"?
On the other hand, shredding depends less on the brain.  It heavily relies on muscle memory.  Brain just sets up basic information like "what code/what sclae" and "what major beat", then finger works all.  In here, detail is less important, such as order of notes  as long as notes are in scale, and diatonically working.

When playing in band, these come out somewhat mixed.  For example, Yngwie Malmsteen, many phrases are roughly 20% controlled, 80% shredded.  So, brain tells "From now, 4 measures will be diminished rooted 20th fret C down."  Then, during 4 measures fingers improvise without help of brain.  In the meanwhile, brain accepts the next phase, "stop at 8th C vibration, for the 4 beats, and then the last half beat will Bm harmonic minor in pulling manner."  After executing 4 measure, this should end at C, and pulling Bm harmonic scale comes up.  Sure while this finger is working, Brain just thinks the next, not the one fingers are playing.

When in shredding mode, accidentals are not common.  Because accidental is a big brain work.  "We make irregular note X, which is not in scale, but produces effects of A,B,C, and some alpha of tention.  It will be resolved by in scale tonic Y or 5th of Y, etc. "  These need lots of controlled work.  Fingers can't just dance on their own.  They will pay attention to the brain.

Now the key point here.  Increasing maneuverability in controlled work is the foundation to play variety of music.  At the same time, brain should have more tools to provide good signals to the fingers.  I will explain this further.
Here is a simple test how fast I can maneuver in controlled.
Simply pentatonic through 6 strings.(Low A(5th fret 6th string) to high C(8th fret 1st string).  Try beginning with down picking. Change the same play with beginning with up picking.  This is one example of controlled picking.
There are different patterns of controls like 3rd down (C-A, B-G, A-F, G-E, F-D, .... ), alternate/3 string sweep, etc.
If these maneuver is fluent, many things will be easier.  Plus, shredding speed will also increase.

At the same time, don't forget to listen to more good musics.  And catch ideas from the music.  Eventually, collection of these ideas will make brain lucrative to utilize, and improvising will be cool and sound.

Guitarists...

So, my favorite instrument is the guitar.  Practically, I only can play the guitar.  Many great musicians inspires me, but due to my limited time, when I get a chance to play it, I have to concentrate for just one thing.

Anyway, my favorite guitarist is "Jason Becker."  He is the god and the most fluent guitarist.  At the same time, he had many brilliant ideas.  Considering all of his work, which ended at his age of 29, he didn't have his best time, unfortunately.

Then, my favorite "active" guitarist is "Guthrie Govan".  He is very special, to tell the truth.  Most of guitarists have own color, specializing handful of genre, Guthrie doesn't have specialty.  He is really all-rounder.  Rock, Blues, Jazz (Classic, Beebop, fusion, plus some brilliant covers with different colors), and Country.  Picking, finger style, slap, tapping, arpegio, ...  He also plays very good acoustic.  His theory is very strong.

I recommend his videos in youtube.  None have disappointed me, so far.

Virtual Fighter 4 title music

My youtube #11.

My youtube #10.

Time What is Time - Blind Guardian.

Audacity slow-down calculator

*Note: this article is out-dated.  Or, no-worth.  I found that audacity fixed noise problem with tempo change.

If you play music, audacity is an essential tool for many useful things.  Copying music, Ear training, etc.  When slowing down original source using "change tempo", annoying noise mixes with proper output.   I walk two step to avoid noise.  "change speed" and "change pitch".

How much parameter to give to slowdown but no noise, no pitch change is calculated.

#!/usr/bin/env python

import os

import sys

a = raw_input("slow down percent (50% half speed): ")

target_speed = float(a)

target_pitch = ( 100.0 - target_speed ) / target_speed * 100

print "target pitch change: %2.2f" % target_pitch

About Enthusiasm

I read a Korean article (http://wangsy.com/blog/2012/10/passion/), and One made me think for a while is this:

요즘 드는 또 다른 생각이 열정이란 만들어 내는 것도, 지켜내는 것도 아닌 주어지는 것 같습니다. 마치 천부적 재능이, 말 그대로 주어진 것이듯 ,열정도 주어지는 것인 것 같습니다. 뭔가 매우 비관적이고 운명론적 사고관이지만, 요즘 드는 생각이 그렇습니다. 열정을 가져 보아라, 열정이 꺼지지 않도록 잘 지켜라는 조언은 천부적 재능을 받아 보아라, 왜 예쁘게 태어나지 않았니 라고 하는 것과 같은 부질없는 이야기 인 것 같습니다.

It's very difficult to argue or practically apply this sentence.  But, I want to say that the author is so brave to tell this, because this is hard to say or hard to find an answer in practical world.  After a while, I somewhat agreed.

Software Design, or not?

During my career, I saw many people who write good pieces of software.  My goal has always been pursuing this.  To write a good software like these people.  But, here is an interesting thing to bring up.

So many of great software developers don't prepare separate time for designing!

In my case, I need time to design what I will write.  My design process is roughly like this:

1. Gather requirements.  And list what should happen.

2. Divide out inputs and outputs.  This eventually determines "interface".

3. Organize internal or intermediate data that I will handle in my system.  And see if I have to store anything.  (Store in memory for session, or store in DB for persistence).  These will contribute a lot to concrete functions or classes.  And key to the solutions.

Yep.. No UML, but my own way of listing and diagrams to represent. And this takes time.  So much time, actually.

I saw, and I am working with many great and smart developers.  And I know they write close to flawless codes in a shot.  My conclusion is "They also design, but they all do in their brain.  Therefore, design process is fast, and sometimes it looks missing from outside."  To be thorough, I need to check one by one through paper.  So, I am solving problem case by case.  This is inefficient, but so far this brings out my best quality.  I wish I could do these check step in brain so that I can produce software faster.
The key skill here is "memory", which is very hard to improve.

Passing by a bird

On the way to work this morning, I was driving my truck on 400 south at 60 mph.  I saw a bird from a distance.  He was flying -- entering low to cross the road from the right.  This bird, interestingly, tried to turn the direction, right in front of my lane.  While approaching to him(or her?), I recognized that it was an eagle by his slow but strong wing flap.  Since he just began to take off, he couldn’t fly high enough to clear height of my truck.  Initially, I wasn’t bothered slowing down because birds are quick to fly away.  But, the eagle seemed to stay still in front of me trying to turn around.  I put on a break a little bit and paid big attention to the distance to him.  After my second slow down for the elevated alerting level, the eagle finally finished turning.
When we were close, the eagle made a big wing-flap.  I saw him very close through the top right corner of my front windshield.  He missed me.  Although, it was an alerting situation, his final wing flap (flying away) looked beautiful.  He made total of 4 or 5 strong flaps during this incident, but 60 mph was a fast speed for natural creatures.  I felt so relieved that I didn’t harm this beautiful bird.

Several drafts...

I decided to use blog more to improve my writing skill.
Still writing a blog post is a hard thing.  I read somewhere to encourage blog posting saying "Invest a little more time writing facebook/twitter to write a blog post." (translated from Korean)

So, here I am.
My method to accomplish this was to use draft.  I write freely and save as draft.
I review my drafts and edits until I am satisfied to publish one.

The reality is only having several drafts so far.  Not one makes me happy to publish.
The trend will be only having more drafts, but very few will be published.  :)
I really envy people who write fluently and describe one's thought on writing.

my youtube #7

Back to Gentoo for one of my guest

Confessing that I gave up FreeBSD, but came back to Gentoo.
But not for my desktop.  My desktop is Windows 7, although I don't like this.
Running Gentoo as a guest with Enlightenment windows manager.

Feel home!

Experience with FreeBSD

I use Windows Vista on my laptop, but I miss Linux a lot.

Maybe I am not the only one to see these days problems of popular Linux distros.  "Bloated."

My best featured machine is 5-year-old Dell Inspiron 1521 (AMD, 2G mem, 120G disk).  This barely runs modern FC15 without visual effects.  My choice of Desktop, KDE turned down my love with their broken nepomuk indexer.  

I feel like, my laptop is ruled out.  When I found myself disabling default stuffs just to make my user experience not terrible, a question came up.  Aren't there any other distro for small boxes?

Well, there are DamnSmallLinux.  But that's not a major distro.

How about Gentoo?  I used to be a big fan of Gentoo, but now I don't like compiling unless I have to do so.  If Gentoo supports binary packages a little better, that will be the perfect distro.

Then, FreeBSD came.

   1. FreeBSD is a major distro, and actually a traditional unix than Linux.

   2. FreeBSD supports not only source compilation, but also does binary packages.  Very strong and convenient.

   3. If the software works on both FreeBSD and Linux, then most likely its compatibility level is very high already.

However, I just realized that #3 is self-torturing, too much.  

I was about to develop my own patch for screen-4.0.3 on FreeBSD, I ran into a different issue.

Complaint of "sys/stropts.h".

I didn't know what that header file supposed to be... But, well, elite programmers like screen developers use this, and there should be a reason to be used.  So, I searched and learned about how FreeBSD organize compatibility header files.  But, when I looked at binary patch file, disappointed a little bit.

 

--- process.c
+++ process.c
@@ -37,7 +37,7 @@
 #include "config.h"
 
 /* for solaris 2.1, Unixware (SVR4.2) and possibly others: */
-#ifdef SVR4
+#if defined(SVR4) && !defined(__FreeBSD__)
 # include sys stropts.h
 #endif
 




This happens three times in different files.  

In other words, FreeBSD doesn't use this header.  Reading a little more from stackoverflow, surely this is for Sun.  Main source tree not having this patch means, FreeBSD isn't major enough, and I will run into this situations in the future..  This is self-torturing.  

Fine!  Close to 10 years of Development life won't give up this obstacle.  It's tedious, but not difficult.  So, I prepared seperate header directory from /usr/src/sys/compat/svr4/, and renamed its contents.  (svr4_ was prefixed, DAMN!!).  Modified Makefile and compiled.  The next "make" command passed "sys/stropts.h", but another complaint.

utmp.c:731: error: 'struct utmpx' has no member named 'ut_xtime'




struct is difined differently??  From BSD and Linux??

And again, from binary patch file (patch-os.c, patch-utmp.c) read about how to work around utmp problem (the patch was describing how to replace some sections of code, not just lines), I realized that "ENOUGH!!!"  Having compatibility by paying this torturing is costly.  I accepted that "FreeBSD isn't popular enough."

Now, I am not sure if I want to try out Arch Linux.