private char insert ( char p , char [ ] key , int start , char val ) { int len = strlen ( key , start ) ; if ( p == 0 ) { // this means there is no branch, this node will start a new branch. // Instead of doing that, we store the key somewhere else and create // only one node with a pointer to the key p = freenode ++ ; eq [ p ] = val ; // holds data length ++ ; hi [ p ] = 0 ; if ( len > 0 ) { sc [ p ] = 0xFFFF ; // indicates branch is compressed lo [ p ] = ( char ) kv . alloc ( len + 1 ) ; // use 'lo' to hold pointer to key strcpy ( kv . getArray ( ) , lo [ p ] , key , start ) ; } else { sc [ p ] = 0 ; lo [ p ] = 0 ; } return p ; } if ( sc [ p ] == 0xFFFF ) { // branch is compressed: need to decompress // this will generate garbage in the external key array // but we can do some garbage collection later char pp = freenode ++ ; lo [ pp ] = lo [ p ] ; // previous pointer to key eq [ pp ] = eq [ p ] ; // previous pointer to data lo [ p ] = 0 ; if ( len > 0 ) { sc [ p ] = kv . get ( lo [ pp ] ) ; eq [ p ] = pp ; lo [ pp ] ++ ; if ( kv . get ( lo [ pp ] ) == 0 ) { // key completely decompressed leaving garbage in key array lo [ pp ] = 0 ; sc [ pp ] = 0 ; hi [ pp ] = 0 ; } else { // we only got first char of key, rest is still there sc [ pp ] = 0xFFFF ; } } else { // In this case we can save a node by swapping the new node // with the compressed node sc [ pp ] = 0xFFFF ; hi [ p ] = pp ; sc [ p ] = 0 ; eq [ p ] = val ; length ++ ; return p ; } } char s = key [ start ] ; if ( s < sc [ p ] ) { lo [ p ] = insert ( lo [ p ] , key , start , val ) ; } else if ( s == sc [ p ] ) { if ( s != 0 ) { eq [ p ] = insert ( eq [ p ] , key , start + 1 , val ) ; } else { // key already in tree, overwrite data eq [ p ] = val ; } } else { hi [ p ] = insert ( hi [ p ] , key , start , val ) ; } return p ; }
The actual insertion function recursive version .