A wide character trie implementation

It’s been a long time since I posted here. Therefore I decided to dig out some quick and straightforward stuffs from my disk which I previously decided should’t be in this blog.

I have posted multiple trie and dictionary search based programs in C, C++ and Perl before Jumble Work Solver and Jumble Work Solver Again. This time (again!) it’s about a trie. Although this time there was a specific requirement from a group who needed to implement a trie based word distance counting for bangla language, therefore Unicode support. This was supposed to be modified more and plugged into a spelling correction for scanned OCR text in the Bengali language.

Initially I suggested that a ternary tree would be more appropriate as the memory cost for standard trie (not compressed) would be huge. Although, finally the decision was to go with plain and simple trie. I know it is mad, but this is what it is :D.

Also, before going into the implementation, I should note that there is an efficient implementation of Radix Tree present in libcprops library. Though which we won’t be using for this one. I would recommend you people to have a look into this library if you already haven’t seen it yet.

Let’s say, we have a word “hello” and a node with an array of pointers of length 26 representing each character of the English language, each of which indicates that if the ith character follows the character represented by this node. Therefore for this example “hello”, the head node’s array of pointers will have the location 7 pointing to another node, which will have the 4th location of the pointer pointing to another node, whose pointer array’s 11 th location will point to another node and so on. Note here the indexing starts from zero. When the word ends, then the next pointer can be pointed to a special terminal marker node, which can be common to all, and the node is marked as a terminal node. This is essential as a valid word can be a substring of another valid word, in which case the shorter would need to be decided. When another new word like “help” comes in, we will follow the same path upto “hel” created by the word “hello”, and as we find there are no pointer for “p” pointing to any node, a new node will be created as explained before. Continue reading “A wide character trie implementation”

An overview of the PC Real Time Clock (RTC)

Introduction

Have you ever thought how the computer is able to display the correct time after you power on the system? There is a component called the RTC in the computer which stores this date and time information when the computer is turned off.

I will talk about how to read/write the date and time and use other features of the RTC using command-line tools, Linux RTC driver and also a low level direct access to the RTC internal registers.
Continue reading “An overview of the PC Real Time Clock (RTC)”

Generate the process tree of a Linux system

This is a quick post on how to generate a process tree Linux (and *nix) operating systems.

The idea is the same, as in the previous posts: Finding overall and per core CPU utilization and Find process IDs of a running process by name. Read the information present in the /proc/ directory. To get which processes are running we can read the directories with numbers as their names in the /proc/ directory. To generate a process tree we need to establish a process child relationship within the running processes. Each process has a parent (the first generated process is an exception), and it is stored in the process table entry of that process. We need to fetch the parent process id for each running process inorder to establish the tree. Here’s the plan. Continue reading “Generate the process tree of a Linux system”

Find process IDs of a running process by name

In this post I will talk about a procedure to find the process IDs of a running process by name, which can then be used to send signals or do other stuffs. For example if you have multiple instances of bash opened, this should be able to get you the list of process IDs (PIDs) of the bash instances.

Firstly, a shell utility is already available called pidof which is a part of the sysvinit-tools package. There are a whole bunch of tools in this package which lets you query PID based on different requirements, send signals to set of processes, etc. Just check out the stuff.

I will only mention the outline of how this is done and post the sourcecodes to do it. After that this can be extended to have many features just like the tools of sysvinit-tools package or more.
Continue reading “Find process IDs of a running process by name”

Finding overall and per core CPU utilization

Today I will post about how to monitor CPU usage by processor in Linux. As you might have expected this will simply access the CPU time information from /proc pseudo-filesystem and report the results.

The proc filesystem or the Procfs is a special filesystem which gives you a view into the kernel data. No files in procfs exists actually in the disk. There is no disk inodes and thus storage related to the files. Instead of going into procfs I will redirect you to wikipedia: http://en.wikipedia.org/wiki/Procfs. Let’s get in.
Continue reading “Finding overall and per core CPU utilization”

Change Useragent in Firefox

Firefox LogoThere are some websites which require you to visit them using Internet Explorer only, I don’t know why but there are some. My friend had to download an important document from a site which insisted on using Internet Explorer. We both are in Linux, Fedora. Is there a way? Yes there is. The browser version and certain system details are stored in the browser configuration, and this sting is called the useragent string. The information in this string is used to detect what browser you are using. Therefore if we can modify this string such that it looks like we are using Internet Explorer instead of Firefox, then we can fool the other end. After doing this the server side will believe that you are using an InternetExplorer browser or any other browser (also a different OS), depending on what the useragent string you are using to override the original.

What we need to do is simple. Just create a new entry in firefox browser configuration and set the value to appropriate useragent string. So let’s get started with this short and quick guide.
Continue reading “Change Useragent in Firefox”

Fix dark video in Skype for Linux

fedora_logoI was very much disappointed when i installed Skype in Fedora, three causes which are as follows in the order. First, Skype for Linux is very old version (2.2 beta) than the Windows Skype, second, the video was too dark or black, and third cause surfaced after i installed Fedora 16 x86_64, no 64 bit binary for Fedora was available. The third one was solved as described in this post: Running Skype for Fedora x86 in Fedora x86_64. For the first one i can’t do anything, but there should be some solution for the second problem: dark video. Cheese (a video capture application) works fine and video is good. Searching in the skype forums got a lot of mumbo jumbo solutions of which none worked. After a lot of search i got a very simple solution.

Edit (16.06.2012): The first problem seems to solve atleast upto some extent as Skype 4.0 is now out and can be downloaded here.

Continue reading “Fix dark video in Skype for Linux”

Simple script to restart services automatically when stopped in Fedora/Redhat

fedora_logoWhen occasionally the services like Apache or MySQL or other rc.d script crashes and stops working, then instead of restarting them manually, it may be more desirable to restart them automatically. A friend of mine asked about such an issue and here is the quick fix bash script fix.

Continue reading “Simple script to restart services automatically when stopped in Fedora/Redhat”

Running Skype for Fedora x86 in Fedora x86_64

fedora_logoAfter I installed Fedora 16 x86_64, i needed to install manually Skype for linux, which is available from This link, as it is not in Fedora repositories. After clicking the Skype icon from the kickstart menu, the Skype icon kept bouncing. Skype for linux is not available for 64 bit fedora (till now), and therefore requires 32 bit libraries to run. Problems …

Continue reading “Running Skype for Fedora x86 in Fedora x86_64”