Segmentation Fault In Recurisve Structure With Smart Pointer

A singly linked list implemented with smart pointer, which has a reference to next, can easily cause Stack Overflow at its destruction because the destructor of the next, and the next, and the next, are called recursively.

Here's the code.

Code:

#include <boost/shared_ptr.hpp>
#include <iostream>
 
#define RECURSIVE
 
class IntSLLNode {
 
private:
  int index;
  boost::shared_ptr<IntSLLNode> next;
 
  IntSLLNode(int ix){
    index = ix;
  }
 
public:
  int hasNext(){return next != 0;}
  boost::shared_ptr<IntSLLNode>& moveNext(){return next;}
  int getIndex(){return index;}
  friend class IntSLList;
};
 
class IntSLList {
private:
  boost::shared_ptr<IntSLLNode> head, tail;
public:  
  ~IntSLList(){
#ifndef RECURSIVE
    while(head != tail){
      // replace
      head = head->next;
    }
#endif
  }
 
  void addNode(int index){
 
    boost::shared_ptr<IntSLLNode> n(new IntSLLNode(index));
    if(head == 0){
      head = tail =n;
    }
    else
    {
      tail->next = n;
      tail = n;
    }
 
  }
 
  boost::shared_ptr<IntSLLNode>& getHeadNode(){return head;}
};
 
int main(){
  IntSLList list;
  // the number to reproduce crush may vary, but seems to be stable
  // On my Core2Duo box, it is around 65000
  // Here I dare to use a value large enough
  for(int i=0; i<1000000; i++){
    list.addNode(i);
  }
  // crush at destruction
  std::cout << "CRUSH?" << std::endl;
}


This works by commenting out the line 4.

For your own smart pointer, the point is line 7 in the following code.

Code:

SmartPointer& operator=(const SmartPointer& src){
    if(this != &src){
      if(counter->decrement() == 0){
        delete counter;
        //src.pointee_ = 0; // NOT DESTRUCTIVE
        counter = src.counter;
        counter->increment(); // increment before deleting pointee_, which might have a reference to src. This results in a temporal no referencer, and triggers recursive destruction
        if(pointee_) delete pointee_;
        pointee_ = src.pointee_;
      }else{
        pointee_ = src.pointee_;
        //src.pointee_ = 0; // NOT DESTRUCTIVE
        counter = src.counter;
        counter->increment();
      }
    }
    return *this;
  }

If you call delete pointee_ before incrementing the counter of src, it triggers recursive destruction in the above case.

For a large graph cached in memory, it's good to have some kind of protection or grouping methods.

Posted under Information, Performance, Ease Of Use on 07.10.2010 • PermalinkPermalink

So far, so bad.

I found a couple of things. A couple of bad things.

1. shared_ptr is not thread safe * it was stack overflow by recursive destruction

Here's the code to reproduce. The reason follows.

SPIntSLList.h

Code:

#ifndef INT_SINGLY_LINKEDLIST
#define INT_SINGLY_LINKEDLIST
 
#include <boost/shared_ptr.hpp>
 
class SPIntSLLNode {
 
private:
  int index;
  long int payload[4];
  boost::shared_ptr<SPIntSLLNode> next;
 
  SPIntSLLNode(int ix){
    index = ix;
  }
 
public:
  int hasNext(){return next != 0;}
  boost::shared_ptr<SPIntSLLNode>& moveNext(){return next;}
  int getIndex(){return index;}
  friend class SPIntSLList;
};
 
class SPIntSLList {
private:
  boost::shared_ptr<SPIntSLLNode> head, tail;
public:  
  ~SPIntSLList();
 
  void addNode(int index);
  boost::shared_ptr<SPIntSLLNode>& getHeadNode(){return head;}
};
 
#endif

SPIntSLList.cpp

Code:

#include <iostream>
#include <time.h>
#include "SPIntSLList.h"
 
SPIntSLList::~SPIntSLList(){
  // no need iterative deletion
}
 
void SPIntSLList::addNode(int index){
  boost::shared_ptr<SPIntSLLNode> n(new SPIntSLLNode(index));
  if(head == 0){
    head = n;
    tail = n;
  }
  else
  {
    tail->next = n;
    tail = n;
  }
}
 
int main(){
 
  std::cout << "sizeof(SPIntSLLNode) = " << sizeof(SPIntSLLNode) << std::endl;
 
  clock_t start, end;
 
  std::cout << "creating huge large SPIntSLList" << std::endl;
  start = clock();
  SPIntSLList huge;
  std::cout << "creating huge SPIntSLListNode" << std::endl;
  // 157160: segmetation fault boarder when load was evaluated
  for(int i=0; i<1000000; i++){
    huge.addNode(i);
    // n, temporal PSP is destructed here
  }
  end = clock();
  std::cout << "creation time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;
 
  std::cout << "iterating over huge SPIntSLListNode" << std::endl;
  start = clock();
  // the following code calls copy constructor instead of assignment operator
  boost::shared_ptr<SPIntSLLNode> current = huge.getHeadNode();
  while(current->hasNext()){
    if(current->getIndex() % 10000 == 0)
      std::cout << "index:" << current->getIndex() << std::endl;
    current = current->moveNext();
  }
  end = clock();
  std::cout << "iteration time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;
  std::cout << "completed huge SPIntSLList" << std::endl;
}

Then, a wonderful gift.

Segmentation fault (core dumped)

And here's the stack trace.

Code:

Program terminated with signal 11, Segmentation fault.
#0  0x0000000000401227 in boost::detail::atomic_exchange_and_add (pw=Cannot access memory at address 0x7fff2ee2dff8
)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:36
36      {
(gdb) bt
#0  0x0000000000401227 in boost::detail::atomic_exchange_and_add (pw=Cannot access memory at address 0x7fff2ee2dff8
)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:36
#1  0x000000000040137b in boost::detail::sp_counted_base::release (
    this=0xd921130)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/sp_counted_base_gcc_x86.hpp:143
#2  0x000000000040142b in boost::detail::shared_count::~shared_count (
    this=0xd9210c0, __in_chrg=<value optimized out>)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/detail/shared_count.hpp:217
#3  0x00000000004014be in boost::shared_ptr<SPIntSLLNode>::~shared_ptr (
    this=0xd9210b8, __in_chrg=<value optimized out>)
    at /home/takenori/workspace_native/Boost/boost/smart_ptr/shared_ptr.hpp:163

They have the same mistake as mine.

Code:

~shared_count() // nothrow
    {
       if( pi_ != 0 ) pi_->release();
#if defined(BOOST_SP_ENABLE_DEBUG_HOOKS)
        id_ = 0;
#endif
    }

After "pi_ != 0", pi is not guarranteed to stay valid. It is possible to delete after its evaluation.

The last two referencing threads can enter release().

Code:

void release() // nothrow
    {
        if( atomic_exchange_and_add( &use_count_, -1 ) == 1 )
        {
            dispose();
            weak_release();
        }
    }

Then, one comes late experiences Segmentation Fault on $use_count_.

2. Atomic types and operations are not as fast as RCU(read copy update)

I expected this(from the presentation by liburcu).

But the performance of lock-free reference counting smart pointer is as slow as mutex, on my dual core linux box.

The difference might be less significant because it's only dual core on 1 CPU. But I doubt it.

The test was like this.

Code:

#include "TsPersistentSmartPointer.h"
#include <iostream>
#include <time.h>
 
#define MAX_THREADS  100
#define ITERATION  1000
 
class Foo{
public:
  Foo(int id) : id_(id){std::cout << id_ << ":constructer called" << std::endl;}
  ~Foo(){std::cout << id_ << ":destructer called" << std::endl;}
 
  void SayHello(){
    std::cout << "Hello, this is " << id_ << std::endl;
  }
private:
  int id_;
};
 
void *copy(void *arg){
  // 1. copy, adding a reference
  TsPersistentSmartPointer<Foo> psp = *((TsPersistentSmartPointer<Foo>*) arg);
  TsPersistentSmartPointer<Foo> pspCopied = psp;
 
  // 2. removing a reference when exiting
}
 
int main(){
  
  TsPersistentSmartPointer<Foo> psp(new Foo(3));
  pthread_t threads[MAX_THREADS];
  int rt;
 
  clock_t start, end;
  std::cout << "Executing..." << std::endl;
  start = clock();
  for(int i=0; i<ITERATION; i++)
  {
    for(int t=0; t<MAX_THREADS; t++){
      rt = pthread_create(&threads[t], NULL, copy, (void*) &psp);
      if(rt != 0){
        std::cout << "Failed to create thread " << t << std::endl;
      }
    }
 
    for(int t=0; t<MAX_THREADS; t++){
      rt = pthread_join(threads[t], NULL);
      if(rt != 0){
        std::cout << "Failed to join thread " << t << std::endl;
      }
    }
  }
 
  end = clock();
  std::cout << "execution time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;
}

This is heavily read intensive test. But each read on reference counting SmartPointer requires incrementing the counter, and decrementing when exiting. So it is deadly heavy write intensive test. It would run as low as Mutex in the figure above.

liburcu is implemented with architecture specific assembly code. But what's the difference? That's what I ought to find...

Posted under Performance, Ease Of Use on 07.9.2010 • PermalinkPermalink

Lock-free reference counting smart pointer

With GCC 4.4, I tested how atomic types and operations of c++0x work by implementing lock-free reference counting smart pointer.

TsPersistentSmartPointer.h

Code:

#ifndef PERSISTENT_SMART_POINTER
#define PERSISTENT_SMART_POINTER
 
#include <cstdatomic>
 
class Counter {
public:
  Counter():i(1){}
  ~Counter(){}
 
  void increment(){
    i.fetch_add( 1, std::memory_order_relaxed );
  }
  int decrement(){
    return i.fetch_sub( 1, std::memory_order_relaxed );
  }
  void reset(){
    i.store(0, std::memory_order_relaxed);
  }
private:
  std::atomic_uint i;
};
 
template <class T>
class TsPersistentSmartPointer {
public:
  explicit TsPersistentSmartPointer(T* pointee) : pointee_(pointee), counter(new Counter()){
  }
  TsPersistentSmartPointer() : pointee_(0), counter(new Counter()){
  }; // for null construction, has to be copied from somewhere else
  ~TsPersistentSmartPointer(){
    if(counter->decrement() == 0){
      delete counter;
      delete pointee_;
    }
  }
 
  T& operator*() const{
    return *pointee_;
  }
 
  T* operator->() const{
    return pointee_;
  }
 
  // assignment
  TsPersistentSmartPointer(const TsPersistentSmartPointer& src){
      pointee_ = src.pointee_;
      counter = src.counter;
      counter->increment();
      //src.pointee_ = 0; // NOT DESTRUCTIVE
  }
  TsPersistentSmartPointer& operator=(const TsPersistentSmartPointer& src){
    if(this != &src){
      if(counter->decrement() == 0){
        delete counter;
        if(pointee_) delete pointee_;
      }
      pointee_ = src.pointee_;
      //src.pointee_ = 0; // NOT DESTRUCTIVE
      counter = src.counter;
      counter->increment();
    }
    return *this;
  }
  TsPersistentSmartPointer& operator=(T* pointee){
    if(pointee_ != pointee){
      if(pointee_)
        delete pointee_;
      pointee_ = pointee;
      counter->reset();
    }
    return *this;
  }
 
  // equality
  inline friend bool operator==(const TsPersistentSmartPointer& psp, const T* pointee){
    return psp.pointee_ == pointee;
  }
  inline friend bool operator==(const T* pointee, const TsPersistentSmartPointer& psp){
    return pointee == psp.pointee_;
  }
  // inequality
  inline friend bool operator!=(const TsPersistentSmartPointer& psp, const T* pointee){
    return psp.pointee_ != pointee;
  }
  inline friend bool operator!=(const T* pointee, const TsPersistentSmartPointer& psp){
    return pointee != psp.pointee_;
  }
 
private:
  T* pointee_;
  Counter* counter;
};
 
#endif

Atomic operations are implemented inside Counter class. The point is the following part, the destructor of TsPersistentSmartPointer:

Code:

if(counter->decrement() == 0){
      delete counter;
      delete pointee_;
    }

At first, I did the following, which resulted in Segmentation Fault under a million of concurrent destructions.

Code:

counter->decrement();
    if(counter->get() == 0){
      delete counter;
      delete pointee_;
    }

The problem could happen when the last two enters concurrently.

Thread1: counter->decrement(); // i = 1
Thread2: counter->decrement(); // i = 0
Thread2: counter->get() == 0 // TRUE
Thread1: counter->get() == 0 // TRUE!
Thread1: delete counter;
Thread2: delete counter; // OUCH!

Here're some more code for testing.

TsPersistentSmartPointer.cpp

Code:

#include "TsPersistentSmartPointer.h"
#include <iostream>
 
class Foo{
public:
  Foo(int id) : id_(id){std::cout << id_ << ":constructer called" << std::endl;}
  ~Foo(){std::cout << id_ << ":destructer called" << std::endl;}
 
  void SayHello(){
    std::cout << "Hello, this is " << id_ << std::endl;
  }
private:
  int id_;
};
 
int main(){
 
  Foo f0(0);
  Foo *f1 = new Foo(1);
  Foo *f2 = new Foo(2); // memory leak
  Foo *f3 = new Foo(3);
  TsPersistentSmartPointer<Foo> psp(0);
 
  // copy
  psp = f3;
 
  // dereference and indirection
  psp->SayHello();
  (*psp).SayHello();
 
  // equality
  std::cout << "equality works? :" << ((psp == f3) & (f3 == psp)) << std::endl;
 
  // copy constructor
  TsPersistentSmartPointer<Foo> pspCopied(psp);
  // dereference and indirection
  pspCopied->SayHello();
  (*pspCopied).SayHello();
 
  // see how destructors are called
  delete f1;
 
  return 0;
}

TsPSPIntSLList.h

Code:

#ifndef INT_SINGLY_LINKEDLIST
#define INT_SINGLY_LINKEDLIST
 
#include "TsPersistentSmartPointer.h"
 
class TsPSPIntSLLNode {
 
private:
  int index;
  long int payload[4];
  TsPersistentSmartPointer<TsPSPIntSLLNode> next;
 
  TsPSPIntSLLNode(int ix){
    index = ix;
  }
 
public:
  int hasNext(){return next != 0;}
  TsPersistentSmartPointer<TsPSPIntSLLNode>& moveNext(){return next;}
  int getIndex(){return index;}
  friend class TsPSPIntSLList;
};
 
class TsPSPIntSLList {
private:
  TsPersistentSmartPointer<TsPSPIntSLLNode> head, tail;
public:  
  ~TsPSPIntSLList();
 
  void addNode(int index);
  TsPersistentSmartPointer<TsPSPIntSLLNode>& getHeadNode(){return head;}
};
 
#endif

TsPSPIntSLList.cpp

Code:

#include <iostream>
#include <time.h>
#include "TsPSPIntSLList.h"
 
TsPSPIntSLList::~TsPSPIntSLList(){
  // no need iterative deletion
}
 
void TsPSPIntSLList::addNode(int index){
  TsPersistentSmartPointer<TsPSPIntSLLNode> n(new TsPSPIntSLLNode(index));
  if(head == 0){
    head = n;
    tail = n;
  }
  else
  {
    tail->next = n;
    tail = n;
  }
}
 
int main(){
 
  std::cout << "sizeof(TsPSPIntSLLNode) = " << sizeof(TsPSPIntSLLNode) << std::endl;
 
  clock_t start, end;
 
  std::cout << "creating huge large TsPSPIntSLList" << std::endl;
  start = clock();
  TsPSPIntSLList huge;
  std::cout << "creating huge TsPSPIntSLListNode" << std::endl;
  // 157160: segmetation fault boarder when load was evaluated
  for(int i=0; i<1000000; i++){
    huge.addNode(i);
    // n, temporal PSP is destructed here
  }
  end = clock();
  std::cout << "creation time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;
 
  std::cout << "iterating over huge TsPSPIntSLListNode" << std::endl;
  start = clock();
  // the following code calls copy constructor instead of assignment operator
  TsPersistentSmartPointer<TsPSPIntSLLNode> current = huge.getHeadNode();
  while(current->hasNext()){
    if(current->getIndex() % 10000 == 0)
      std::cout << "index:" << current->getIndex() << std::endl;
    current = current->moveNext();
  }
  end = clock();
  std::cout << "iteration time: " << (end-start) << " clocks(" << (double) (end-start)/CLOCKS_PER_SEC << " sec)" << std::endl;
  std::cout << "completed huge TsPSPIntSLList" << std::endl;
 
  // followings are called automatically, but here explicitely for measurement
  //current.~TsPersistentSmartPointer();
  //huge.~TsPSPIntSLList();
 
}

Please note no code is required for the destructor of TsPersistentSmartPointer.

So what about reference linking?

No. It can't be lock free if with doubly linked list. Two links to prev and next have to be updated at the same time, otherwise one could see inconsistent stete.

Performance?

I have measured performance with clock() function defined in "time.h" as in TsPSPIntSLList.cpp.

Raw Pointer for single thread
Creation: 0.01 sec
Iteration: 0.02 sec

SmartPointer for single thread
Creation: 0.27 sec
Iteration: 0.05 sec

Lock-free SmartPointer
Creation: 0.45 sec
Iteration: 0.12 sec

In time, there's a significant overhead over plain raw pointer implementation.

Also, a couple of CPU cache statistics collected by vaigrind.

Raw Pointer for single thread
Instruction Read: 409,523,865
Data Read: 115,388,899
L1 Data Read Miss: 2,013,421
L2 Data Read Miss: 2,005,354
Data Write: 69,133,007
L1 Data Write Miss: 1,002,531
L2 Data Write Miss: 1,001,018

Smart Pointer for single thread
Instruction Read: 960,359,665
Data Read: 284,618,659
L1 Data Read Miss: 2,049,844
L2 Data Read Miss: 2,041,472
Data Write: 172,410,809
L1 Data Write Miss: 1,916,330
L2 Data Write Miss: 1,914,709

Lock-free Smart Pointer
Instruction Read: 1,161,535,161
Data Read: 317,391,770
L1 Data Read Miss: 2,013,687
L2 Data Read Miss: 2,005,198
Data Write: 235,134,100
L1 Data Write Miss: 2,002,377
L2 Data Write Miss: 2,001,012

(pthread Mutex SmartPointer)
Creation: 0.51 sec
Iteration: 0.14 sec
Instruction Read: 1,149,615,787
Data Read: 311,412,927
L1 Data Read Miss: 3,014,567
L2 Data Read Miss: 3,005,312
Data Write: 237,144,326
L1 Data Write Miss: 3,002,797
L2 Data Write Miss: 3,001,194

Please note L1 and L2 cache read miss stays around as total number increases.
(except mutex: mutex calls another million of malloc)

It is not free lunch. But for read intensive applications, how attractive it is!

Posted under Performance, Ease Of Use on 07.8.2010 • PermalinkPermalink

Google Visualization API On Your Site Example

This is a Google Visualization Gadget example that is hosted on my site.

SONY's sales&op_profits by segments since 1996. Enjoy!

Posted under Ease Of Use on 06.7.2008 • PermalinkPermalink

Visualize Your Data with Google Visualization API

Today, here at Google I/O 2nd day, a new Google Visualization API was announced.

What's new?

1. events
2. gadget.draw()

Google Visualization Gadget supports selection events so that a developer can respond to end users.

With draw() method, a gadget can draw any tables only if a table supports pre-defined DataTable APIs.

Let's try the new draw() method with the JSON example.

Instead of writing tables with HTML tags, simply pass DataTable object to Table gadget.

Here's the code.

Code:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
  <head>
    <script type="text/javascript" src="http://www.google.com/jsapi"></script>
    <script type="text/javascript">
    
    google.load("visualization", "1", {packages:["table"]});
    
    var xhr;
    try {  xhr = new ActiveXObject('Msxml2.XMLHTTP');   }
    catch (e)
    {
        try {   xhr = new ActiveXObject('Microsoft.XMLHTTP');    }
        catch (e2)
        {
          try {  xhr = new XMLHttpRequest();     }
          catch (e3) {  xhr = false;   }
        }
     }
 
   xhr.open("GET", DATASOURCE_URL,  true);
   xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
   xhr.send(null);
  
   xhr.onreadystatechange  = function()
    {
         if(xhr.readyState  == 4)
         {
              if(xhr.status  == 200){
                  the_object = eval( "(" + xhr.responseText + ")" );
                  handleQueryResponse(the_object.table);
              }else{
                
              }
         }
    };
 
      // Query response handler function.
      function handleQueryResponse(table) {
        var data = new google.visualization.DataTable();
        
        // convert to Google.DataTable
        // column
        for (var col = 0; col < table.cols.length; col++) {
          data.addColumn('string', table.cols[col].label);
        }
        // row
        for (var row = 0; row < table.rows.length; row++) {
          data.addRow();
          for (var col = 0; col < table.cols.length; col++) {
            data.setCell(row, col, table.rows[row][col].v);
          }
        }
        
       var vis_table = new google.visualization.Table(document.getElementById('table_div'));
       vis_table.draw(data, {showRowNumber: false});
        
      }
 
    </script>
  </head>
 
  <body>
    <div id="table_div">Loading...</div>
  </body>
</html>

Thanks a lot, Google Visualization Team! Now that our own data can be easily integrated with Gadget!

Posted under Ease Of Use on 05.30.2008 • PermalinkPermalink

JSON Restful Web Service in Java

What kind of ways are available to get JSON Restful Web Service in Java?

Wait, what is JSON? Also Restful Web Service exactly?

Actually, I got to know them only a couple of weeks ago.

If you have tried XML Web Service with SOAP, you probably know how hard to get performance, and ease of use without complexity(especially about schema binding).

Then, JSON Restful Web Service must be what you will get interested in.

Let's go back to the first question. You can think of two providers. Sun and Apache. Here're options to go first.

  1. Apache Axis2.0
  2. JAX-WS with JSON extention

In my opinion, they're just a topping on top of XML Web Service. That is the very basic mismatch. Feel free to try if you need to make sure

This is the one, with which you can get a true power of JSON Restful Web Service.

Restlet

Take a look at Introduction on the site if you are not 100% sure about Restful Web Service(REST).

I'm going to show you an example to implement a service that returns DataTable compatible with one of Google Visualization API. The source of information is this thread in Google Visualization Discussion.

Code:

<CHUNK1>
google.visualization.Query.setResponse(
{
        requestId:'0',
        status:'ok',
        signature:'6173382439516707022',                /* Changes when data changes */
</CHUNK1>
So the timeseries gadget must download this JSON every so often and
check the new signature against it's own.  If the signature is
different, it knows that the data on the "spreadsheet" has changed.
<CHUNK2>
        table:{
                cols:
                        [
                                {
                                        id:'A',
                                        label:'Date',
                                        type:'d',               /* d=date */
                                        pattern:'M/d/yyyy'      /* unique date pattern */
                                },
                                {
                                        id:'B',
                                        label:'Budget',
                                        type:'n',       /*      n=number */
                                        pattern:'#0.###############'    /* unique number pattern */
                                },
                                {
                                        id:'C',
                                        label:'Revenue',
                                        type:'n',
                                        pattern:'#0.###############'
                                },
                                {
                                        id:'D',
                                        label:'Movie',
                                        type:'t',       /*      t=text */
                                        pattern:''      /* there is no text pattern */
                                }
                        ],
</CHUNK2>
Chunk2 shows the columns needed for a timeseries chart. (Date,
Value1, ..., ValueN, PopupText)
Note the type and pattern fields.  d=date, n=number, t=text
<CHUNK3>
                rows:
                        [
                                [
                                        {
                                                v:new Date(1981,10,6),
                                                f:'11/6/1981'
                                        },
                                        {
                                                v:5000000.0,
                                                f:'5000000'
                                        },
                                        {
                                                v:4.2365581E7,
                                                f:'42365581'
                                        },
                                        {
                                                v:'Time Bandits'
                                        }
                                ],
</CHUNK3>

To get this type of JSON Object is the goal. So how to do this?

In order to understand the following code, you may want to learn the tutorial how Restlet models the resource oriented Restfull world.

Restlet

Code:

import org.restlet.Application;
import org.restlet.Context;
import org.restlet.Restlet;
import org.restlet.Router;
 
public class JSONApplication extends Application {
 
  public JSONApplication() {
    super();
  }
 
  public JSONApplication(Context arg0) {
    super(arg0);
  }
 
  @Override
  public Restlet createRoot() {
        Router router = new Router(getContext());
        
        router.attach("/table", JSONTableResource.class);
        
    return router;
  }
 
}

Table Resource and JSON Representation

Code:

import org.json.JSONArray;
import org.json.JSONException;
import org.json.JSONObject;
import org.restlet.Context;
import org.restlet.data.CharacterSet;
import org.restlet.data.MediaType;
import org.restlet.data.Request;
import org.restlet.data.Response;
import org.restlet.data.Status;
import org.restlet.ext.json.JsonRepresentation;
import org.restlet.resource.Representation;
import org.restlet.resource.Resource;
import org.restlet.resource.ResourceException;
import org.restlet.resource.Variant;
 
public class JSONTableResource extends Resource {
  
  private static final String JSON_NAME_TABLE = "table";
  
  private static final String JSON_NAME_COLUMNS = "cols";
  private static final String JSON_NAME_COLUMNS_ID = "id";
  private static final String JSON_NAME_COLUMNS_LABEL = "label";
  private static final String JSON_NAME_COLUMNS_TYPE = "type";
  private static final String JSON_NAME_COLUMNS_PATTERN = "pattern";
  
  private static final String JSON_NAME_ROWS = "rows";
  private static final String JSON_NAME_ROWS_V = "v";
  private static final String JSON_NAME_ROWS_F = "f";
 
  public JSONTableResource(Context context, Request request, Response response) {
    super(context, request, response);
    
    getVariants().add(new Variant(MediaType.APPLICATION_JSON));
  }
 
  @Override
  public Representation represent(Variant variant) throws ResourceException {
    JSONObject json = new JSONObject();
    
    try {
      
      json.put("requestId", "0");
      json.put("status", "ok");
      json.put("signature", "6173382439516707022");
      
      json.put(JSON_NAME_TABLE, this.createTable());
      
    } catch (JSONException e) {
      throw new ResourceException(Status.SERVER_ERROR_INTERNAL);
    }
    
    JsonRepresentation jr = new JsonRepresentation(json);
    
    jr.setCharacterSet(CharacterSet.UTF_8);
    
    return jr;
  }
  
  private JSONObject createTable() throws JSONException{
    JSONArray columns = new JSONArray();
    JSONArray rows = new JSONArray();
    JSONObject r_c = new JSONObject();
    r_c.put(JSON_NAME_COLUMNS, columns);
    r_c.put(JSON_NAME_ROWS, rows);
    
    this.createColumns(columns);
    this.createRows(rows);
    
    return r_c;
  }
  
  private void createColumns(JSONArray columns) throws JSONException{
    
    columns.put(this.createColumn("A", "Date", "d", "M/d/yyyy"));
    columns.put(this.createColumn("B", "Budget", "n", "#0.###############"));
    columns.put(this.createColumn("C", "Revenue", "n", "#0.###############"));
    columns.put(this.createColumn("D", "Movie", "t", ""));
    
  }
  
  private void createRows(JSONArray rows) throws JSONException{
    
    JSONArray row = new JSONArray();
    
    row.put(this.createCell("new Date(1981,10,6)", "11/6/1981"));
    row.put(this.createCell("5000000.0", "5000000"));
    row.put(this.createCell("4.2365581E7", "42365581"));
    row.put(this.createCell("Time Bandits", null));
    
    rows.put(row);
    
  }
  
  private JSONObject createCell(String v, String f) throws JSONException{
    JSONObject jo = new JSONObject();
    jo.put(JSON_NAME_ROWS_V, v);
    if(f != null)
      jo.put(JSON_NAME_ROWS_F, f);
    return jo;
  }
  
  private JSONObject createColumn(String id, String label, String type, String pattern) throws JSONException{
    JSONObject jo = new JSONObject();
    jo.put(JSON_NAME_COLUMNS_ID, id);
    jo.put(JSON_NAME_COLUMNS_LABEL, label);
    jo.put(JSON_NAME_COLUMNS_TYPE, type);
    jo.put(JSON_NAME_COLUMNS_PATTERN, pattern);
    return jo;
  }
 
}

web.xml

XML:

<?xml version="1.0" encoding="UTF-8"?>
<web-app id="WebApp_ID" version="2.4"
            xmlns="http://java.sun.com/xml/ns/j2ee"
            xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
            xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee
                 http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd">
   <display-name>first steps servlet</display-name>
   <!−− Application class name −−>
   <context-param>
      <param-name>org.restlet.application</param-name>
      <param-value>
         firstSteps.JSONApplication
      </param-value>
   </context-param>
 
   <!−− Restlet adapter −−>
   <servlet>
      <servlet-name>RestletServlet</servlet-name>
      <servlet-class>
         com.noelios.restlet.ext.servlet.ServerServlet
      </servlet-class>
   </servlet>
 
   <!−− Catch all requests −−>
   <servlet-mapping>
      <servlet-name>RestletServlet</servlet-name>
      <url-pattern>/json/*</url-pattern>
   </servlet-mapping>
</web-app>

You can get JSON Object in Java here.

Here's the JSON texts you'll get.

Code:

{"status":"ok","requestId":"0",
"table":
  {"cols":[
        {"id":"A","pattern":"M/d/yyyy","label":"Date","type":"d"},
        {"id":"B","pattern":"#0.###############","label":"Budget","type":"n"},
        {"id":"C","pattern":"#0.###############","label":"Revenue","type":"n"},
        {"id":"D","pattern":"","label":"Movie","type":"t"}  
      ],
  "rows":[
        [
          {"f":"11/6/1981","v":"new Date(1981,10,6)"},
          {"f":"5000000","v":"5000000.0"},
          {"f":"42365581","v":"4.2365581E7"},
          {"v":"Time Bandits"}
        ]
      ]
  },
"signature":"6173382439516707022"}

Then, you can call the service, get DataTable, then process to visualize. Here's an example to show a simple table in Ajax.

Code:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
  <head>
    <script type="text/javascript">
    
    var xhr;
    try {  xhr = new ActiveXObject('Msxml2.XMLHTTP');   }
    catch (e)
    {
        try {   xhr = new ActiveXObject('Microsoft.XMLHTTP');    }
        catch (e2)
        {
          try {  xhr = new XMLHttpRequest();     }
          catch (e3) {  xhr = false;   }
        }
     }
 
   xhr.open("GET", JSON_RESTFULL_WEB_SERVICE_URL,  true);
   xhr.setRequestHeader("Content-Type", "application/x-www-form-urlencoded");
   xhr.send(null);
  
   xhr.onreadystatechange  = function()
    {
         if(xhr.readyState  == 4)
         {
              if(xhr.status  == 200){
                  the_object = eval( "(" + xhr.responseText + ")" );
                  handleQueryResponse(the_object.table);
              }else{
                
              }
         }
    };
 
      // Query response handler function.
      function handleQueryResponse(table) {
 
        var html = [];
        html.push('<table border="1">');
 
        // Header row
        html.push('<tr><th>Seq</th>');
        for (var col = 0; col < table.cols.length; col++) {
          html.push('<th>' + escapeHtml(table.cols[col].label) + '</th>');
        }
        html.push('</tr>');
 
        for (var row = 0; row < table.rows.length; row++) {
          html.push('<tr><td align="right">' + (row + 1) + '</td>');
          for (var col = 0; col < table.cols.length; col++) {
            html.push(table.cols[col].type == 'number' ? '<td align="right">' : '<td>');
            html.push(escapeHtml(table.rows[row][col].f));
            html.push('</td>');
          }
          html.push('</tr>');
        }
        html.push('</table>');
 
        document.getElementById('tablediv').innerHTML = html.join('');
      }
 
      function escapeHtml(text) {
        if (text == null)
          return '';
 
        return text.replace(/&/g, '&amp;')
          .replace(/</g, '&lt;')
          .replace(/>/g, '&gt;')
          .replace(/"/g, '&quot;');
      }
 
    </script>
  </head>
 
  <body>
    <div id="tablediv">Loading...</div>
  </body>
</html>

Simple, Fast, and Flexible. Experience JSON Restful Web Service!

Posted under Ease Of Use on 05.23.2008 • PermalinkPermalink

"Interface" in C

Recently, I began to study C programming language. I used to be a Java guy, but have felt like doing that to contribute to any serious device projects here in Japan.

Java is new, object oriented language. But C is old, not object oriented.

What made me surprised was that I couldn't find a way to cut a dependency. I can define a template, but they are exposed in terms of "coupling" object oriented concept.

Before diving into C world, to avoid such a "spagetti", I would like to get a gut feeling about dependency management.

Then, I have investigated Linux VFS(Virtual File System) design. A file system in Linux is well abstracted, so must have a good design in C.

"The VFS is object-oriented. A family of data structures represents the common file model. There data structures are akin to objects. Because the kernel is programmed strictly in C, without the benefit of a language directly supporting object-oriented paradigms, the data structures are represented as C structures. The structures contain both data and pointers to filesystem-implemented functions that operate on the data." - page212, Linux Kernel Development Second Edition, Robert Love

Ah-ha, a strucrue could be used like an interface... OK, let's nail down the source. Here's a code snippet from linux/fs.c.

struct super_block {
...
struct super_operations *s_op;
...
};

Methods look defined as an interface. So what about super_operations?

struct super_operations {
struct inode *(*alloc_inode)(struct super_block *sb);
void (*destroy_inode)(struct inode *);

void (*read_inode) (struct inode *);

void (*dirty_inode) (struct inode *);
int (*write_inode) (struct inode *, int);
void (*put_inode) (struct inode *);
void (*drop_inode) (struct inode *);
void (*delete_inode) (struct inode *);
void (*put_super) (struct super_block *);
void (*write_super) (struct super_block *);
int (*sync_fs)(struct super_block *sb, int wait);
void (*write_super_lockfs) (struct super_block *);
void (*unlockfs) (struct super_block *);
int (*statfs) (struct super_block *, struct kstatfs *);
int (*remount_fs) (struct super_block *, int *, char *);
void (*clear_inode) (struct inode *);
void (*umount_begin) (struct super_block *);

...
};

Mmmm, something looks strange. I wonder why they have an argument of its body, "struct super_block *" or "struct inode *".

Yes, because there is no such a thing like "instance" in C. So you can not access to an instance inside a method body, like "this" in Java. This is a bit strange, but still OK.

Yet wait, passing itself to methods mean that an interface(operations struct) depends on its concrete type! That's too bad... Its implementation can be abstracted, but not like an interface to cut dependencies.

How can I put an abstraction with an interface to cut dependencies?

I found a way to do that with a generic pointer. I am trying to test "List" interface Java design in C. Performance may matter, but still look promissing. Let's see...

Posted under Ease Of Use on 02.27.2008 • PermalinkPermalink
Free Blog Themes and Free Blog Templates