doubly-linked free-lists for thread caches and page heaps

third_party/tcmalloc/chromium/src/thread_cache.cc

 // Copyright (c) 2008, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 135 matching lines @@
   const int batch_size = Static::sizemap()->num_objects_to_move(cl);
 
   const int num_to_move = min<int>(list->max_length(), batch_size);
   void *start, *end;
   int fetch_count = Static::central_cache()[cl].RemoveRange(
       &start, &end, num_to_move);
 
   ASSERT((start == NULL) == (fetch_count == 0));
   if (--fetch_count >= 0) {
     size_ += byte_size * fetch_count;
-    list->PushRange(fetch_count, SLL_Next(start), end);
+    // Pop the top of the list and add the rest to the freelist.
+    void *second = start;
+    start = FL_Pop(&second);
+    list->PushRange(fetch_count, second, end);
   }
 
   // Increase max length slowly up to batch_size.  After that,
   // increase by batch_size in one shot so that the length is a
   // multiple of batch_size.
   if (list->max_length() < batch_size) {
     list->set_max_length(list->max_length() + 1);
   } else {
     // Don't let the list get too long.  In 32 bit builds, the length
     // is represented by a 16 bit int, so we need to watch out for
@@ skipping 326 matching lines @@
 void ThreadCache::set_overall_thread_cache_size(size_t new_size) {
   // Clip the value to a reasonable range
   if (new_size < kMinThreadCacheSize) new_size = kMinThreadCacheSize;
   if (new_size > (1<<30)) new_size = (1<<30);     // Limit to 1GB
   overall_thread_cache_size_ = new_size;
 
   RecomputePerThreadCacheSize();
 }
 
 }  // namespace tcmalloc