public boolean rm ( Msg msg , int start , int size ) { // TODO: Shouldn't an error be reported if the key does not exist? if ( size == 0 ) { if ( refcnt == 0 ) { return false ; } refcnt -- ; return refcnt == 0 ; } assert ( msg != null ) ; byte c = msg . get ( start ) ; if ( count == 0 || c < min || c >= min + count ) { return false ; } Trie nextNode = count == 1 ? next [ 0 ] : next [ c - min ] ; if ( nextNode == null ) { return false ; } boolean ret = nextNode . rm ( msg , start + 1 , size - 1 ) ; // Prune redundant nodes if ( nextNode . isRedundant ( ) ) { //delete next_node; assert ( count > 0 ) ; if ( count == 1 ) { // The just pruned node was the only live node next = null ; count = 0 ; -- liveNodes ; assert ( liveNodes == 0 ) ; } else { next [ c - min ] = null ; assert ( liveNodes > 1 ) ; -- liveNodes ; // Compact the table if possible if ( liveNodes == 1 ) { // We can switch to using the more compact single-node // representation since the table only contains one live node Trie node = null ; // Since we always compact the table the pruned node must // either be the left-most or right-most ptr in the node // table if ( c == min ) { // The pruned node is the left-most node ptr in the // node table => keep the right-most node node = next [ count - 1 ] ; min += count - 1 ; } else if ( c == min + count - 1 ) { // The pruned node is the right-most node ptr in the // node table => keep the left-most node node = next [ 0 ] ; } assert ( node != null ) ; //free (next.table); next = new Trie [ ] { node } ; count = 1 ; } else if ( c == min ) { // We can compact the table "from the left". // Find the left-most non-null node ptr, which we'll use as // our new min byte newMin = min ; for ( int i = 1 ; i < count ; ++ i ) { if ( next [ i ] != null ) { newMin = ( byte ) ( i + min ) ; break ; } } assert ( newMin != min ) ; assert ( newMin > min ) ; assert ( count > newMin - min ) ; count = count - ( newMin - min ) ; next = realloc ( next , count , true ) ; min = newMin ; } else if ( c == min + count - 1 ) { // We can compact the table "from the right". // Find the right-most non-null node ptr, which we'll use to // determine the new table size int newCount = count ; for ( int i = 1 ; i < count ; ++ i ) { if ( next [ count - 1 - i ] != null ) { newCount = count - i ; break ; } } assert ( newCount != count ) ; count = newCount ; next = realloc ( next , count , false ) ; } } } return ret ; }
removed from the trie .