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