source: trunk/sys/libphoenix/iterator.c @ 382

Last change on this file since 382 was 1, checked in by alain, 7 years ago

First import

File size: 4.4 KB
Line 
1/* Copyright (c) 2007-2009, Stanford University
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 met:
6*     * Redistributions of source code must retain the above copyright
7*       notice, this list of conditions and the following disclaimer.
8*     * Redistributions in binary form must reproduce the above copyright
9*       notice, this list of conditions and the following disclaimer in the
10*       documentation and/or other materials provided with the distribution.
11*     * Neither the name of Stanford University nor the names of its
12*       contributors may be used to endorse or promote products derived from
13*       this software without specific prior written permission.
14*
15* THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
16* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18* DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE FOR ANY
19* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*/ 
26
27#include <assert.h>
28
29#include "iterator.h"
30#include "memory.h"
31
32#include <stdlib.h>
33
34typedef struct iterator_t iterator_t;
35
36int iter_init (iterator_t *itr, int num_lists)
37{
38    assert (itr);
39    assert (num_lists > 0);
40
41    itr->list_array = 
42        (keyvals_t **)mem_malloc (sizeof(keyvals_t *) * num_lists);
43
44    if (! itr->list_array) {
45        return -1;
46    }
47
48    itr->max_list = num_lists;
49    itr->next_insert_pos = 0;
50    itr->current_list = 0;
51    itr->current_index = 0;
52    itr->val = NULL;
53    itr->size = 0;
54
55    return 0;
56}
57
58void iter_reset (iterator_t *itr)
59{
60    assert (itr);
61
62    itr->next_insert_pos = 0;
63    itr->current_list = 0;
64    itr->current_index = 0;
65    itr->val = NULL;
66    itr->size = 0;
67}
68
69void iter_rewind (iterator_t *itr)
70{
71    assert (itr);
72
73    itr->current_list = 0;
74    itr->current_index = 0;
75    itr->val = itr->list_array[0]->vals;
76}
77
78void iter_finalize (iterator_t *itr)
79{
80    assert (itr);
81    assert (itr->list_array);
82
83    mem_free (itr->list_array);
84}
85
86int iter_add (iterator_t *itr, keyvals_t *list)
87{
88    assert (itr);
89    assert (list->len);
90
91    if (itr->next_insert_pos >= itr->max_list)
92    {
93        /* Iterator full. */
94        return -1;
95    }
96   
97    itr->list_array[itr->next_insert_pos] = list;
98
99    if (itr->next_insert_pos == 0)
100    {
101        itr->val = list->vals;
102    }
103    itr->next_insert_pos += 1;
104    itr->size += list->len;
105
106    return 0;
107}
108
109/* Returns 1 when element exists.
110   Returns 0 when endpoint reached. */
111int iter_next (iterator_t *itr, void **addr)
112{
113    assert (itr);
114
115    if (itr->current_index >= itr->val->next_insert_pos)
116    {
117        /* Should hop to a different chunk. */
118        if (itr->val->next_val)
119        {
120            /* Hop to next chunk on the same list. */
121            itr->val = itr->val->next_val;
122            itr->current_index = 0;
123
124            /* Prefetch next chunk on the same list. */
125            if (itr->val->next_val) {
126                __builtin_prefetch (itr->val->next_val->array, 0, 0);
127            }
128        }
129        else if (itr->current_list + 1 < itr->next_insert_pos)
130        {
131            /* Hop to the first block of next list. */
132            itr->current_list += 1;
133            itr->val = itr->list_array[itr->current_list]->vals;
134            itr->current_index = 0;
135
136            /* Prefetch next chunk on the same list. */
137            if (itr->val->next_val) {
138                __builtin_prefetch (itr->val->next_val->array, 0, 0);
139            }
140        }
141        else
142        {
143            /* Endpoint reached. */
144            *addr = NULL;
145            return 0;
146        }
147    }
148
149    *addr = itr->val->array[itr->current_index++];
150
151    return 1;
152}
153
154int iter_next_list (iterator_t *itr, keyvals_t **list)
155{
156    assert (itr);
157
158    if (itr->current_list >= itr->next_insert_pos)
159    {
160        *list = NULL;
161        return 0;
162    }
163
164    *list = itr->list_array[itr->current_list++];
165    return 1;
166}
167
168int iter_size (iterator_t *itr)
169{
170    assert (itr);
171
172    return itr->size;
173}
Note: See TracBrowser for help on using the repository browser.