vnet/vnet/vcgn/index_list.c

   1 /*
   2  *------------------------------------------------------------------
   3  * index_list.c - vector-index-based lists. 64-bit pointers suck.
   4  *
   5  * Copyright (c) 2008-2009, 2011 Cisco and/or its affiliates.
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at:
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *------------------------------------------------------------------
  18  */
  19
  20 #include <stdio.h>
  21 #include <string.h>
  22 //#include <clib_lite.h>
  23 #include <vppinfra/vec.h>
  24 #include "index_list.h"
  25
  26 /*
  27  * index_slist_addhead
  28  *
  29  * args:  headp -- pointer to e.g. a hash bucket
  30  *       vector -- vector containing the list
  31  *       elsize -- size of an element in this vector
  32  *       offset -- offset in each vector element of this list thread
  33  * index_to_add -- index in the vector to add to the list
  34  *
  35  * Adds new items to the head of the list. Try not to screw up the args!
  36  */
  37 void index_slist_addhead (index_slist_t *headp,
  38                           u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
  39 {
  40     return (index_slist_addhead_inline(headp, vector, elsize, offset,
  41                                       index_to_add));
  42 }
  43
  44 /*
  45  * index_slist_remelem
  46  *
  47  * args:  headp -- pointer to e.g. a hash bucket
  48  *       vector -- vector containing the list
  49  *       elsize -- size of an element in this vector
  50  *       offset -- offset in each vector element of this list thread
  51  * index_to_del -- index in the vector to delete from the list
  52  *
  53  * Try not to screw up the args!
  54  */
  55
  56 int index_slist_remelem (index_slist_t *headp,
  57                          u8 *vector, u32 elsize, u32 offset,
  58                          u32 index_to_delete)
  59 {
  60     return (index_slist_remelem_inline(headp, vector, elsize, offset,
  61                                        index_to_delete));
  62 }
  63
  64
  65 /*
  66  * index_dlist_addtail
  67  *
  68  * Append the indicated vector element to the doubly-linked list
  69  * whose first element is pointed to by headp.
  70  *
  71  * args: head_index -- listhead vector element index.
  72  *       vector -- vector containing the list
  73  *       elsize -- size of an element in this vector
  74  *       offset -- offset in each vector element of this list thread
  75  * index_to_add -- index in the vector to add to the list
  76  *
  77  * Do not call this routine to create the listhead. Simply set
  78  * index_dlist->next = index_dlist->prev = index of item.
  79  *
  80  * Try not to screw up the args.
  81  */
  82
  83 void index_dlist_addtail (u32 head_index, u8 *vector, u32 elsize,
  84                           u32 offset, u32 index_to_add)
  85 {
  86     index_dlist_t *elp;
  87     index_dlist_t *elp_next;
  88     index_dlist_t *headp;
  89
  90     headp = (index_dlist_t *)(vector + offset + elsize*head_index);
  91     elp = (index_dlist_t *)(vector + offset + elsize*index_to_add);
  92     elp->next = index_to_add;
  93     elp->prev = index_to_add;
  94
  95     elp->next = headp->next;
  96     headp->next = index_to_add;
  97
  98     elp_next = (index_dlist_t *)(vector + offset + elsize*elp->next);
  99     elp->prev = elp_next->prev;
 100     elp_next->prev = index_to_add;
 101 }
 102
 103 u32 index_dlist_remelem (u32 head_index,
 104                          u8 *vector, u32 elsize, u32 offset,
 105                          u32 index_to_delete)
 106 {
 107     u32 rv = head_index;
 108     index_dlist_t *headp, *elp, *elp_next;
 109
 110     elp = (index_dlist_t *)(vector + offset + elsize*index_to_delete);
 111
 112     /* Deleting the head index? */
 113     if (PREDICT_FALSE(head_index == index_to_delete)) {
 114         rv = elp->next;
 115         /* The only element on the list? */
 116         if (PREDICT_FALSE(rv == head_index))
 117             rv = EMPTY;
 118     }
 119
 120     headp = (index_dlist_t *)(vector + offset + elsize*elp->prev);
 121     headp->next = elp->next;
 122     elp_next = (index_dlist_t *)(vector + offset + elsize*elp->next);
 123     elp_next->prev = elp->prev;
 124
 125     elp->next = elp->prev = EMPTY;
 126
 127     return rv;
 128 }
 129
 130
 131 #ifdef TEST_CODE2
 132
 133 typedef struct tv_ {
 134     char junk[43];
 135     index_dlist_t l;
 136 } tv_t;
 137
 138
 139 void index_list_test_cmd(int argc, unsigned long *argv)
 140 {
 141     int i, j;
 142     u32 head_index;
 143     index_dlist_t *headp;
 144     tv_t *tp=0;
 145
 146     vec_validate(tp, 3);
 147     head_index = 3;
 148
 149     memset(tp, 0xa, sizeof(tp[0])*vec_len(tp));
 150
 151     /* Here's how to set up the head element... */
 152     headp = &((tp + head_index)->l);
 153     headp->next = headp->prev = head_index;
 154
 155     for (i = 0; i < 3; i++) {
 156         index_dlist_addtail(head_index, (u8 *)tp, sizeof(tp[0]),
 157                             STRUCT_OFFSET_OF(tv_t, l), i);
 158         printf("headp next %d prev %d\n",
 159                headp->next, headp->prev);
 160         for (j = 0; j <= 3; j++) {
 161             printf ("[%d]: next %d prev %d\n", j,
 162                     tp[j].l.next, tp[j].l.prev);
 163         }
 164         printf("---------------\n");
 165
 166     }
 167
 168     printf("After all adds:\n");
 169
 170     printf("headp next %d prev %d\n",
 171            headp->next, headp->prev);
 172
 173     for (j = 0; j <= 3; j++) {
 174         printf ("[%d]: next %d prev %d\n", j,
 175                 tp[j].l.next, tp[j].l.prev);
 176     }
 177     printf("---------------\n");
 178
 179     head_index = index_dlist_remelem (head_index, (u8 *)tp, sizeof(tp[0]),
 180                                       STRUCT_OFFSET_OF(tv_t, l), 1);
 181
 182     printf("after delete 1, head index %d\n", head_index);
 183     headp = &((tp + head_index)->l);
 184     printf("headp next %d prev %d\n",
 185            headp->next, headp->prev);
 186     for (j = 0; j <= 3; j++) {
 187         printf ("[%d]: next %d prev %d\n", j,
 188                 tp[j].l.next, tp[j].l.prev);
 189     }
 190     printf("---------------\n");
 191
 192     index_dlist_addtail(head_index, (u8 *)tp, sizeof(tp[0]),
 193                         STRUCT_OFFSET_OF(tv_t, l), 1);
 194
 195     printf("after re-add 1, head index %d\n", head_index);
 196     headp = &((tp + head_index)->l);
 197     printf("headp next %d prev %d\n",
 198            headp->next, headp->prev);
 199     for (j = 0; j <= 3; j++) {
 200         printf ("[%d]: next %d prev %d\n", j,
 201                 tp[j].l.next, tp[j].l.prev);
 202     }
 203     printf("---------------\n");
 204
 205     for (i = 3; i >= 0; i--) {
 206         head_index = index_dlist_remelem (head_index, (u8 *)tp, sizeof(tp[0]),
 207                             STRUCT_OFFSET_OF(tv_t, l), i);
 208         printf("after delete, head index %d\n", head_index);
 209         if (head_index != EMPTY) {
 210             headp = &((tp + head_index)->l);
 211             printf("headp next %d prev %d\n",
 212                    headp->next, headp->prev);
 213             for (j = 0; j <= 3; j++) {
 214                 printf ("[%d]: next %d prev %d\n", j,
 215                         tp[j].l.next, tp[j].l.prev);
 216             }
 217         } else {
 218             printf("empty list\n");
 219         }
 220         printf("---------------\n");
 221     }
 222 }
 223 #endif /* test code 2 */
 224
 225 #ifdef TEST_CODE
 226
 227 typedef struct tv_ {
 228     char junk[43];
 229     index_slist_t l;
 230 } tv_t;
 231
 232
 233 void index_list_test_cmd(int argc, unsigned long *argv)
 234 {
 235     int i, j;
 236     tv_t *tp = 0;
 237     index_slist_t *buckets = 0;
 238
 239     vec_add1((u32 *)buckets, EMPTY);
 240     vec_validate(tp, 9);
 241
 242     for (i = 0; i < 10; i++) {
 243         index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
 244                             STRUCT_OFFSET_OF(tv_t, l), i);
 245     }
 246
 247     printf ("after adds, buckets[0] = %u\n", buckets[0]);
 248
 249     for (j = 0; j < 10; j++) {
 250         printf("tp[%d] next %u\n", j, tp[j].l);
 251
 252     }
 253
 254     for (i = 0; i < 10; i++) {
 255         if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
 256                                 STRUCT_OFFSET_OF(tv_t, l), i))) {
 257             printf("OUCH: remelem failure at index %d\n", i);
 258         }
 259         if (PREDICT_FALSE(tp[i].l.next != EMPTY)) {
 260             printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
 261         }
 262     }
 263
 264     printf ("after deletes, buckets[0] = %x\n", buckets[0]);
 265
 266     for (i = 0; i < 10; i++) {
 267         index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
 268                             STRUCT_OFFSET_OF(tv_t, l), i);
 269     }
 270
 271     printf ("after adds, buckets[0] = %u\n", buckets[0]);
 272
 273     for (j = 0; j < 10; j++) {
 274         printf("tp[%d] next %u\n", j, tp[j].l);
 275
 276     }
 277
 278     for (i = 9; i >= 0; i--) {
 279         if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
 280                                 STRUCT_OFFSET_OF(tv_t, l), i))) {
 281             printf("OUCH: remelem failure at index %d\n", i);
 282         }
 283         if ((tp[i].l.next != EMPTY)) {
 284             printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
 285         }
 286     }
 287
 288     printf ("after deletes, buckets[0] = %x\n", buckets[0]);
 289
 290     printf("add evens, then odds...\n");
 291
 292     for (i = 0; i < 10; i += 2) {
 293         index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
 294                             STRUCT_OFFSET_OF(tv_t, l), i);
 295
 296         printf ("head = buckets[0].next = %d\n", buckets[0].next);
 297         for (j = 0; j < 10; j++) {
 298             printf("tp[%d] next %u\n", j, tp[j].l);
 299         }
 300         printf("-------------\n");
 301     }
 302
 303     for (i = 1; i < 10; i += 2) {
 304         index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
 305                             STRUCT_OFFSET_OF(tv_t, l), i);
 306
 307         printf ("head = buckets[0].next = %d\n", buckets[0].next);
 308         for (j = 0; j < 10; j++) {
 309             printf("tp[%d] next %u\n", j, tp[j].l);
 310         }
 311         printf("-------------\n");
 312     }
 313
 314     printf ("after adds, buckets[0] = %u\n", buckets[0]);
 315
 316     for (j = 0; j < 10; j++) {
 317         printf("tp[%d] next %u\n", j, tp[j].l);
 318
 319     }
 320
 321     for (i = 9; i >= 0; i--) {
 322         if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
 323                                 STRUCT_OFFSET_OF(tv_t, l), i))) {
 324             printf("OUCH: remelem failure at index %d\n", i);
 325         }
 326         if (PREDICT_FALSE(tp[i].l.next != EMPTY)) {
 327             printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
 328         }
 329     }
 330
 331     printf ("after deletes, buckets[0] = %x\n", buckets[0]);
 332
 333     vec_free(buckets);
 334     vec_free(tp);
 335 }
 336 #endif /* test code */