1 /*
2  * Copyright (c) 2004-2006 Hyperic, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "sigar.h"
18 #include "sigar_private.h"
19 #include "sigar_util.h"
20 #include <stdio.h>
21 /*
22  * hash table to cache values where key is a unique number
23  * such as:
24  *  pid -> some process data
25  *  uid -> user name
26  *  gid -> group name
27  */
28 
29 #define ENTRIES_SIZE(n) \
30     (sizeof(sigar_cache_entry_t *) * (n))
31 
32 /* wrap free() for use w/ dmalloc */
free_value(void *ptr)33 static void free_value(void *ptr)
34 {
35     free(ptr);
36 }
37 
sigar_cache_new(int size)38 sigar_cache_t *sigar_cache_new(int size)
39 {
40     sigar_cache_t *table = malloc(sizeof(*table));
41     table->count = 0;
42     table->size = size;
43     table->entries = malloc(ENTRIES_SIZE(size));
44     memset(table->entries, '\0', ENTRIES_SIZE(size));
45     table->free_value = free_value;
46     return table;
47 }
48 
49 #ifdef DEBUG_CACHE
50 /* see how well entries are distributed */
sigar_cache_dump(sigar_cache_t *table)51 static void sigar_cache_dump(sigar_cache_t *table)
52 {
53     int i;
54     sigar_cache_entry_t **entries = table->entries;
55 
56     for (i=0; i<table->size; i++) {
57         sigar_cache_entry_t *entry = *entries++;
58 
59         printf("|");
60         while (entry) {
61             printf("%lld", entry->id);
62             if (entry->next) {
63                 printf(",");
64             }
65             entry = entry->next;
66         }
67     }
68     printf("\n");
69     fflush(stdout);
70 }
71 #endif
72 
sigar_cache_rehash(sigar_cache_t *table)73 static void sigar_cache_rehash(sigar_cache_t *table)
74 {
75     int i;
76     unsigned int new_size = table->size * 2 + 1;
77     sigar_cache_entry_t **entries = table->entries;
78     sigar_cache_entry_t **new_entries =
79         malloc(ENTRIES_SIZE(new_size));
80 
81     memset(new_entries, '\0', ENTRIES_SIZE(new_size));
82 
83     for (i=0; i<table->size; i++) {
84         sigar_cache_entry_t *entry = *entries++;
85 
86         while (entry) {
87             sigar_cache_entry_t *next = entry->next;
88             sigar_uint64_t hash = entry->id % new_size;
89 
90             entry->next = new_entries[hash];
91             new_entries[hash] = entry;
92             entry = next;
93         }
94     }
95 
96     free(table->entries);
97     table->entries = new_entries;
98     table->size = new_size;
99 }
100 
101 #define SIGAR_CACHE_IX(t, k) \
102     t->entries + (k % t->size)
103 
sigar_cache_find(sigar_cache_t *table, sigar_uint64_t key)104 sigar_cache_entry_t *sigar_cache_find(sigar_cache_t *table,
105                                       sigar_uint64_t key)
106 {
107     sigar_cache_entry_t *entry, **ptr;
108 
109     for (ptr = SIGAR_CACHE_IX(table, key), entry = *ptr;
110          entry;
111          ptr = &entry->next, entry = *ptr)
112     {
113         if (entry->id == key) {
114             return entry;
115         }
116     }
117 
118     return NULL;
119 }
120 
121 /* create entry if it does not exist */
sigar_cache_get(sigar_cache_t *table, sigar_uint64_t key)122 sigar_cache_entry_t *sigar_cache_get(sigar_cache_t *table,
123                                      sigar_uint64_t key)
124 {
125     sigar_cache_entry_t *entry, **ptr;
126 
127     for (ptr = SIGAR_CACHE_IX(table, key), entry = *ptr;
128          entry;
129          ptr = &entry->next, entry = *ptr)
130     {
131         if (entry->id == key) {
132             return entry;
133         }
134     }
135 
136     if (table->count++ > table->size) {
137         sigar_cache_rehash(table);
138 
139         for (ptr = SIGAR_CACHE_IX(table, key), entry = *ptr;
140              entry;
141              ptr = &entry->next, entry = *ptr)
142         {
143         }
144     }
145 
146     *ptr = entry = malloc(sizeof(*entry));
147     entry->id = key;
148     entry->value = NULL;
149     entry->next = NULL;
150 
151     return entry;
152 }
153 
sigar_cache_destroy(sigar_cache_t *table)154 void sigar_cache_destroy(sigar_cache_t *table)
155 {
156     int i;
157     sigar_cache_entry_t **entries = table->entries;
158 
159 #ifdef DEBUG_CACHE
160     sigar_cache_dump(table);
161 #endif
162 
163     for (i=0; i<table->size; i++) {
164         sigar_cache_entry_t *entry, *ptr;
165         entry = *entries++;
166 
167         while (entry) {
168             if (entry->value) {
169                 table->free_value(entry->value);
170             }
171             ptr = entry->next;
172             free(entry);
173             entry = ptr;
174         }
175     }
176 
177     free(table->entries);
178     free(table);
179 }
180