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.
FL_PopRange(void ** head,int n,void ** start,void ** end)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.
FL_PushRange(void ** head,void * start,void * end)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|.
FL_Size(void * 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
FL_SetNext(void * t,void * n)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