1 #include <string.h>
2 #include <stdlib.h>
3 #include "lib/mlr_arch.h"
4 #include "lib/mlrutil.h"
5 #include "containers/slls.h"
6
7 // ----------------------------------------------------------------
slls_alloc()8 slls_t* slls_alloc() {
9 slls_t* plist = mlr_malloc_or_die(sizeof(slls_t));
10 plist->phead = NULL;
11 plist->ptail = NULL;
12 plist->length = 0;
13 return plist;
14 }
15
16 // ----------------------------------------------------------------
slls_size(slls_t * plist)17 int slls_size(slls_t* plist) {
18 return plist->length;
19 }
20
21 // ----------------------------------------------------------------
slls_copy(slls_t * pold)22 slls_t* slls_copy(slls_t* pold) {
23 slls_t* pnew = slls_alloc();
24 for (sllse_t* pe = pold->phead; pe != NULL; pe = pe->pnext)
25 slls_append_with_free(pnew, mlr_strdup_or_die(pe->value));
26 return pnew;
27 }
28
29 // ----------------------------------------------------------------
slls_free(slls_t * plist)30 void slls_free(slls_t* plist) {
31 if (plist == NULL)
32 return;
33 sllse_t* pnode = plist->phead;
34 while (pnode != NULL) {
35 sllse_t* pdel = pnode;
36 pnode = pnode->pnext;
37 if (pdel->free_flag & FREE_ENTRY_VALUE)
38 free(pdel->value);
39 free(pdel);
40 }
41 plist->phead = NULL;
42 plist->ptail = 0;
43 plist->length = 0;
44 free(plist);
45 }
46
47 // ----------------------------------------------------------------
slls_single_with_free(char * value)48 slls_t* slls_single_with_free(char* value) {
49 slls_t* pslls = slls_alloc();
50 slls_append_with_free(pslls, value);
51 return pslls;
52 }
53
54 // ----------------------------------------------------------------
slls_single_no_free(char * value)55 slls_t* slls_single_no_free(char* value) {
56 slls_t* pslls = slls_alloc();
57 slls_append_no_free(pslls, value);
58 return pslls;
59 }
60
61 // ----------------------------------------------------------------
slls_append(slls_t * plist,char * value,char free_flag)62 void slls_append(slls_t* plist, char* value, char free_flag) {
63 sllse_t* pnode = mlr_malloc_or_die(sizeof(sllse_t));
64 pnode->value = value;
65 pnode->free_flag = free_flag;
66
67 if (plist->ptail == NULL) {
68 pnode->pnext = NULL;
69 plist->phead = pnode;
70 plist->ptail = pnode;
71 } else {
72 pnode->pnext = NULL;
73 plist->ptail->pnext = pnode;
74 plist->ptail = pnode;
75 }
76 plist->length++;
77 }
78
slls_append_with_free(slls_t * plist,char * value)79 void slls_append_with_free(slls_t* plist, char* value) {
80 slls_append(plist, value, FREE_ENTRY_VALUE);
81 }
slls_append_no_free(slls_t * plist,char * value)82 void slls_append_no_free(slls_t* plist, char* value) {
83 slls_append(plist, value, 0);
84 }
85
86 // ----------------------------------------------------------------
slls_equals(slls_t * pa,slls_t * pb)87 int slls_equals(slls_t* pa, slls_t* pb) {
88 if (pa->length != pb->length)
89 return FALSE;
90 sllse_t* pea = pa->phead;
91 sllse_t* peb = pb->phead;
92 for ( ; pea != NULL && peb != NULL; pea = pea->pnext, peb = peb->pnext) {
93 if (!streq(pea->value, peb->value))
94 return FALSE;
95 }
96 return TRUE;
97 }
98
99 // ----------------------------------------------------------------
slls_from_line(char * line,char ifs,int allow_repeat_ifs)100 slls_t* slls_from_line(char* line, char ifs, int allow_repeat_ifs) {
101 slls_t* plist = slls_alloc();
102 if (*line == 0) // empty string splits to empty list
103 return plist;
104
105 char seps[2] = {ifs, 0};
106 char* sep = &seps[0];
107 int seplen = 1;
108 char* walker = line;
109 char* piece;
110 while ((piece = mlr_strmsep(&walker, sep, seplen)) != NULL) {
111 mlr_rstrip(piece); // https://github.com/johnkerl/miller/issues/313
112 slls_append_no_free(plist, piece);
113 }
114
115 return plist;
116 }
117
118 // ----------------------------------------------------------------
119 // This is inefficient and intended only for debug use.
slls_join(slls_t * plist,char * ofs)120 char* slls_join(slls_t* plist, char* ofs) {
121 unsigned long long len = 0;
122 for (sllse_t* pe = plist->phead; pe != NULL; pe = pe->pnext)
123 len += strlen(pe->value) + 1; // include space for ofs and null-terminator
124 char* output = mlr_malloc_or_die(len);
125 *output = 0;
126 for (sllse_t* pe = plist->phead; pe != NULL; pe = pe->pnext) {
127 strcat(output, pe->value);
128 if (pe->pnext != NULL) {
129 strcat(output, ofs);
130 }
131 }
132
133 return output;
134 }
135
slls_print(slls_t * plist)136 void slls_print(slls_t* plist) {
137 if (plist == NULL) {
138 printf("NULL");
139 } else {
140 unsigned long long i = 0;
141 for (sllse_t* pe = plist->phead; pe != NULL; pe = pe->pnext, i++) {
142 if (i > 0)
143 printf(",");
144 printf("%s", pe->value);
145 }
146 }
147 }
148
slls_print_quoted(slls_t * plist)149 void slls_print_quoted(slls_t* plist) {
150 if (plist == NULL) {
151 printf("NULL");
152 } else {
153 unsigned long long i = 0;
154 for (sllse_t* pe = plist->phead; pe != NULL; pe = pe->pnext, i++) {
155 if (i > 0)
156 printf(" ");
157 printf("\"%s\"", pe->value);
158 }
159 }
160 }
161
162 // ----------------------------------------------------------------
slls_reverse(slls_t * plist)163 void slls_reverse(slls_t* plist) {
164 if (plist->phead == NULL)
165 return;
166
167 sllse_t* pnewhead = NULL;
168 sllse_t* pnewtail = plist->phead;
169 sllse_t* p = plist->phead;
170 sllse_t* q = p->pnext;
171 while (1) {
172 p->pnext = pnewhead;
173 pnewhead = p;
174 if (q == NULL)
175 break;
176 p = q;
177 q = p->pnext;
178 }
179 plist->phead = pnewhead;
180 plist->ptail = pnewtail;
181 }
182
183 // ----------------------------------------------------------------
slls_hash_func(slls_t * plist)184 int slls_hash_func(slls_t *plist) {
185 unsigned long hash = 5381;
186 int c;
187
188 for (sllse_t* pe = plist->phead; pe != NULL; pe = pe->pnext) {
189 char* str = pe->value;
190 while ((c = *str++) != 0)
191 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
192 // So that ["ab","c"] doesn't hash to the same as ["a","bc"]:
193 hash = ((hash << 5) + hash) + ',';
194 }
195
196 return (int)hash;
197 }
198
199 // ----------------------------------------------------------------
slls_compare_lexically(slls_t * pa,slls_t * pb)200 int slls_compare_lexically(slls_t* pa, slls_t* pb) {
201 sllse_t* pe = pa->phead;
202 sllse_t* pf = pb->phead;
203 while (TRUE) {
204 if (pe == NULL && pf == NULL)
205 return 0;
206 if (pe == NULL)
207 return 1;
208 if (pf == NULL)
209 return -1;
210 int rc = strcmp(pe->value, pf->value);
211 if (rc != 0)
212 return rc;
213 pe = pe->pnext;
214 pf = pf->pnext;
215 }
216 }
217
218 // ----------------------------------------------------------------
sllse_vcmp(const void * pva,const void * pvb)219 static int sllse_vcmp(const void* pva, const void* pvb) {
220 const sllse_t** pa = (const sllse_t**)pva;
221 const sllse_t** pb = (const sllse_t**)pvb;
222 return strcmp((*pa)->value, (*pb)->value);
223 }
224
slls_sort(slls_t * plist)225 void slls_sort(slls_t* plist) {
226 if (plist->length < 2)
227 return;
228
229 unsigned long long i;
230 sllse_t* pe;
231
232 // Copy to array
233 sllse_t** node_array = mlr_malloc_or_die(sizeof(sllse_t*) * plist->length);
234 for (i = 0, pe = plist->phead; pe != NULL; i++, pe = pe->pnext)
235 node_array[i] = pe;
236
237 // Sort the array
238 qsort(node_array, plist->length, sizeof(sllse_t*), sllse_vcmp);
239
240 // Copy back
241 plist->phead = node_array[0];
242 plist->ptail = node_array[plist->length - 1];
243 for (i = 1; i < plist->length; i++) {
244 node_array[i-1]->pnext = node_array[i];
245 }
246 plist->ptail->pnext = NULL;
247
248 free(node_array);
249 }
250