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 (at) 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 146
