free_list.h revision 5821806d5e7f356e8fa4b058a389a808ea183019
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 declarations of functions that implement doubly
34// linked lists and definitions of functions that implement singly
35// linked lists.  It also contains macros to tell the SizeMap class
36// how much space a node in the freelist needs so that SizeMap can
37// create large enough size classes.
38
39#ifndef TCMALLOC_FREE_LIST_H_
40#define TCMALLOC_FREE_LIST_H_
41
42#include <stddef.h>
43#include "internal_logging.h"
44#include "linked_list.h"
45
46// Remove to enable singly linked lists (the default for open source tcmalloc).
47#define TCMALLOC_USE_DOUBLYLINKED_FREELIST
48
49namespace tcmalloc {
50
51#if defined(TCMALLOC_USE_DOUBLYLINKED_FREELIST)
52
53// size class information for common.h.
54static const bool kSupportsDoublyLinkedList = true;
55
56void *FL_Next(void *t);
57void FL_Init(void *t);
58void FL_Push(void **list, void *element);
59void *FL_Pop(void **list);
60void FL_PopRange(void **head, int n, void **start, void **end);
61void FL_PushRange(void **head, void *start, void *end);
62size_t FL_Size(void *head);
63
64#else // TCMALLOC_USE_DOUBLYLINKED_FREELIST not defined
65static const bool kSupportsDoublyLinkedList = false;
66
67inline void *FL_Next(void *t) {
68  return SLL_Next(t);
69}
70
71inline void FL_Init(void *t) {
72  SLL_SetNext(t, NULL);
73}
74
75inline void FL_Push(void **list, void *element) {
76  if(*list != element) {
77    SLL_Push(list,element);
78    return;
79  }
80  Log(kCrash, __FILE__, __LINE__, "Double Free of %p detected", element);
81}
82
83inline void *FL_Pop(void **list) {
84  return SLL_Pop(list);
85}
86
87// Removes |N| elements from a linked list to which |head| points.
88// |head| will be modified to point to the new |head|.  |start| and
89// |end| will point to the first and last nodes of the range.  Note
90// that |end| will point to NULL after this function is called.
91inline void FL_PopRange(void **head, int n, void **start, void **end) {
92  SLL_PopRange(head, n, start, end);
93}
94
95inline void FL_PushRange(void **head, void *start, void *end) {
96  SLL_PushRange(head,start,end);
97}
98
99inline size_t FL_Size(void *head) {
100  return SLL_Size(head);
101}
102
103#endif // TCMALLOC_USE_DOUBLYLINKED_FREELIST
104
105} // namespace tcmalloc
106
107#endif // TCMALLOC_FREE_LIST_H_
108