doubly-linked free-lists for thread caches and page heaps

third_party/tcmalloc/chromium/src/free_list.h

+// Copyright (c) 2011, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// --- Author: Rebecca Shapiro <bxx@google.com>
+
+// This file contains declarations of functions that implement doubly
+// linked lists and definitions of functions that implement singly
+// linked lists.  The singly linked lists are null terminated, use raw
+// pointers to link neighboring elements, and these pointers are
+// stored at the start of each element, independently of the
+// elements's size.  Because pointers are stored within each element,
+// each element must be large enough to store two raw pointers if
+// doubly linked lists are employed, or one raw pointer if singly
+// linked lists are employed.  On machines with 64 bit pointers, this
+// means elements must be at least 16 bytes in size for doubly linked
+// list support, and 8 bytes for singly linked list support.  No
+// attempts are made to preserve the data in elements stored in the
+// list.
+//
+// Given a machine with pointers of size N (on a 64bit machine N=8, on
+// a 32bit machine, N=4), the list pointers are stored in the
+// following manner:
+// -In doubly linked lists, the |next| pointer is stored in the first N
+// bytes of the node and the |previous| pointer is writtend into the
+// second N bytes.
+// -In singly linked lists, the |next| pointer is stored in the first N
+// bytes of the node.
+//
+// For both types of lists: when a pop operation is performed on a non
+// empty list, the new list head becomes that which is pointed to by
+// the former head's |next| pointer.  If the list is doubly linked, the
+// new head |previous| pointer gets changed from pointing to the former
+// head to NULL.
+//
+// The original author of the singly liked list code is Sanjay
+// Ghemawat <opensource@google.com>.
+#ifndef TCMALLOC_FREE_LIST_H_
+#define TCMALLOC_FREE_LIST_H_
+
+#include <stddef.h>
+
+namespace tcmalloc {
+
+#ifdef TCMALLOC_USE_DOUBLYLINKED_FREELIST
+static const int kPointerSize = sizeof(void *);
+
+// size class information for common.h/common.cc.
+#if defined(_LP64) || defined(_WIN64)
+// 8 byte pointers require that min class size holds at least 16 bytes.
+#define HAS_64_BIT_POINTERS 1
+#define FIRST_NON_0_SIZE_CLASS 2
+#else
+#define HAS_64_BIT_POINTERS 0
+#define FIRST_NON_0_SIZE_CLASS 1
+#endif
+
+void *FL_Previous(void *t);
+void *FL_Next(void *t);
+void *FL_SetPrevious(void *t, void *n);
+void *FL_SetNext(void *t, void *n);
+void FL_Init(void *t);
+void FL_Push(void **list, void *element);
+void *FL_Pop(void **list);
+void FL_PopRange(void **head, int N, void **start, void **end);

[jar (doing other things), 2011/08/26 18:56:29]

nit: even if the old code (below) used an upper case N, you should probably use
a lower case N in this new code.

[bxx, 2011/08/26 21:45:10]

Done.

+void FL_PushRange(void **head, void *start, void *end);
+
+#else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined
+
+// size class information for common.h/common.cc.
+#define HAS_64_BIT_POINTERS 0
+#define FIRST_NON_0_SIZE_CLASS 1
+
+inline void *FL_Next(void *t) {
+  return *(reinterpret_cast<void**>(t));
+}
+
+inline void FL_SetNext(void *t, void *n) {
+  *(reinterpret_cast<void**>(t)) = n;
+}
+
+inline void FL_Init(void *t) {
+  FL_SetNext(t, NULL);
+}
+
+inline void FL_Push(void **list, void *element) {
+  FL_SetNext(element, *list);
+  *list = element;
+}
+
+inline void *FL_Pop(void **list) {
+  void *result = *list;
+  *list = FL_Next(*list);
+  return result;
+}
+
+// Removes |N| elements from a linked list to which |head| points.
+// |head| will be modified to point to the new |head|.  |start| and
+// |end| will point to the first and last nodes of the range.  Note
+// that |end| will point to NULL after this function is called.
+inline void FL_PopRange(void **head, int N, void **start, void **end) {
+  if (N == 0) {
+    *start = NULL;
+    *end = NULL;
+    return;
+  }
+
+  *start = *head;
+  void *tmp = *head;
+  for (int i = 1; i < N; ++i) { // Find the |N|th element to pop.
+    tmp = FL_Next(tmp);
+  }
+  *end = tmp;
+
+  *head = FL_Next(tmp); // Unlink range from original list.
+  FL_SetNext(tmp, NULL);
+}
+
+inline void FL_PushRange(void **head, void *start, void *end) {
+  if (!start) return;
+  FL_SetNext(end, *head);
+  *head = start;
+}
+
+#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
+#define FIRST_NON_0_SIZE FIRST_NON_0_SIZE_CLASS * 2
+
+inline size_t FL_Size(void *head) {
+  int count = 0;
+  while (head) {
+    count++;
+    head = FL_Next(head);
+  }
+  return count;
+}
+
+} // namespace tcmalloc
+
+#endif // TCMALLOC_FREE_LIST_H_