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

third_party/tcmalloc/chromium/src/thread_cache.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 24 matching lines @@
 
 #include <config.h>
 #ifdef HAVE_PTHREAD
 #include <pthread.h>                    // for pthread_t, pthread_key_t
 #endif
 #include <stddef.h>                     // for size_t, NULL
 #ifdef HAVE_STDINT_H
 #include <stdint.h>                     // for uint32_t, uint64_t
 #endif
 #include <sys/types.h>                  // for ssize_t
-#include "common.h"
-#include "linked_list.h"
+#include "common.h"            // for SizeMap, kMaxSize, etc
+#include "free_list.h"  // for FL_Pop, FL_PopRange, etc
+#include "internal_logging.h"  // for ASSERT, etc
 #include "maybe_threads.h"
-#include "page_heap_allocator.h"
-#include "sampler.h"
-#include "static_vars.h"
-
-#include "common.h"            // for SizeMap, kMaxSize, etc
-#include "internal_logging.h"  // for ASSERT, etc
-#include "linked_list.h"       // for SLL_Pop, SLL_PopRange, etc
 #include "page_heap_allocator.h"  // for PageHeapAllocator
 #include "sampler.h"           // for Sampler
 #include "static_vars.h"       // for Static
 
 namespace tcmalloc {
 
 // Even if we have support for thread-local storage in the compiler
 // and linker, the OS may not support it.  We need to check that at
 // runtime.  Right now, we have to keep a manual set of "bad" OSes.
 #if defined(HAVE_TLS)
@@ skipping 126 matching lines @@
     // Is list empty?
     bool empty() const {
       return list_ == NULL;
     }
 
     // Low-water mark management
     int lowwatermark() const { return lowater_; }
     void clear_lowwatermark() { lowater_ = length_; }
 
     void Push(void* ptr) {
-      SLL_Push(&list_, ptr);
+      FL_Push(&list_, ptr);
       length_++;
     }
 
     void* Pop() {
       ASSERT(list_ != NULL);
       length_--;
       if (length_ < lowater_) lowater_ = length_;
-      return SLL_Pop(&list_);
+      return FL_Pop(&list_);
     }
 
     void PushRange(int N, void *start, void *end) {
-      SLL_PushRange(&list_, start, end);
+      FL_PushRange(&list_, start, end);
       length_ += N;
     }
 
     void PopRange(int N, void **start, void **end) {
-      SLL_PopRange(&list_, N, start, end);
+      FL_PopRange(&list_, N, start, end);
       ASSERT(length_ >= N);
       length_ -= N;
       if (length_ < lowater_) lowater_ = length_;
     }
   };
 
   // Gets and returns an object from the central cache, and, if possible,
   // also adds some objects of that size class to this thread cache.
   void* FetchFromCentralCache(size_t cl, size_t byte_size);
 
@@ skipping 160 matching lines @@
 // because we may be in the thread destruction code and may have
 // already cleaned up the cache for this thread.
 inline ThreadCache* ThreadCache::GetCacheIfPresent() {
   if (!tsd_inited_) return NULL;
   return GetThreadHeap();
 }
 
 }  // namespace tcmalloc
 
 #endif  // TCMALLOC_THREAD_CACHE_H_