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

third_party/tcmalloc/chromium/src/page_heap_allocator.h

 // 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 18 matching lines @@
 
 // ---
 // Author: Sanjay Ghemawat <opensource@google.com>
 
 #ifndef TCMALLOC_PAGE_HEAP_ALLOCATOR_H_
 #define TCMALLOC_PAGE_HEAP_ALLOCATOR_H_
 
 #include <stddef.h>                     // for NULL, size_t
 
 #include "common.h"            // for MetaDataAlloc
+#include "free_list.h"          // for FL_Push/FL_Pop
 #include "internal_logging.h"  // for ASSERT, CRASH
 
 namespace tcmalloc {
 
 // Simple allocator for objects of a specified type.  External locking
 // is required before accessing one of these objects.
 template <class T>
 class PageHeapAllocator {
  public:
   // We use an explicit Init function because these variables are statically
   // allocated and their constructors might not have run by the time some
   // other static variable tries to allocate memory.
   void Init() {
     ASSERT(sizeof(T) <= kAllocIncrement);
     inuse_ = 0;
     free_area_ = NULL;
     free_avail_ = 0;
     free_list_ = NULL;
     // Reserve some space at the beginning to avoid fragmentation.
     Delete(New());
   }
 
   T* New() {
     // Consult free list
     void* result;
     if (free_list_ != NULL) {
-      result = free_list_;
-      free_list_ = *(reinterpret_cast<void**>(result));
+      result = FL_Pop(&free_list_);
     } else {
       if (free_avail_ < sizeof(T)) {
         // Need more room. We assume that MetaDataAlloc returns
         // suitably aligned memory.
         free_area_ = reinterpret_cast<char*>(MetaDataAlloc(kAllocIncrement));
         if (free_area_ == NULL) {
           CRASH("FATAL ERROR: Out of memory trying to allocate internal "
                 "tcmalloc data (%d bytes, object-size %d)\n",
                 kAllocIncrement, static_cast<int>(sizeof(T)));
         }
         free_avail_ = kAllocIncrement;
       }
       result = free_area_;
       free_area_ += sizeof(T);
       free_avail_ -= sizeof(T);
     }
     inuse_++;
     return reinterpret_cast<T*>(result);
   }
 
   void Delete(T* p) {
-    *(reinterpret_cast<void**>(p)) = free_list_;
-    free_list_ = p;
+    FL_Push(&free_list_, p);
     inuse_--;
   }
 
   int inuse() const { return inuse_; }
 
  private:
   // How much to allocate from system at a time
   static const int kAllocIncrement = 128 << 10;
 
   // Free area from which to carve new objects
   char* free_area_;
   size_t free_avail_;
 
   // Free list of already carved objects
   void* free_list_;
 
   // Number of allocated but unfreed objects
   int inuse_;
 };
 
 }  // namespace tcmalloc
 
 #endif  // TCMALLOC_PAGE_HEAP_ALLOCATOR_H_