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
68namespace 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.
75void 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.
99void 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|.
119size_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
137namespace {
138
139inline void FL_SetNext(void *t, void *n) {
140  tcmalloc::SLL_SetNext(t,n);
141}
142
143}
144
145#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
146