1 // Copyright (c) 2008, 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: Sanjay Ghemawat <opensource (at) google.com> 32 // 33 // Some very basic linked list functions for dealing with using void * as 34 // storage. 35 36 #ifndef TCMALLOC_LINKED_LIST_H_ 37 #define TCMALLOC_LINKED_LIST_H_ 38 39 #include <stddef.h> 40 41 namespace tcmalloc { 42 43 inline void *SLL_Next(void *t) { 44 return *(reinterpret_cast<void**>(t)); 45 } 46 47 inline void SLL_SetNext(void *t, void *n) { 48 *(reinterpret_cast<void**>(t)) = n; 49 } 50 51 inline void SLL_Push(void **list, void *element) { 52 SLL_SetNext(element, *list); 53 *list = element; 54 } 55 56 inline void *SLL_Pop(void **list) { 57 void *result = *list; 58 *list = SLL_Next(*list); 59 return result; 60 } 61 62 // Remove N elements from a linked list to which head points. head will be 63 // modified to point to the new head. start and end will point to the first 64 // and last nodes of the range. Note that end will point to NULL after this 65 // function is called. 66 inline void SLL_PopRange(void **head, int N, void **start, void **end) { 67 if (N == 0) { 68 *start = NULL; 69 *end = NULL; 70 return; 71 } 72 73 void *tmp = *head; 74 for (int i = 1; i < N; ++i) { 75 tmp = SLL_Next(tmp); 76 } 77 78 *start = *head; 79 *end = tmp; 80 *head = SLL_Next(tmp); 81 // Unlink range from list. 82 SLL_SetNext(tmp, NULL); 83 } 84 85 inline void SLL_PushRange(void **head, void *start, void *end) { 86 if (!start) return; 87 SLL_SetNext(end, *head); 88 *head = start; 89 } 90 91 inline size_t SLL_Size(void *head) { 92 int count = 0; 93 while (head) { 94 count++; 95 head = SLL_Next(head); 96 } 97 return count; 98 } 99 100 } // namespace tcmalloc 101 102 #endif // TCMALLOC_LINKED_LIST_H_ 103