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

third_party/tcmalloc/chromium/src/tcmalloc.cc

 // Copyright (c) 2005, 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 104 matching lines @@
 #include <vector>                       // for vector
 
 #include <google/malloc_extension.h>
 #include <google/malloc_hook.h>         // for MallocHook
 #include "base/basictypes.h"            // for int64
 #include "base/commandlineflags.h"      // for RegisterFlagValidator, etc
 #include "base/dynamic_annotations.h"   // for RunningOnValgrind
 #include "base/spinlock.h"              // for SpinLockHolder
 #include "central_freelist.h"  // for CentralFreeListPadded
 #include "common.h"            // for StackTrace, kPageShift, etc
+#include "free_list.h"         // for FL_Init
 #include "internal_logging.h"  // for ASSERT, TCMalloc_Printer, etc
-#include "linked_list.h"       // for SLL_SetNext
 #include "malloc_hook-inl.h"       // for MallocHook::InvokeNewHook, etc
 #include "page_heap.h"         // for PageHeap, PageHeap::Stats
 #include "page_heap_allocator.h"  // for PageHeapAllocator
 #include "span.h"              // for Span, DLL_Prepend, etc
 #include "stack_trace_table.h"  // for StackTraceTable
 #include "static_vars.h"       // for Static
 #include "system-alloc.h"      // for DumpSystemAllocatorStats, etc
 #include "tcmalloc_guard.h"    // for TCMallocGuard
 #include "thread_cache.h"      // for ThreadCache
 
@@ skipping 1083 matching lines @@
 
   ValidateAllocatedRegion(ptr, cl);
 
   if (cl != 0) {
     ASSERT(!Static::pageheap()->GetDescriptor(p)->sample);
     ThreadCache* heap = GetCacheIfPresent();
     if (heap != NULL) {
       heap->Deallocate(ptr, cl);
     } else {
       // Delete directly into central cache
-      tcmalloc::SLL_SetNext(ptr, NULL);
+      tcmalloc::FL_Init(ptr);
       Static::central_cache()[cl].InsertRange(ptr, ptr, 1);
     }
   } else {
     SpinLockHolder h(Static::pageheap_lock());
     ASSERT(reinterpret_cast<uintptr_t>(ptr) % kPageSize == 0);
     ASSERT(span != NULL && span->start == p);
     if (span->sample) {
       StackTrace* st = reinterpret_cast<StackTrace*>(span->objects);
       tcmalloc::DLL_Remove(span);
       Static::stacktrace_allocator()->Delete(st);
@@ skipping 685 matching lines @@
   *mark = ~allocated_mark;  //  Distinctively not allocated.
 }
 
 static void MarkAllocatedRegion(void* ptr) {
   if (ptr == NULL) return;
   MarkType* mark = GetMarkLocation(ptr);
   *mark = GetMarkValue(ptr, mark);
 }
 
 #endif  // TCMALLOC_VALIDATION