third_party/tcmalloc/chromium/src/free_list.cc

   1 // Copyright (c) 2011, 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: Rebecca Shapiro <bxx@google.com>
  32 //
  33 // This file contains functions that implement doubly linked and
  34 // singly linked lists.  The singly linked lists are null terminated,
  35 // use raw pointers to link neighboring elements, and these pointers
  36 // are stored at the start of each element, independently of the
  37 // elements's size.  Because pointers are stored within each element,
  38 // each element must be large enough to store two raw pointers if
  39 // doubly linked lists are employed, or one raw pointer if singly
  40 // linked lists are employed.  On machines with 64 bit pointers, this
  41 // means elements must be at least 16 bytes in size for doubly linked
  42 // list support, and 8 bytes for singly linked list support.  No
  43 // attempts are made to preserve the data in elements stored in the
  44 // list.
  45 //
  46 // Given a machine with pointers of size N (on a 64bit machine N=8, on
  47 // a 32bit machine, N=4), the list pointers are stored in the
  48 // following manner:
  49 // -In doubly linked lists, the |next| pointer is stored in the first N
  50 // bytes of the node and the |previous| pointer is writtend into the
  51 // second N bytes.
  52 // -In singly linked lists, the |next| pointer is stored in the first N
  53 // bytes of the node.
  54 //
  55 // For both types of lists: when a pop operation is performed on a non
  56 // empty list, the new list head becomes that which is pointed to by
  57 // the former head's |next| pointer.  If the list is doubly linked, the
  58 // new head |previous| pointer gets changed from pointing to the former
  59 // head to NULL.
  60
  61
  62 #include <limits>
  63 #include <stddef.h>
  64 #include "free_list.h"
  65
  66 #if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST)
  67
  68 namespace tcmalloc {
  69
  70 // Remove |n| elements from linked list at whose first element is at
  71 // |*head|.  |head| will be modified to point to the new head.
  72 // |start| will point to the first node of the range, |end| will point
  73 // to the last node in the range. |n| must be <= FL_Size(|*head|)
  74 // If |n| > 0, |head| must not be NULL.
  75 void FL_PopRange(void **head, int n, void **start, void **end) {
  76   if (n == 0) {
  77     *start = NULL;
  78     *end = NULL;
  79     return;
  80   }
  81
  82   *start = *head; // Remember the first node in the range.
  83   void *tmp = *head;
  84   for (int i = 1; i < n; ++i) { // Find end of range.
  85     tmp = FL_Next(tmp);
  86   }
  87   *end = tmp; // |end| now set to point to last node in range.
  88   *head = FL_Next(*end);
  89   FL_SetNext(*end, NULL); // Unlink range from list.
  90
  91   if (*head ) { // Fixup popped list.
  92     FL_SetPrevious(*head, NULL);
  93   }
  94 }
  95
  96 // Pushes the nodes in the list begginning at |start| whose last node
  97 // is |end| into the linked list at |*head|. |*head| is updated to
  98 // point be the new head of the list.  |head| must not be NULL.
  99 void FL_PushRange(void **head, void *start, void *end) {
 100   if (!start) return;
 101
 102   // Sanity checking of ends of list to push is done by calling
 103   // FL_Next and FL_Previous.
 104   FL_Next(start);
 105   FL_Previous(end);
 106   ASSERT(FL_Previous_No_Check(start) == NULL);
 107   ASSERT(FL_Next_No_Check(end) == NULL);
 108
 109   if (*head) {
 110     FL_EqualityCheck(FL_Previous_No_Check(*head), (void*)NULL,
 111                      __FILE__, __LINE__);
 112     FL_SetNext(end, *head);
 113     FL_SetPrevious(*head, end);
 114   }
 115   *head = start;
 116 }
 117
 118 // Calculates the size of the list that begins at |head|.
 119 size_t FL_Size(void *head){
 120   int count = 0;
 121   if (head) {
 122     FL_EqualityCheck(FL_Previous_No_Check(head), (void*)NULL,
 123                      __FILE__, __LINE__);
 124   }
 125   while (head) {
 126     count++;
 127     head = FL_Next(head);
 128   }
 129   return count;
 130 }
 131
 132 } // namespace tcmalloc
 133
 134 #else
 135 #include "linked_list.h" // for SLL_SetNext
 136
 137 namespace {
 138
 139 inline void FL_SetNext(void *t, void *n) {
 140   tcmalloc::SLL_SetNext(t,n);
 141 }
 142
 143 }
 144
 145 #endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST