Dealing with an “insufficient storage available” error message on sgs II smartphone

My Samsung Galaxy S II phone has terrified me to the death pulling out for almost any application update an error message like “Insufficient storage available”
Luckily for me I have found a way to get rid of this, by applying the following procedure:

  • Open the Phone application and switch to Keypad
  • Dial *#9900# This will lead you to the SysDump application
  • On the screen that appears, click on the button labelled “Delete dumpstate/logcat” (which should be the second item in the list)

By doing this I was able to get back more than one gigabyte of system storage!
Looks like some smartphone models are in a heavy need of a logrotate application:)

Python dependency conflict with gnome-music-3.10

If it happens to you that you hit the following dependency conflict with different python versions involved, like:

 # emerge -a1v gnome-music

These are the packages that would be merged, in order:

Calculating dependencies -

!!! Problem resolving dependencies for media-sound/gnome-music
... done!

!!! The ebuild selected to satisfy "gnome-music" has unmet requirements.
- media-sound/gnome-music-3.10.1::gentoo USE="" PYTHON_SINGLE_TARGET="-python3_2 -python3_3" PYTHON_TARGETS="python3_3 -python3_2"

  The following REQUIRED_USE flag constraints are unsatisfied:
    exactly-one-of ( python_single_target_python3_2 python_single_target_python3_3 )

  The above constraints are a subset of the following complete expression:
    python_single_target_python3_2? ( python_targets_python3_2 ) python_single_target_python3_3? ( python_targets_python3_3 ) exactly-one-of ( python_single_target_python3_2 python_single_target_python3_3 )

while using the default python configuration:

$ emerge --info
Portage 2.2.7 (default/linux/amd64/13.0/desktop, gcc-4.8.2, glibc-2.17, 3.10.7-gentoo x86_64)
...
PYTHON_SINGLE_TARGET="python2_7" PYTHON_TARGETS="python2_7 python3_3"
...

then this conflict can be temporarily resolved by adding a python_single_target_python3_3 USE flag to the corresponding ebuild:

$ cat /etc/portage/package.use/gnome-3.10
...
media-sound/gnome-music python_single_target_python3_3
...

Dual graphic card configuration on Gentoo

Recently, I was experimenting with OpenGL 3.3 support on my intel GPU within the newly released mesa 10.0.2.

Vendor: ........... Intel Open Source Technology Center
Renderer: ......... Mesa DRI Intel(R) Ivybridge Mobile 
Version: .......... 3.3 (Core Profile) Mesa 10.0.2
GLSL version: ..... 3.30

Sadly, it turned out, that the rotating cube made of triangles I was playing with was not drawn correctly as you can observe on this video. It took me a lot of time to realize, that it could be not just an oversight from my side but as well an undiscovered yet issue in the driver which I was trying out. It was about time to recall that my laptop has a hybrid video card. So, I started to think about an opportunity to configure it as well, to be able to test my sample code on the second video card I have. And I did.

Vendor: ........... NVIDIA Corporation
Renderer: ......... GeForce GT 640M/PCIe/SSE2
Version: .......... 3.3.0 NVIDIA 331.38
GLSL version: ..... 3.30 NVIDIA via Cg compiler

Luckily for me, at the end if this story my sample code was running fine, all issues I have observed with the intel mesa driver went away. It does not for sure mean, that my code is written correctly, but at least it’s a good indication, that it could be the case.

So, if you have a hybrid video card, like I do, there is a good and well supported on Gentoo project named Bumblebee which allows you to launch any application using the mighty secondary video card, in my case it’s GeForce GT 640M/PCIe/SSE2. I decided to go with a proprietary nvidia-driver, and therefore added it to my video card’s list side by side with intel:

# cat /etc/portage/make.conf
...
VIDEO_CARDS="intel nvidia" 
...

Updated my system afterwards and finally emerged bumblebee.

# emerge -a1v bumblebee

Make sure that you add yourself to the bumblebee group:

# gpasswd -a <user> bumblebee

As I have mentioned earlier bumblebee is well supported on Gentoo, so nothing else were required. The default configuration this ebuild provide is quite good as well.

Afterwards you should be able to launch any application on the secondary video card you desire with:

$ optirun <your app>

If you hit an error while trying to launch it, similar to this one:

$ optirun glxgears -info
[ 2108.388910] [ERROR]The Bumblebee daemon has not been started yet or the socket path /var/run/bumblebee.socket was incorrect.
[ 2108.388931] [ERROR]Could not connect to bumblebee daemon - is it running?

then just make sure that you have started the bumblebeed service:

# systemctl start bumblebeed
# systemctl status bumblebeed
bumblebeed.service - Bumblebee C Daemon
   Loaded: loaded (/usr/lib64/systemd/system/bumblebeed.service; disabled)
   Active: active (running) since Fri 2014-01-24 15:13:05 CET; 4s ago
 Main PID: 1487 (bumblebeed)
   CGroup: /system.slice/bumblebeed.service
           └─1487 /usr/sbin/bumblebeed

Jan 24 15:13:05 pls systemd[1]: Starting Bumblebee C Daemon...
Jan 24 15:13:05 pls systemd[1]: Started Bumblebee C Daemon.
Jan 24 15:13:05 pls bumblebeed[1487]: [ 2264.079511] [INFO]/usr/sbin/bumblebeed 3.2.1 started

A non-recursive implementation of an in-order traversal of a binary search tree without a stack

In my spare time, I occasionally was reading a book: “Introduction to algorithms” written by Cordon et al. to refresh and extend my knowledge on this field. Reading a book on algorithms has a side affect on me, that sooner or later I end up playing around with algorithm’s code. This time I wanted to get a non-recursive traversal of a BST without using an auxiliary stack. While a recursive traversal of a BST is really trivial, a non-recursive one is not. At least not in my eyes.
First, this is a simple API which I decided to use for a BST:

template <class T> class btree;
 
template <class T> struct node
{
public:
  friend class btree<T>;
   
private:
  T *data;
  node *left;
  node *right;
};
 

template <class T> class btree
{
public:
  btree (std::function<int(const T&, const T&)> cmp);
  ~btree ();
...
  void foreach2 (std::function<void(T&)> func) const;
...
   
private:
  node<T> *root;
  std::function<int(const T&, const T&)> cmp;
...
};

So, as you can observe, there are two classes: a node and the btree itself. The constructor of a btree takes a compare function to be able to compare its elements while searching, for example. However, this post is actually dedicated to the foreach2 member function, which travels in-order through the whole BST and takes a function as a parameter to do some action with a node’s item.

Next, I try to introduce this algorithm step by step. This way to traverse a tree is not really efficient as it visits most of the nodes almost twice on one side, but on the other side it does not require any additional data structure to keep track how to return to the parent node. All in one, it’s a lot of fun:) Below you see the whole algorithm, and as you will find out, despite the fact that this code is really small, at first glance, it’s really hard to figure out, how it works and why it works at all. So, just scroll over.

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    if (i->left != nullptr) {
      node<T> *r = i->left;
 
      while (r->right != nullptr && r->right != i) {
        r = r->right;
      }
 
      if (r->right == nullptr) {
        r->right = i;
        i = i->left;
        continue;
      } else {
        r->right = nullptr;
      }
    }
 
    func (*i->data);
    i = i->right;
  }
}

So, let’s build it from scratch. Therefore, we consider a few simple cases of a BST. Suppose all node in our BST have no left nodes, so it has a form similar to this one:

//    A
//   / \
//      B
//     / \
//        C
//       / \

To traverse this BST and thus cover this case, the lines of code we come up with should be very simple:

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    ...
    func (*i->data);
    i = i->right;
  }
}

And it’s no wonder, because it’s just the code, which is used to go through the singly linked list. Therefore let’s consider another special case, in which all nodes have no right child.

//       A
//      / \
//     B
//    / \
//   C
//  / \

To be able to traverse this, we should first go to the bottom of the left subtree. Let us therefore add this part of the code:

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;
 
  while (i != nullptr) {
    if (i->left != nullptr) {
      ...
      i = i->left;
      continue;
      ...
    }
 
    func (*i->data);
    i = i->right;
  }
}

Once, we have arrived at the bottom we perform an operation on C’s data and bump we are stuck! At this point we should go backwards the tree. However, there is no way to go back and it’s too late already. Nevertheless, from the bottom position we can make an interesting observation: taking an arbitrary tree structure into account, all nodes at which we are going to stuck will have no right child set. Hence, at the beginning while moving down the left subtree, we should find a predecessor of the current node (in the sense of in-order traversal order) and temporarily adjust its right child to this node i.e. while visiting node A, we find its predecessor and it’s B, we set its right child temporarily to A and go one step down in the left subtree to B. For the node B we do absolutely the same thing.
Once we will arrive to the node A for the second time we should revert the temporary change by setting B’s right link to null pointer again, proceed with the data of node A and finally move to the right subtree. Remarkably, this is all what is required to be able to traverse a BST of any arbitrary structure.

Bellow you can find the entire example, in which a randomly build BST containing 50 items is constructed and traversed in-order afterwards, printing its items:

#include <functional>
#include <iostream>
#include <random>
#include <algorithm>

template <class T> class btree;

template <class T> struct node 
{
public:
  friend class btree<T>;
  
private:
  T *data;
  node *left;
  node *right;
};

template <class T> class btree
{
public:
  btree (std::function<int(const T&, const T&)> cmp);
  ~btree ();

  void insert (const T& data);
  void foreach (std::function<void(T&)> func) const;
  void foreach2 (std::function<void(T&)> func) const;
  int length () const;
  void remove (const T& data);
  
private:
  node<T> *root;
  std::function<int(const T&, const T&)> cmp;

  void foreach (node <T>* node, std::function<void(T&)> func) const;
  int length (node<T> *node, int len) const;
};

template <class T>
btree<T>::btree (std::function<int(const T&, const T&)> cmp)
{
  root = nullptr;
  this->cmp = cmp;
}

template <class T>
btree<T>::~btree ()
{
}

template <class T>
int btree<T>::length () const
{
  return length (root, 0);
}

template <class T>
int btree<T>::length (node<T> *node, int len) const
{
  if (node != NULL) {
    int l1, l2;
    l1 = length (node->left, len + 1);
    l2 = length (node->right, len + 1);

    return std::max (l1, l2);
  }
  
  return len;
}

template <class T>
void btree<T>::foreach (std::function<void(T&)> func) const
{
  foreach (root, func);
}

template <class T>
void btree<T>::foreach (node<T> *node, std::function<void(T&)> func) const
{
  if (node != NULL) {
    foreach (node->left, func);
    func (*node->data);
    foreach (node->right, func);
  }
}

template <class T>
void btree<T>::remove (const T& data)
{
  node<T> *i = root;
  node<T> *p = nullptr;
  node<T> *s = nullptr;
  int val;

  while (i != nullptr && (val = cmp (data, *i->data)) != 0) {
    p = i;
    if (val > 0) {
      i = i->right;
    } else {
      i = i->left;
    }
  }

  if (i == nullptr) return;

  if (i->left == nullptr) {
    s = i->right;
  } else if (i->right == nullptr) {
    s = i->left;
  } else {
    node<T> *b = i;
    s = i->right;

    while (s->left != nullptr) {
      b = s;
      s = s->left;
    }

    if (b->left == s) {
      b->left = s->right;
    } else {
      b->right = s->right;
    }

    s->left = i->left;
    s->right = i->right;
  }

  if (p == nullptr) {
    root = s;
  } else if (p->left == i) {
    p->left = s;
  } else {
    p->right = s;
  }
  
  delete i->data;
  delete i;
}

template <class T>
void btree<T>::foreach2 (std::function<void(T&)> func) const
{
  node<T> *i = root;

  while (i != nullptr) {
    if (i->left != nullptr) {
      node<T> *r = i->left;

      while (r->right != nullptr && r->right != i) {
        r = r->right;
      }

      if (r->right == nullptr) {
        r->right = i;
        i = i->left;
        continue;
      } else {
        r->right = nullptr;
      }
    }

    func (*i->data);
    i = i->right;
  }
}

template <class T>
void btree<T>::insert (const T& data)
{
  node<T> *n = new node<T>;
  n->data = new T (data);
  n->left = nullptr;
  n->right = nullptr;

  node<T> *i = root;
  node<T> *p = nullptr;

  while (i != nullptr) {
    p = i;
    if (cmp (*i->data, *n->data) >= 0) {
      i = i->left;
    } else {
      i = i->right;
    }
  }

  if (p == nullptr) {
    root = n;
  } else if (cmp (*p->data, *n->data) >= 0) {
      p->left = n;
  } else {
      p->right = n;
  }
}

int main ()
{
  std::random_device rd;
  std::uniform_int_distribution<int> dist (0, 1000);

  std::cout << "testing..." << std::endl;
  btree<int> bt([] (const int &a, const int &b) -> int { return (a - b); });
  int num;
  for (int i = 0; i < 50; i ++) {
    num = dist (rd);
    bt.insert (num);
  }

  bt.foreach ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;

  bt.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  std::cout << "length: " << bt.length () << std::endl;
  
  std::cout << "testing delete..." << std::endl;
  btree<int> bt2([] (const int &a, const int &b) -> int { return (a - b); });
  int vals[] = { 12, 20, 8, 10, 4, 3, 2, 1 };
  for (int i = 0; i < sizeof (vals)/sizeof (vals[0]); i++) {
    bt2.insert (vals[i]);
  }
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  bt2.remove (8);
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
  bt2.remove (12);
  bt2.foreach2 ([] (int& d) { std::cout << d << " "; });
  std::cout << std::endl;
}

It can be compiled with:

all:
	g++ inorder.cpp -o inorder --std=c++11 -O3

Reference: Threaded binary tree

Vala, OpenGL and Gtk+ sample code with shaders on Gnu/Linux

This is the follow up post for the discoveries which I was doing for myself to unify OpenGL support with Gtk+. Here, you can find a first post, I have shared towards this direction.
The content of the trivial shader program: vertex-shader.txt

#version 130

attribute vec4 vPosition;

void main () {
	gl_Position = vPosition;
}

Here,
fragment-shader.txt

#version 130

precision mediump float;
uniform vec4 vColor;

void main () {
	gl_FragColor = vColor;
}
using GL;

namespace Evg {
	public class Shader {
		private bool loaded;
		private uint type;
		private uint id;

		public Shader () {
			this.loaded = false;
			this.id = 0;
		}

		~Shader () {
			this.delete ();
		}

		public bool load_from_string (string shader, uint type) {
			this.id = glCreateShader (type);

			stdout.printf ("id is %u\n", id);

			glShaderSource (id, shader);
			glCompileShader (id);

			int status;
			glGetShaderiv (id, GL_COMPILE_STATUS, out status);

			if (status == GL_FALSE) {
				stdout.printf ("shader info log: '%s'\n", glGetShaderInfoLog (this.id));
				return false;
			}

			this.type = type;
			this.loaded = true;

			return true;
		}

		public bool load_from_file (string path, uint type) {
			File file = File.new_for_path (path);

			if (!file.query_exists ()) {
				stderr.printf ("File '%s' doesn't exist.\n", file.get_path ());
				return false;
			}

			try {
				DataInputStream dis = new DataInputStream (file.read ());
				StringBuilder sb = new StringBuilder ();
				string line;

				while ((line = dis.read_line ()) != null) {
					sb.append_printf ("%s\n", line);
				}

				return this.load_from_string (sb.str, type);
			} catch (Error e) {
				error ("%s", e.message);
			}
		}

		public bool is_loaded () {
			return this.loaded;
		}

		public uint get_id () {
			return this.id;
		}

		public void delete () {
			if (!this.loaded) return;
			this.loaded = false;
			glDeleteShader (this.id);
		}
	}
}
using GL;

namespace Evg {
	public class Program {
		private bool linked;
		private uint id;

		public Program () {
			this.id = 0;
			this.linked = false;
		}

		public uint get_id () {
			return this.id;
		}

		public bool create () {
			this.id = glCreateProgram ();
			return (this.id != 0);
		}

		public bool attach_shader (Evg.Shader shader) {
			if (!shader.is_loaded ())
				return false;

			glAttachShader (this.id, shader.get_id ());
			return true;
		}

		public bool is_linked () {
			return this.linked;
		}

		public bool is_created () {
			return (this.id != 0);
		}

		public bool link () {
			glLinkProgram (this.id);

			int status;
			glGetProgramiv (this.id, GL_LINK_STATUS, out status);
			this.linked = (status == GL_TRUE);

			if (!this.linked) {
				stdout.printf ("program info log: '%s'\n", glGetProgramInfoLog (this.id));
			}

			return this.linked;
		}

		public void use () {
			if (this.linked)
				glUseProgram (this.id);
		}

		public void delete () {
			if (!this.linked)
				return;

			this.linked = false;
			glDeleteProgram (this.id);
			this.id = 0;
		}

		~Program () {
			this.delete ();
		}
	}
}
using GLX;
using GL;

class GLXSample : Gtk.Window {

    private unowned X.Display xdisplay;
    private GLX.Context context;
    private GLX.XVisualInfo xvinfo;

	private Evg.Shader vertex_shader;
	private Evg.Shader fragment_shader;
	private Evg.Program program;
	private Triangle triangle;

    public GLXSample () {
        this.title = "OpenGL with GLX";
        this.set_reallocate_redraws (true);
        this.destroy.connect (Gtk.main_quit);

        int[] attrlist = {
            GLX_RGBA,
            GLX_RED_SIZE, 1,
            GLX_GREEN_SIZE, 1,
            GLX_BLUE_SIZE, 1,
            GLX_DOUBLEBUFFER, 0
        };

        this.xdisplay = Gdk.x11_get_default_xdisplay ();

        if (!glXQueryExtension (xdisplay, null, null)) {
            stderr.printf ("OpenGL not supported\n");
        }

        this.xvinfo = glXChooseVisual (xdisplay,
									   Gdk.x11_get_default_screen (),
									   attrlist );

        if (xvinfo == null) {
            stderr.printf ("Error configuring OpenGL\n");
        }

        var drawing_area = new Gtk.DrawingArea ();
        drawing_area.set_size_request (300, 300);
        drawing_area.set_double_buffered (false);

        this.context = glXCreateContext (xdisplay, xvinfo, null, true);

        drawing_area.configure_event.connect (on_configure_event);
		drawing_area.realize.connect (on_realize);
        drawing_area.draw.connect (on_draw);

        this.add (drawing_area);
    }

	private void on_realize (Gtk.Widget widget) {
		if (!glXMakeCurrent (xdisplay,
							 Gdk.X11Window.get_xid (widget.get_window ()),
							 context))
            return;

		stdout.printf ("Vendor: ........... %s\n", glGetString (GL_VENDOR));
		stdout.printf ("Renderer: ......... %s\n", glGetString (GL_RENDERER));
		stdout.printf ("Version: .......... %s\n", glGetString (GL_VERSION));
		stdout.printf ("GLSL version: ..... %s\n",
					   glGetString (GL_SHADING_LANGUAGE_VERSION));

		this.vertex_shader = new Evg.Shader ();

		stdout.printf ("loading vertex shader\n");
		vertex_shader.load_from_file ("vertex-shader.txt", GL_VERTEX_SHADER);
		stdout.printf ("vertex shader is loaded %s\n",
					   vertex_shader.is_loaded ().to_string ());

		this.fragment_shader = new Evg.Shader ();

		stdout.printf ("loading fragment shader\n");
		fragment_shader.load_from_file ("fragment-shader.txt", GL_FRAGMENT_SHADER);
		stdout.printf ("fragment shader is loaded %s\n",
					   fragment_shader.is_loaded ().to_string ());

		this.program = new Evg.Program ();
		this.program.create ();
		stdout.printf ("program is created %s\n", program.is_created ().to_string ());
		this.program.attach_shader (this.vertex_shader);
		this.program.attach_shader (this.fragment_shader);
		this.program.link ();
		this.program.use ();
		stdout.printf ("program is linked %s\n", program.is_linked ().to_string ());

		this.triangle = new Triangle (this.program.get_id ());
	}

    private bool on_configure_event (Gtk.Widget widget, Gdk.EventConfigure event) {
        if (!glXMakeCurrent (xdisplay,
							 Gdk.X11Window.get_xid (widget.get_window ()),
							 context))
            return false;

		int width = widget.get_allocated_width ();
		int height = widget.get_allocated_height ();
		int size = int.min (width, height);

		glViewport ((width - size) / 2, (height - size) / 2, size, size);

        return true;
    }

    private bool on_draw (Gtk.Widget widget, Cairo.Context cr) {
        if (!glXMakeCurrent (xdisplay,
							 Gdk.X11Window.get_xid (widget.get_window ()),
							 context))
            return false;

        glClear( GL_COLOR_BUFFER_BIT );

		this.triangle.draw ();

        glXSwapBuffers (xdisplay, Gdk.X11Window.get_xid (widget.get_window ()));

        return true;
    }
}

public class Triangle {
	private float[] color = { 0.63671875f, 0.76953125f, 0.22265625f, 1.0f };
	private float[] triangle_vertex = {
         0.0f,  0.622008459f, 0.0f,
        -0.5f, -0.311004243f, 0.0f,
         0.5f, -0.311004243f, 0.0f
    };

	private uint program_id;

	public Triangle (uint program_id) {
		this.program_id = program_id;
	}

	public void draw () {
		int position_id = glGetAttribLocation (this.program_id, "vPosition");
		glEnableVertexAttribArray (position_id);
		glVertexAttribPointer (position_id, 3, GL_FLOAT, false, 12, triangle_vertex);

		int color_id = glGetUniformLocation (this.program_id, "vColor");
		glUniform4fv(color_id, 1, color);

		glDrawArrays (GL_TRIANGLES, 0, 3);

		glDisableVertexAttribArray (position_id);
	}
}

void main (string[] args) {
    Gtk.init (ref args);

    var sample = new GLXSample ();
    sample.show_all ();

    Gtk.main ();
}

The content of the makefile:

all:
	valac-0.18 -o glx-test glx-test.vala evg-shader.vala evg-program.vala --vapidir ../vapi --pkg gl --pkg gl3 --pkg gio-2.0 --pkg gtk+-3.0 --pkg glx --pkg gdk-x11-3.0 #--ccode

Recursively defined lambda functions in C++11

A neat feature, which was introduced in since C++11 is the ability to define a lambda functions[1] in combination with delegates represented by std::function[2]. The following exemplary code snippet demonstrates how a recursive lambda function can be constructed this way:

#include <functional>
#include <iostream>

int main () {
  std::function<void(int)> count_down;

  count_down = [&count_down] (int num) -> void {
    if (num > 0) {
      std::cout << "i:" << num << std::endl;
      
      count_down (num - 1);
    }
  };

  count_down (6);
}

Using GCC, the above code can be compiled with:

$ g++ testcase.cpp -o testcase --std=c++11

[1] http://en.cppreference.com/w/cpp/language/lambda
[2] http://en.cppreference.com/w/cpp/utility/functional/function

Quickly applying patches on Gentoo

Sometimes, it’s necessary to apply a patch for a given package and there is no time and no desire to fork an ebuild to a custom overlay. Luckily Gentoo provides an easy way to so. All you need to do is to place a patch into the directory /etc/portage/patches/[category]/[ebuild's name]/new-fix.patch. Sadly, not all ebuilds in the portage tree has a build-in support for this feature and to be on the safe side you can put the following hook into the portage’s bashrc file:

# cat /etc/portage/bashrc 
post_src_prepare() {
    if type epatch_user &> /dev/null ; then
    	epatch_user
    fi
}

Reference: Gentoo wiki