×

Optimized resizing for RCU-protected hash tables

  • US 9,009,122 B2
  • Filed: 12/08/2011
  • Issued: 04/14/2015
  • Est. Priority Date: 12/08/2011
  • Status: Expired due to Fees
First Claim
Patent Images

1. A system, comprising:

  • one or more processors;

    a memory coupled to said one or more processors, said memory including a computer usable medium storing a first RCU [Read-Copy Update]-protected first hash table and at least one program of instructions executable by said processor to perform operations, said operations comprising;

    allocating a second RCU-protected hash table in said memory, said second hash table representing a resized version of said first hash table that has a different number of hash buckets than said first hash table, said second hash table buckets being defined but initially having no hash table elements;

    populating said second hash table without copying or moving any hash table elements in memory by linking each hash bucket of said second hash table to all hash buckets of said first hash table containing elements that hash to said second hash table bucket;

    publishing said second hash table so that it is available for searching by hash table readers; and

    freeing said first hash table from said memory after waiting for a grace period which guarantees that no readers searching said first hash table will be affected by said freeing.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×