41J Blog

Archive for March 2012

A quick and dirty BST implementation

March 18, 2012, 2:55 pm

Another quick and dirty algorithm implementation in C++. This time a Binary search tree (no balancing):


#include <iostream>
#include <vector>

using namespace std;

class Node {

public:

  int value;

  Node *less;
  Node *more;
};

class BinarySearchTree {

public:

  BinarySearchTree() : root(NULL) {}

  void find_node(int value,Node **findnode,Node **parent) {

    *findnode = NULL;
    *parent   = NULL;

    if(root == NULL) {
      return;
    }

    Node *current = root;
    for(;;) {
      if(current->value == value) {*findnode = current; return;}

      if(value < current->value) {
        if(current->less != NULL) {*parent = current; current = current->less;}
        else {
          return;
        }
      } else {
        if(current->more != NULL) {*parent = current; current = current->more;}
        else {
          return;
        }
      }
    }
  }
 
  Node *getr(Node *c,Node **parent) {
    *parent = c;
    for(;c->more != NULL;) {
      *parent = c;
      c = c->more;
    }
    return c;
  }

  void remove(int value) {
  
    Node *delnode;
    Node *parent;

    find_node(value,&delnode,&parent);

    if(delnode == NULL) return;

    // leaf
    if((delnode->less == NULL) && (delnode->more == NULL)) {
      if(parent->less == delnode) {parent->less = NULL;}
      if(parent->more == delnode) {parent->more = NULL;}
      delete delnode;
      return;
    }

    // only one child
    if((delnode->less == NULL) || (delnode->more == NULL)) {
      if(delnode->less != NULL) {
        if(parent->less == delnode) {parent->less = delnode->less;}
        if(parent->more == delnode) {parent->more = delnode->less;}
        delete delnode; 
        return;
      }

      if(delnode->more != NULL) {
        if(parent->less == delnode) {parent->less = delnode->more;}
        if(parent->more == delnode) {parent->more = delnode->more;}
        delete delnode;
        return;
      }
    }

    // two children
    Node *i = getr(delnode->less,&parent);

    delnode->value = i->value;
    if(parent == i)       { delnode->less = NULL;}
    if(parent->less == i) { parent->less = NULL; }
                     else { parent->more = NULL; }
    delete i;
  }

  void insert(int value) {

    if(root == NULL) {
      Node *n = new Node();
      n->value = value;
      n->less = NULL;
      n->more = NULL;
      root = n;

      return;
    }

    Node *current = root;
    for(;;) {
      if(value < current->value) {
        if(current->less != NULL) current = current->less;
        else {
          Node *n = new Node();
          n->value = value;
          n->less = NULL;
          n->more = NULL;
          current->less = n;
          break;
        }
      } else {
        if(current->more != NULL) current = current->more;
        else {
          Node *n = new Node();
          n->value = value;
          n->less = NULL;
          n->more = NULL;
          current->more = n;
          break;
        }
      }
    }
  }

  bool exists(int value) {
    if(root == NULL) {
      return false;
    }

    Node *current = root;
    for(;;) {
      if(current->value == value) return true;

      if(value < current->value) {
        if(current->less != NULL) current = current->less;
        else {
          return false;
        }
      } else {
        if(current->more != NULL) current = current->more;
        else {
          return false;
        }
      }
    }
  }

  Node *root;
};

int main() {

  BinarySearchTree s;

  vector<int> testdata;

  for(size_t n=0;n<10;n++) { testdata.push_back(rand()%20); }

  for(size_t n=0;n<10;n++) { s.insert(testdata[n]); }

  cout << "testdata: " << endl;
  for(size_t n=0;n<10;n++) { cout << testdata[n] << endl; }

  cout << "existance check: " << endl;
  for(size_t n=0;n<10;n++) { if(s.exists(testdata[n])) cout << "existance: " << testdata[n] << " true" << endl; else cout << "existance: " << testdata[n] << " false" << endl;}
  for(size_t n=0;n<10;n++) { if(s.exists(testdata[n]+20)) cout << "existance: " << testdata[n]+20 << " true" << endl; else cout << "existance: " << testdata[n]+20 << " false" << endl;}

  cout << "remove: " << testdata[5] << endl;
  s.remove(testdata[5]);
  if(s.exists(testdata[5])) cout << testdata[5] << " still exists" << endl; else cout << testdata[5] << " no longer exists" << endl;

  cout << "remove: " << testdata[3] << endl;
  s.remove(testdata[3]);
  if(s.exists(testdata[3])) cout << testdata[3] << " still exists" << endl; else cout << testdata[3] << " no longer exists" << endl;

  cout << "remove: " << testdata[0] << endl;
  s.remove(testdata[0]);
  if(s.exists(testdata[0])) cout << testdata[0] << " still exists" << endl; else cout << testdata[0] << " no longer exists" << endl;
}

Category: Uncategorized | Comment

Isilon /var full usage at 100% but few files

March 17, 2012, 2:50 pm

I had this problem last week. The /var filesystem was full, but contained few files. This in term seemed to kill cifs and the web interface, though nfs was fine.

Long story short, it’s probably snmpd, there’s a bug in a version of the isilon os (possibly fixed now).

You can use fstat to find abnormally large open files (unfortunately lsof isn’t present, so I couldn’t see a way to locate unlinked files) and the process that has them open. You can then kill -9 snmpd. After that you can restart services as follows:

isi services apache2 disable
Isi services apache2 enable
isi services cifs disable
isi services cifs enable

You may also need to kill off webui/smbd (killall -9 isi_webui_d).

Category: Uncategorized | Comment

Heap (maxheap) implementation

March 17, 2012, 12:05 am

A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree:

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

class Heap {

public:

  Heap() {
    store.push_back(0);
  }

  int l_child(int idx) {
    return idx*2;
  }

  int r_child(int idx) {
    return (idx*2)+1;
  }

  int get_parent(int idx) {
    return (idx/2);
  }

  void insert(int val) {
    store.push_back(val);

    int idx = store.size()-1;

    if(idx == 1) return;

    // bubble up
    for(;store[get_parent(idx)] < store[idx];) {
      int t = store[get_parent(idx)];
      store[get_parent(idx)] = val;
      store[idx] = t;
      idx = get_parent(idx);
      if(get_parent(idx) == 0) break;
    }
  }

  void dump() {
    cout << "DUMPSTART" << endl;
    for(size_t n=0;n<store.size();n++) {
      cout << store[n] << endl;
    }
    cout << "DUMPEND" << endl;
  }

  int pop() {
    int r = store[1];

    store[1] = store[store.size()-1];
    store.pop_back();

    bool min=true;
    int idx = 1;
    for(;min==true;) {

      min=false;

      int lidx = l_child(idx);
      int ridx = r_child(idx);
 
      int lval;
      int rval;
      if(lidx < store.size()) lval = store[lidx]; else lval = INT_MIN;
      if(ridx < store.size()) rval = store[ridx]; else rval = INT_MIN;

      if(store[idx] < lval) { min=true; }
      if(store[idx] < rval) { min=true; }

      if(!min) break;

      int t = store[idx];
      if(lval > rval) {
        store[idx] = store[l_child(idx)];
        store[l_child(idx)] = t;
        idx = l_child(idx);
      } else {
        store[idx] = store[r_child(idx)];
        store[r_child(idx)] = t;
        idx = r_child(idx);
      }
    }
    return r;
  }

  vector<int> store;
};

int main() {

  vector<int> testdata;

  for(size_t n=0;n<10;n++) testdata.push_back(rand()%20);

  Heap myheap;
  for(size_t n=0;n<testdata.size();n++) myheap.insert(testdata[n]);

  cout << "popping heap:" << endl;
  for(size_t n=0;n<testdata.size();n++) cout << myheap.pop() << endl;

  cout << "sorted testdata:" << endl;
  sort(testdata.rbegin(),testdata.rend());
  for(size_t n=0;n<testdata.size();n++) cout << testdata[n] << endl;
 
  cout << "second test: " << endl;
  Heap myheap2; 
  for(size_t n=0;n<testdata.size();n++) myheap2.insert(testdata[n]);
  for(size_t n=0;n<(testdata.size()/2);n++) cout << myheap2.pop() << endl;
  myheap2.insert(100);
  myheap2.insert(7);
  for(size_t n=0;n<(testdata.size()/2)+2;n++) cout << myheap2.pop() << endl;

}

Category: Uncategorized | Comment

A singly linked list with reverse…

March 15, 2012, 2:17 am

In (not particularly beautiful) C++, both recursive and non-recursive reverse methods:

#include <iostream>
using namespace std;

class ListItem {

public:

  ListItem() : next(NULL)
  {}

  char data[100];
  ListItem *next;

  void reverse(ListItem *p) {
    if(next == NULL) {
      next = p;
    } else {
      next->reverse(this);
      next = p;
    }
  }
};

class LinkedList {

public:

  LinkedList() {}

  ListItem *start;
  ListItem *end;

  ListItem *push_back(char *data) {
  

    ListItem *i = new ListItem();

    if(end != NULL) { end->next = i; }
               else { start = i; }

    for(size_t n=0;n<100;n++) {i->data[n] = data[n];}

    end = i;
    return i;
  }

  void reverse() {
    start->reverse(NULL);
    ListItem *temp = end;
    end = start;
    start = temp;
  }

  void reverse_nonrec() {
  
    ListItem *last=NULL;
    for(ListItem *p=start;p!=NULL;) {
      ListItem *next = p->next;

      p->next = last;
      last = p;
      p = next;
    }

    ListItem *temp = end;
    end = start;
    start = temp;
  }

  void dump() {
    for(ListItem *p=start;p!=NULL;p=p->next) {
      cout << "data: " << p->data << endl;
    }
  }

  ~LinkedList() {
    ListItem *op = NULL;
    for(ListItem *p=start;p!=NULL;p=p->next) {
      if(op != NULL) delete op;
      op = p;
    }
    if(op != NULL) delete op;
  }

};

int main() {

  LinkedList mylist;

  char tempdata[100];
  for(size_t n=0;n<100;n++) { tempdata[n] = 'A'; }
  tempdata[99] = 0;
  for(size_t n=0;n<20;n++) {
    mylist.push_back(tempdata);
    for(size_t n=0;n<99;n++) { tempdata[n]++; }
  }

  mylist.dump();
  mylist.reverse();

  cout << "Reversed List" << endl;
  mylist.dump();

  cout << "Reverse again" << endl;
  mylist.reverse_nonrec();
  mylist.dump();

  
}

Category: Uncategorized | Comment

A quick and dirty BST implementation

Isilon /var full usage at 100% but few files

Heap (maxheap) implementation

A singly linked list with reverse…

Recent Posts

Archives

About