Patent ID: 8775393

Claim:
A computer-implemented method for inserting a representation of a new rule, defined as a set of at least one new transition corresponding to the new rule, each of the at least one new transition of the set being from a source state to a destination state, into a perfect hash table which includes previously placed transitions, each of the previously placed transitions being from a source state to a destination state, to generate an updated perfect hash table, the computer-implemented method comprising, for each of the at least one new transition of the new rule: a) hashing the new transition; b) determining whether the hashed new transition collides with any of the previously placed transitions; c) responsive to a determination that there is no collision, inserting the hashed new transition into the perfect hash table, and otherwise, responsive to a determination that the hashed new transition collides with any of the previously placed transitions, 1) determining whether or not the source state associated with the new transition has more transitions than a state associated with the colliding transition, and 2) responsive to a determination that the source state associated with the new transition has equal or more transitions than the source state associated with the colliding transition, A) removing from the hash table any transitions of the source state associated with the colliding transition, B) placing the hashed new transition into the perfect hash table, and C) re-placing the removed transitions into the hash table such that the hash table is maintained as a perfect hash table, otherwise, responsive to a determination that the source state associated with the new transition has fewer transitions than the source state associated with the colliding transition, A) removing any previously placed transitions of the source state associated with the new transition, and B) re-placing the transitions of the source state associated with the new transition into the hash table such that the hash table is maintained as a perfect hash table.