Changeset 3144 for trunk/containers/include/hash_table.h

Timestamp:

03/08/10 20:03:58 (6 months ago)

Author:

plasmahh

Message:

• added some draft ideas

Files:

• trunk/containers/include/hash_table.h (modified) (1 diff)

trunk/containers/include/hash_table.h

@@ -229 +229 @@
 };
 #endif
+
+// all of them should get a _templ variant that gets the NEXT parameter, and
+// one without, then we can use an mpl list of all of them that we chain
+// together with the NEXT ones.
+/**
+ * Tries to resolve collisions by linear probing, that is if slot[hash % mask]
+ * is occupied, the algorithm will use a loop for(i=1 to maxsteps) try
+ * slot[(hash+(i*stepsize) % mask] as the next slot.
+ * @tparam NEXT the type that is being used next to resolve collisions
+ * @tparam stepsize the amount to add in each iteration
+ * @tparam maxsteps the maximum number of iterations this resolver will try
+ * until giving up and passing work to the next one
+ */
+template<
+class NEXT,
+size_t stepsize,
+size_t maxsteps
+>
+struct resolver_linear_probing
+{
+        // DRAFT!!!
+        template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
+        bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
+        {
+                for( size_t i = 1; i <= maxsteps; ++i )
+                {
+                        size_t hvalue = hsum + stepsize * i;
+                        size_t idx = SLOT_SELECTOR()(hvalue,mask);
+                        if( ! INSERTER::occupied(idx,table) )
+                        {
+                                return INSERTER::insert(it,idx,table);
+                        }
+                }
+        }
+};
+
+template<
+class NEXT,
+class polytype,
+size_t maxsteps,
+           // XXX Check if this technique shouldnt be use everywhere else where some float would be a nice idea
+size_t c1_n,
+size_t c2_n,
+size_t c1_d = 1,
+size_t c2_d = 1
+>
+struct resolver_quadratic_probing
+{
+        // DRAFT!!!
+        template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
+        bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
+        {
+                polytype c1 = c1_n / c1_d;
+                polytype c2 = c2_n / c2_d;
+                for( size_t i = 1; i <= maxsteps; ++i )
+                {
+                        size_t hvalue = hsum + c1 * i + c2 * i * i;
+                        size_t idx = SLOT_SELECTOR()(hvalue,mask);
+                        if( ! INSERTER::occupied(idx,table) )
+                        {
+                                return INSERTER::insert(it,idx,table);
+                        }
+                }
+        }
+};
+
+template<
+class NEXT,
+class OTHERHASH,
+size_t maxsteps
+>
+struct resolver_double_hashing
+{
+        // DRAFT!!!
+        template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
+        bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
+        {
+                OTHERHASH hasher;
+                size_t extrahash = hasher(it);
+                for( size_t i = 1; i <= maxsteps; ++i )
+                {
+                        size_t hvalue = hsum + i * extrahash;
+                        size_t idx = SLOT_SELECTOR()(hvalue,mask);
+                        if( ! INSERTER::occupied(idx,table) )
+                        {
+                                return INSERTER::insert(it,idx,table);
+                        }
+                }
+        }
+};
+
+template<
+class NEXT,
+class OTHERHASH
+>
+struct resolver_second_hashing
+{
+        // DRAFT!!!
+        template<class ITEM_TYPE, class TABLE_TYPE, class INSERTER, class SLOT_SELECTOR>
+        bool operator()( size_t hsum, size_t mask, ITEM_TYPE& it, TABLE_TYPE& table )
+        {
+                OTHERHASH hasher;
+                size_t hvalue = hasher(it);
+                size_t idx = SLOT_SELECTOR()(hvalue,mask);
+                if( ! INSERTER::occupied(idx,table) )
+                {
+                        return INSERTER::insert(it,idx,table);
+                }
+        }
+};
+
+
 
 struct slot_selector_modulo