A method of reprogramming classification data in a packet classification state machine without interrupting the operation of the state machine is disclosed. Data relating to a plurality of new nodes from a starting node of the classification tree within a classification tree are stored such that they accurately indicate subsequent nodes within the existing data structure. Once the data is stored, a new first node address is stored in a predetermined location. Thereby causing subsequent state machine executions to begin at a new node. Preferably, the new first node address is stored using an atomic operation such that no reading of the first node address is possible during the store operation. The method allows a plurality of state machines to simultaneously use a same classification data memory because the method does not involve overwriting existing data.