third_party/tcmalloc/vendor/src/span.h

   1 // Copyright (c) 2008, Google Inc.
   2 // All rights reserved.
   3 //
   4 // Redistribution and use in source and binary forms, with or without
   5 // modification, are permitted provided that the following conditions are
   6 // met:
   7 //
   8 //     * Redistributions of source code must retain the above copyright
   9 // notice, this list of conditions and the following disclaimer.
  10 //     * Redistributions in binary form must reproduce the above
  11 // copyright notice, this list of conditions and the following disclaimer
  12 // in the documentation and/or other materials provided with the
  13 // distribution.
  14 //     * Neither the name of Google Inc. nor the names of its
  15 // contributors may be used to endorse or promote products derived from
  16 // this software without specific prior written permission.
  17 //
  18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30 // ---
  31 // Author: Sanjay Ghemawat <opensource@google.com>
  32 //
  33 // A Span is a contiguous run of pages.
  34
  35 #ifndef TCMALLOC_SPAN_H_
  36 #define TCMALLOC_SPAN_H_
  37
  38 #include <config.h>
  39 #include "common.h"
  40
  41 namespace tcmalloc {
  42
  43 // Information kept for a span (a contiguous run of pages).
  44 struct Span {
  45   PageID        start;          // Starting page number
  46   Length        length;         // Number of pages in span
  47   Span*         next;           // Used when in link list
  48   Span*         prev;           // Used when in link list
  49   void*         objects;        // Linked list of free objects
  50   unsigned int  refcount : 16;  // Number of non-free objects
  51   unsigned int  sizeclass : 8;  // Size-class for small objects (or 0)
  52   unsigned int  location : 2;   // Is the span on a freelist, and if so, which?
  53   unsigned int  sample : 1;     // Sampled object?
  54
  55 #undef SPAN_HISTORY
  56 #ifdef SPAN_HISTORY
  57   // For debugging, we can keep a log events per span
  58   int nexthistory;
  59   char history[64];
  60   int value[64];
  61 #endif
  62
  63   // What freelist the span is on: IN_USE if on none, or normal or returned
  64   enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };
  65 };
  66
  67 #ifdef SPAN_HISTORY
  68 void Event(Span* span, char op, int v = 0);
  69 #else
  70 #define Event(s,o,v) ((void) 0)
  71 #endif
  72
  73 // Allocator/deallocator for spans
  74 Span* NewSpan(PageID p, Length len);
  75 void DeleteSpan(Span* span);
  76
  77 // -------------------------------------------------------------------------
  78 // Doubly linked list of spans.
  79 // -------------------------------------------------------------------------
  80
  81 // Initialize *list to an empty list.
  82 void DLL_Init(Span* list);
  83
  84 // Remove 'span' from the linked list in which it resides, updating the
  85 // pointers of adjacent Spans and setting span's next and prev to NULL.
  86 void DLL_Remove(Span* span);
  87
  88 // Return true iff "list" is empty.
  89 inline bool DLL_IsEmpty(const Span* list) {
  90   return list->next == list;
  91 }
  92
  93 // Add span to the front of list.
  94 void DLL_Prepend(Span* list, Span* span);
  95
  96 // Return the length of the linked list. O(n)
  97 int DLL_Length(const Span* list);
  98
  99 }  // namespace tcmalloc
 100
 101 #endif  // TCMALLOC_SPAN_H_