git.saurik.com Git - apple/libc.git/blob - libdarwin/dirstat

1 /*

4 *

5 * This code is derived from software contributed to Berkeley by

6 * Chris Newcomb.

7 *

8 * Redistribution and use in source and binary forms, with or without

9 * modification, are permitted provided that the following conditions

10 * are met:

11 * 1. Redistributions of source code must retain the above copyright

12 * notice, this list of conditions and the following disclaimer.

13 * 2. Redistributions in binary form must reproduce the above copyright

14 * notice, this list of conditions and the following disclaimer in the

15 * documentation and/or other materials provided with the distribution.

16 * 3. All advertising materials mentioning features or use of this software

17 * must display the following acknowledgement:

18 * This product includes software developed by the University of

19 * California, Berkeley and its contributors.

20 * 4. Neither the name of the University nor the names of its contributors

21 * may be used to endorse or promote products derived from this software

22 * without specific prior written permission.

23 *

24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

34 * SUCH DAMAGE.

35 */

36 /*

38 *

39 * @APPLE_LICENSE_HEADER_START@

40 *

41 * This file contains Original Code and/or Modifications of Original Code

42 * as defined in and that are subject to the Apple Public Source License

43 * Version 2.0 (the 'License'). You may not use this file except in

44 * compliance with the License. Please obtain a copy of the License at

45 * http://www.opensource.apple.com/apsl/ and read it before using this

46 * file.

47 *

48 * The Original Code and all software distributed under the License are

49 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER

50 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,

51 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,

52 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.

53 * Please see the License for the specific language governing rights and

54 * limitations under the License.

55 *

56 * @APPLE_LICENSE_HEADER_END@

57 */

59 /*

60 * Taken from file_cmds:du.c

61 */

63 #include <stddef.h>

64 #include <stdlib.h>

65 #include <stdint.h>

66 #include "dirstat_collection.h"

68 struct fileid_entry {

69 struct fileid_entry *next;

70 struct fileid_entry *previous;

71 //int links;

72 uint64_t fileid;

73 };

76 struct dirstat_fileid_set_s {

77 struct fileid_entry **buckets;

78 struct fileid_entry *free_list;

79 size_t number_buckets;

80 unsigned long number_entries;

81 bool stop_allocating;

82 };

84 static const size_t links_hash_initial_size = 8192;

86 dirstat_fileid_set_t

87 _dirstat_fileid_set_create(void)

88 {

     dirstat_fileid_set_t ds = calloc(1, sizeof(dirstat_fileid_set_s));

90 ds->number_buckets = links_hash_initial_size;

         ds->buckets = calloc(ds->number_buckets, sizeof(ds->buckets[0]));

     if (ds->buckets == NULL) {

93 free(ds);

94 return NULL;

95 }

96 return ds;

97 }

99 void

100 _dirstat_fileid_set_destroy(dirstat_fileid_set_t ds)

101 {

102 struct fileid_entry *le;

     for (size_t i = 0; i < ds->number_buckets; i++) {

         while (ds->buckets[i] != NULL) {

105 le = ds->buckets[i];

             ds->buckets[i] = le->next;

107 free(le);

108 }

109 }

110 free(ds->buckets);

111 free(ds);

112 }

113

114 bool

 _dirstat_fileid_set_add(dirstat_fileid_set_t ds, uint64_t fileid)

116 {

117 struct fileid_entry *le, **new_buckets;

118 size_t i, new_size;

119 int hash;

120

121 /* If the hash table is getting too full, enlarge it. */

         if (ds->number_entries > ds->number_buckets * 10 && !ds->stop_allocating) {

                 new_size = ds->number_buckets * 2;

                 new_buckets = calloc(new_size, sizeof(struct fileid_entry *));

125

126 /* Try releasing the free list to see if that helps. */

                 if (new_buckets == NULL && ds->free_list != NULL) {

                         while (ds->free_list != NULL) {

129 le = ds->free_list;

130 ds->free_list = le->next;

131 free(le);

132 }

                         new_buckets = calloc(new_size, sizeof(new_buckets[0]));

134 }

135

136 if (new_buckets == NULL) {

137 ds->stop_allocating = 1;

138 } else {

                         for (i = 0; i < ds->number_buckets; i++) {

                                 while (ds->buckets[i] != NULL) {

141 /* Remove entry from old bucket. */

142 le = ds->buckets[i];

                                         ds->buckets[i] = le->next;

144

145 /* Add entry to new bucket. */

                                         hash = (int)(fileid % new_size);

147

                                         if (new_buckets[hash] != NULL)

149 new_buckets[hash]->previous =

150 le;

151 le->next = new_buckets[hash];

152 le->previous = NULL;

153 new_buckets[hash] = le;

154 }

155 }

156 free(ds->buckets);

157 ds->buckets = new_buckets;

158 ds->number_buckets = new_size;

159 }

160 }

161

162 /* Try to locate this entry in the hash table. */

         hash = (int)(fileid % ds->number_buckets);

         for (le = ds->buckets[hash]; le != NULL; le = le->next) {

                 if (le->fileid == fileid) {

166 #if 0 // TODO

167 /*

168 * Save memory by releasing an entry when we've seen

169 * all of its links.

170 */

                         if (--le->links <= 0) {

                                 if (le->previous != NULL)

                                         le->previous->next = le->next;

                                 if (le->next != NULL)

                                         le->next->previous = le->previous;

                                 if (buckets[hash] == le)

177 buckets[hash] = le->next;

178 number_entries--;

179 /* Recycle this node through the free list */

180 if (stop_allocating) {

181 free(le);

182 } else {

183 le->next = free_list;

184 free_list = le;

185 }

186 }

187 #endif

188 return true;

189 }

190 }

191

192 if (ds->stop_allocating)

193 return false;

194

195 /* Add this entry to the links cache. */

         if (ds->free_list != NULL) {

197 /* Pull a node from the free list if we can. */

198 le = ds->free_list;

199 ds->free_list = le->next;

200 } else {

201 /* Malloc one if we have to. */

                 le = malloc(sizeof(struct fileid_entry));

203 }

204 if (le == NULL) {

205 ds->stop_allocating = 1;

206 return false;

207 }

208 le->fileid = fileid;

209 ds->number_entries++;

         le->next = ds->buckets[hash];

211 le->previous = NULL;

         if (ds->buckets[hash] != NULL)

                 ds->buckets[hash]->previous = le;

214 ds->buckets[hash] = le;

215 return false;

216 }