1 /* Copyright (c) 2000-2009, The Johns Hopkins University
2 * All rights reserved.
3 *
4 * The contents of this file are subject to a license (the ``License'').
5 * You may not use this file except in compliance with the License. The
6 * specific language governing the rights and limitations of the License
7 * can be found in the file ``STDUTIL_LICENSE'' found in this
8 * distribution.
9 *
10 * Software distributed under the License is distributed on an AS IS
11 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.
12 *
13 * The Original Software is:
14 * The Stdutil Library
15 *
16 * Contributors:
17 * Creator - John Lane Schultz (jschultz@cnds.jhu.edu)
18 * The Center for Networking and Distributed Systems
19 * (CNDS - http://www.cnds.jhu.edu)
20 */
21
22 #include <stdutil/stderror.h>
23 #include <stdutil/stdit.h>
24 #include <stdutil/stdarr.h>
25 #include <stdutil/stdcarr.h>
26 #include <stdutil/stddll.h>
27 #include <stdutil/stdhash.h>
28 #include <stdutil/stdskl.h>
29
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33
34 /************************************************************************************************
35 * stdit_get_type: Get the functional type of an iterator.
36 ***********************************************************************************************/
37
stdit_get_type(const stdit * it)38 STDINLINE stdit_type stdit_get_type(const stdit *it)
39 {
40 stdit_type ret;
41
42 switch (it->type_id) {
43 case STDPTR_IT_ID:
44 case STDPPTR_IT_ID:
45 case STDARR_IT_ID:
46 case STDCARR_IT_ID:
47 ret = STDIT_RANDOM_ACCESS;
48 break;
49
50 case STDDLL_IT_ID:
51 case STDHASH_IT_ID:
52 case STDHASH_IT_KEY_ID:
53 case STDSKL_IT_ID:
54 case STDSKL_IT_KEY_ID:
55 ret = STDIT_BIDIRECTIONAL;
56 break;
57
58 default:
59 ret = (stdit_type) 0;
60 STDEXCEPTION(uninitialized or corrupted iterator);
61 break;
62 }
63
64 return ret;
65 }
66
67 /************************************************************************************************
68 * stdit_key: Get the key of a key-value pair from an iterator.
69 ***********************************************************************************************/
70
stdit_key(const stdit * it)71 STDINLINE const void *stdit_key(const stdit *it)
72 {
73 const void * ret;
74
75 switch (it->type_id) {
76 case STDPTR_IT_ID:
77 case STDARR_IT_ID:
78 case STDCARR_IT_ID:
79 case STDDLL_IT_ID:
80 ret = NULL;
81 break;
82
83 case STDPPTR_IT_ID:
84 ret = it->impl.pptr.key;
85 break;
86
87 case STDHASH_IT_ID:
88 case STDHASH_IT_KEY_ID:
89 ret = stdhash_it_key(it);
90 break;
91
92 case STDSKL_IT_ID:
93 case STDSKL_IT_KEY_ID:
94 ret = stdskl_it_key(it);
95 break;
96
97 default:
98 ret = NULL;
99 STDEXCEPTION(uninitialized or corrupted iterator);
100 break;
101 }
102
103 return ret;
104 }
105
106 /************************************************************************************************
107 * stdit_key_size: Get the size in bytes of the key type 'it' references.
108 ***********************************************************************************************/
109
stdit_key_size(const stdit * it)110 STDINLINE stdsize stdit_key_size(const stdit *it)
111 {
112 stdsize ret;
113
114 switch (it->type_id) {
115 case STDPTR_IT_ID:
116 case STDARR_IT_ID:
117 case STDCARR_IT_ID:
118 case STDDLL_IT_ID:
119 ret = 0;
120 break;
121
122 case STDPPTR_IT_ID:
123 ret = it->impl.pptr.ksize;
124 break;
125
126 case STDHASH_IT_ID:
127 case STDHASH_IT_KEY_ID:
128 ret = stdhash_it_key_size(it);
129 break;
130
131 case STDSKL_IT_ID:
132 case STDSKL_IT_KEY_ID:
133 ret = stdskl_it_key_size(it);
134 break;
135
136 default:
137 ret = 0;
138 STDEXCEPTION(uninitialized or corrupted iterator);
139 break;
140 }
141
142 return ret;
143 }
144
145 /************************************************************************************************
146 * stdit_val: Get the value that 'it' references.
147 ***********************************************************************************************/
148
stdit_val(const stdit * it)149 STDINLINE void *stdit_val(const stdit *it)
150 {
151 void * ret;
152
153 switch (it->type_id) {
154 case STDPTR_IT_ID:
155 ret = it->impl.ptr.val;
156 break;
157
158 case STDPPTR_IT_ID:
159 ret = it->impl.pptr.val;
160 break;
161
162 case STDARR_IT_ID:
163 ret = stdarr_it_val(it);
164 break;
165
166 case STDCARR_IT_ID:
167 ret = stdcarr_it_val(it);
168 break;
169
170 case STDDLL_IT_ID:
171 ret = stddll_it_val(it);
172 break;
173
174 case STDHASH_IT_ID:
175 case STDHASH_IT_KEY_ID:
176 ret = stdhash_it_val(it);
177 break;
178
179 case STDSKL_IT_ID:
180 case STDSKL_IT_KEY_ID:
181 ret = stdskl_it_val(it);
182 break;
183
184 default:
185 ret = NULL;
186 STDEXCEPTION(uninitialized or corrupted iterator);
187 break;
188 }
189
190 return ret;
191 }
192
193 /************************************************************************************************
194 * stdit_val_size: Get the size in bytes of the value 'it' references.
195 ***********************************************************************************************/
196
stdit_val_size(const stdit * it)197 STDINLINE stdsize stdit_val_size(const stdit *it)
198 {
199 stdsize ret;
200
201 switch (it->type_id) {
202 case STDPTR_IT_ID:
203 ret = it->impl.ptr.vsize;
204 break;
205
206 case STDPPTR_IT_ID:
207 ret = it->impl.pptr.vsize;
208 break;
209
210 case STDARR_IT_ID:
211 ret = stdarr_it_val_size(it);
212 break;
213
214 case STDCARR_IT_ID:
215 ret = stdcarr_it_val_size(it);
216 break;
217
218 case STDDLL_IT_ID:
219 ret = stddll_it_val_size(it);
220 break;
221
222 case STDHASH_IT_ID:
223 case STDHASH_IT_KEY_ID:
224 ret = stdhash_it_val_size(it);
225 break;
226
227 case STDSKL_IT_ID:
228 case STDSKL_IT_KEY_ID:
229 ret = stdskl_it_val_size(it);
230 break;
231
232 default:
233 ret = 0;
234 STDEXCEPTION(uninitialized or corrupted iterator);
235 break;
236 }
237
238 return ret;
239 }
240
241 /************************************************************************************************
242 * stdit_eq: Compare two iterators for equality (reference same element).
243 ***********************************************************************************************/
244
stdit_eq(const stdit * it1,const stdit * it2)245 STDINLINE stdbool stdit_eq(const stdit *it1, const stdit *it2)
246 {
247 stdbool ret;
248
249 STDSAFETY_CHECK(it1->type_id == it2->type_id);
250
251 switch (it1->type_id) {
252 case STDPTR_IT_ID:
253 STDSAFETY_CHECK(it1->impl.ptr.vsize == it2->impl.ptr.vsize);
254 ret = (it1->impl.ptr.val == it2->impl.ptr.val);
255 break;
256
257 case STDPPTR_IT_ID:
258 STDSAFETY_CHECK(it1->impl.pptr.ksize == it2->impl.pptr.ksize && it1->impl.pptr.vsize == it2->impl.pptr.vsize);
259 ret = (it1->impl.pptr.key == it2->impl.pptr.key && it1->impl.pptr.val == it2->impl.pptr.val);
260 break;
261
262 case STDARR_IT_ID:
263 ret = stdarr_it_eq(it1, it2);
264 break;
265
266 case STDCARR_IT_ID:
267 ret = stdcarr_it_eq(it1, it2);
268 break;
269
270 case STDDLL_IT_ID:
271 ret = stddll_it_eq(it1, it2);
272 break;
273
274 case STDHASH_IT_ID:
275 case STDHASH_IT_KEY_ID:
276 ret = stdhash_it_eq(it1, it2);
277 break;
278
279 case STDSKL_IT_ID:
280 case STDSKL_IT_KEY_ID:
281 ret = stdskl_it_eq(it1, it2);
282 break;
283
284 default:
285 ret = STDFALSE;
286 STDEXCEPTION(uninitialized or corrupted iterator);
287 break;
288 }
289
290 return ret;
291 }
292
293 /************************************************************************************************
294 * stdit_next: Advance an iterator towards "end" by one position.
295 ***********************************************************************************************/
296
stdit_next(stdit * it)297 STDINLINE stdit *stdit_next(stdit *it)
298 {
299 switch (it->type_id) {
300 case STDPTR_IT_ID:
301 it->impl.ptr.val += it->impl.ptr.vsize;
302 break;
303
304 case STDPPTR_IT_ID:
305 it->impl.pptr.key += it->impl.pptr.ksize;
306 it->impl.pptr.val += it->impl.pptr.vsize;
307 break;
308
309 case STDARR_IT_ID:
310 stdarr_it_next(it);
311 break;
312
313 case STDCARR_IT_ID:
314 stdcarr_it_next(it);
315 break;
316
317 case STDDLL_IT_ID:
318 stddll_it_next(it);
319 break;
320
321 case STDHASH_IT_ID:
322 case STDHASH_IT_KEY_ID:
323 stdhash_it_next(it);
324 break;
325
326 case STDSKL_IT_ID:
327 case STDSKL_IT_KEY_ID:
328 stdskl_it_next(it);
329 break;
330
331 default:
332 STDEXCEPTION(uninitialized or corrupted iterator);
333 break;
334 }
335
336 return it;
337 }
338
339 /************************************************************************************************
340 * stdit_advance: Advance an iterator towards "end" by num_advance positions.
341 ***********************************************************************************************/
342
stdit_advance(stdit * it,stdsize num_advance)343 STDINLINE stdit *stdit_advance(stdit *it, stdsize num_advance)
344 {
345 switch (it->type_id) {
346 case STDPTR_IT_ID:
347 it->impl.ptr.val += it->impl.ptr.vsize * num_advance;
348 break;
349
350 case STDPPTR_IT_ID:
351 it->impl.pptr.key += it->impl.pptr.ksize * num_advance;
352 it->impl.pptr.val += it->impl.pptr.vsize * num_advance;
353 break;
354
355 case STDARR_IT_ID:
356 stdarr_it_advance(it, num_advance);
357 break;
358
359 case STDCARR_IT_ID:
360 stdcarr_it_advance(it, num_advance);
361 break;
362
363 case STDDLL_IT_ID:
364 stddll_it_advance(it, num_advance);
365 break;
366
367 case STDHASH_IT_ID:
368 case STDHASH_IT_KEY_ID:
369 stdhash_it_advance(it, num_advance);
370 break;
371
372 case STDSKL_IT_ID:
373 case STDSKL_IT_KEY_ID:
374 stdskl_it_advance(it, num_advance);
375 break;
376
377 default:
378 STDEXCEPTION(uninitialized or corrupted iterator);
379 break;
380 }
381
382 return it;
383 }
384
385 /************************************************************************************************
386 * stdit_distance: Calculate the distance from b to e.
387 ***********************************************************************************************/
388
stdit_distance(const stdit * b,const stdit * e)389 STDINLINE stdssize stdit_distance(const stdit *b, const stdit *e)
390 {
391 stdsize ret = 0;
392 stdit curr = *b;
393
394 switch (b->type_id) {
395 case STDPTR_IT_ID:
396 case STDPPTR_IT_ID:
397 case STDARR_IT_ID:
398 case STDCARR_IT_ID:
399 ret = stdit_cmp(e, b);
400 break;
401
402 case STDDLL_IT_ID:
403 for (; !stddll_it_eq(&curr, e); stddll_it_next(&curr), ++ret);
404 break;
405
406 case STDHASH_IT_ID:
407 case STDHASH_IT_KEY_ID:
408 for (; !stdhash_it_eq(&curr, e); stdhash_it_next(&curr), ++ret);
409 break;
410
411 case STDSKL_IT_ID:
412 case STDSKL_IT_KEY_ID:
413 for (; !stdskl_it_eq(&curr, e); stdskl_it_next(&curr), ++ret);
414 break;
415
416 default:
417 STDEXCEPTION(uninitialized or corrupted iterator);
418 break;
419 }
420
421 return ret;
422 }
423
424 /************************************************************************************************
425 * stdit_prev: Advance an iterator towards "begin" by one position.
426 ***********************************************************************************************/
427
stdit_prev(stdit * it)428 STDINLINE stdit *stdit_prev(stdit *it)
429 {
430 switch (it->type_id) {
431 case STDPTR_IT_ID:
432 it->impl.ptr.val -= it->impl.ptr.vsize;
433 break;
434
435 case STDPPTR_IT_ID:
436 it->impl.pptr.key -= it->impl.pptr.ksize;
437 it->impl.pptr.val -= it->impl.pptr.vsize;
438 break;
439
440 case STDARR_IT_ID:
441 stdarr_it_prev(it);
442 break;
443
444 case STDCARR_IT_ID:
445 stdcarr_it_prev(it);
446 break;
447
448 case STDDLL_IT_ID:
449 stddll_it_prev(it);
450 break;
451
452 case STDHASH_IT_ID:
453 case STDHASH_IT_KEY_ID:
454 stdhash_it_prev(it);
455 break;
456
457 case STDSKL_IT_ID:
458 case STDSKL_IT_KEY_ID:
459 stdskl_it_prev(it);
460 break;
461
462 default:
463 STDEXCEPTION(uninitialized or corrupted iterator);
464 break;
465 }
466
467 return it;
468 }
469
470 /************************************************************************************************
471 * stdit_retreat: Advance an iterator towards "begin" by num_retreat positions.
472 ***********************************************************************************************/
473
stdit_retreat(stdit * it,stdsize num_retreat)474 STDINLINE stdit *stdit_retreat(stdit *it, stdsize num_retreat)
475 {
476 switch (it->type_id) {
477 case STDPTR_IT_ID:
478 it->impl.ptr.val -= it->impl.ptr.vsize * num_retreat;
479 break;
480
481 case STDPPTR_IT_ID:
482 it->impl.pptr.key -= it->impl.pptr.ksize * num_retreat;
483 it->impl.pptr.val -= it->impl.pptr.vsize * num_retreat;
484 break;
485
486 case STDARR_IT_ID:
487 stdarr_it_retreat(it, num_retreat);
488 break;
489
490 case STDCARR_IT_ID:
491 stdcarr_it_retreat(it, num_retreat);
492 break;
493
494 case STDDLL_IT_ID:
495 stddll_it_retreat(it, num_retreat);
496 break;
497
498 case STDHASH_IT_ID:
499 case STDHASH_IT_KEY_ID:
500 stdhash_it_retreat(it, num_retreat);
501 break;
502
503 case STDSKL_IT_ID:
504 case STDSKL_IT_KEY_ID:
505 stdskl_it_retreat(it, num_retreat);
506 break;
507
508 default:
509 STDEXCEPTION(uninitialized or corrupted iterator);
510 break;
511 }
512
513 return it;
514 }
515
516 /************************************************************************************************
517 * stdit_cmp: Compare two iterators for rank difference.
518 ***********************************************************************************************/
519
stdit_cmp(const stdit * it1,const stdit * it2)520 STDINLINE stdssize stdit_cmp(const stdit *it1, const stdit *it2)
521 {
522 stdssize ret;
523
524 STDSAFETY_CHECK(it1->type_id == it2->type_id);
525
526 switch (it1->type_id) {
527 case STDPTR_IT_ID:
528 STDSAFETY_CHECK(it1->impl.ptr.vsize == it2->impl.ptr.vsize);
529 ret = (it1->impl.ptr.val - it2->impl.ptr.val) / it1->impl.ptr.vsize;
530 break;
531
532 case STDPPTR_IT_ID:
533 STDSAFETY_CHECK(it1->impl.pptr.ksize == it2->impl.pptr.ksize && it1->impl.pptr.vsize == it2->impl.pptr.vsize);
534 ret = (it1->impl.pptr.key - it2->impl.pptr.key) / it1->impl.pptr.ksize;
535 STDSAFETY_CHECK(ret == (it1->impl.pptr.val - it2->impl.pptr.val) / it1->impl.pptr.vsize);
536 break;
537
538 case STDARR_IT_ID:
539 ret = stdarr_it_cmp(it1, it2);
540 break;
541
542 case STDCARR_IT_ID:
543 ret = stdcarr_it_cmp(it1, it2);
544 break;
545
546 case STDDLL_IT_ID:
547 case STDHASH_IT_ID:
548 case STDHASH_IT_KEY_ID:
549 case STDSKL_IT_ID:
550 case STDSKL_IT_KEY_ID:
551 ret = 0;
552 STDEXCEPTION(iterator type does not support stdit_cmp);
553 break;
554
555 default:
556 ret = 0;
557 STDEXCEPTION(uninitialized or corrupted iterator);
558 break;
559 }
560
561 return ret;
562 }
563
564 /************************************************************************************************
565 * stdit_offset: Advance an iterator towards "end" by 'offset' positions.
566 ***********************************************************************************************/
567
stdit_offset(stdit * it,stdssize offset)568 STDINLINE stdit *stdit_offset(stdit *it, stdssize offset)
569 {
570 switch (it->type_id) {
571 case STDPTR_IT_ID:
572 it->impl.ptr.val += it->impl.ptr.vsize * offset;
573 break;
574
575 case STDPPTR_IT_ID:
576 it->impl.pptr.key += it->impl.pptr.ksize * offset;
577 it->impl.pptr.val += it->impl.pptr.vsize * offset;
578 break;
579
580 case STDARR_IT_ID:
581 stdarr_it_offset(it, offset);
582 break;
583
584 case STDCARR_IT_ID:
585 stdcarr_it_offset(it, offset);
586 break;
587
588 case STDDLL_IT_ID:
589 case STDHASH_IT_ID:
590 case STDHASH_IT_KEY_ID:
591 case STDSKL_IT_ID:
592 case STDSKL_IT_KEY_ID:
593 STDEXCEPTION(iterator type does not support stdit_offset);
594 break;
595
596 default:
597 STDEXCEPTION(uninitialized or corrupted iterator);
598 break;
599 }
600
601 return it;
602 }
603
604 /************************************************************************************************
605 * stdit_ptr: Initialize a stdit from a pointer.
606 ***********************************************************************************************/
607
stdit_ptr(stdit * it,const void * val,stdsize vsize)608 STDINLINE stdit *stdit_ptr(stdit *it, const void * val, stdsize vsize)
609 {
610 it->impl.ptr.val = (char*) val;
611 it->impl.ptr.vsize = vsize;
612
613 it->type_id = STDPTR_IT_ID;
614
615 return it;
616 }
617
618 /************************************************************************************************
619 * stdit_pptr: Initialize a stdit from two parallel pointers.
620 ***********************************************************************************************/
621
stdit_pptr(stdit * it,const void * key,const void * val,stdsize ksize,stdsize vsize)622 STDINLINE stdit *stdit_pptr(stdit *it, const void *key, const void * val, stdsize ksize, stdsize vsize)
623 {
624 it->impl.pptr.key = (char*) key;
625 it->impl.pptr.ksize = ksize;
626
627 it->impl.pptr.val = (char*) val;
628 it->impl.pptr.vsize = vsize;
629
630 it->type_id = STDPPTR_IT_ID;
631
632 return it;
633 }
634
635 #ifdef __cplusplus
636 }
637 #endif
638