summaryrefslogtreecommitdiffstats
path: root/plugins/vcgn-plugin/vcgn/index_list.c
diff options
context:
space:
mode:
Diffstat (limited to 'plugins/vcgn-plugin/vcgn/index_list.c')
-rw-r--r--plugins/vcgn-plugin/vcgn/index_list.c336
1 files changed, 336 insertions, 0 deletions
diff --git a/plugins/vcgn-plugin/vcgn/index_list.c b/plugins/vcgn-plugin/vcgn/index_list.c
new file mode 100644
index 00000000000..ec1b83b0b30
--- /dev/null
+++ b/plugins/vcgn-plugin/vcgn/index_list.c
@@ -0,0 +1,336 @@
+/*
+ *------------------------------------------------------------------
+ * index_list.c - vector-index-based lists. 64-bit pointers suck.
+ *
+ * Copyright (c) 2008-2009, 2011 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *------------------------------------------------------------------
+ */
+
+#include <stdio.h>
+#include <string.h>
+//#include <clib_lite.h>
+#include <vppinfra/vec.h>
+#include "index_list.h"
+
+/*
+ * index_slist_addhead
+ *
+ * args: headp -- pointer to e.g. a hash bucket
+ * vector -- vector containing the list
+ * elsize -- size of an element in this vector
+ * offset -- offset in each vector element of this list thread
+ * index_to_add -- index in the vector to add to the list
+ *
+ * Adds new items to the head of the list. Try not to screw up the args!
+ */
+void index_slist_addhead (index_slist_t *headp,
+ u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
+{
+ return (index_slist_addhead_inline(headp, vector, elsize, offset,
+ index_to_add));
+}
+
+/*
+ * index_slist_remelem
+ *
+ * args: headp -- pointer to e.g. a hash bucket
+ * vector -- vector containing the list
+ * elsize -- size of an element in this vector
+ * offset -- offset in each vector element of this list thread
+ * index_to_del -- index in the vector to delete from the list
+ *
+ * Try not to screw up the args!
+ */
+
+int index_slist_remelem (index_slist_t *headp,
+ u8 *vector, u32 elsize, u32 offset,
+ u32 index_to_delete)
+{
+ return (index_slist_remelem_inline(headp, vector, elsize, offset,
+ index_to_delete));
+}
+
+
+/*
+ * index_dlist_addtail
+ *
+ * Append the indicated vector element to the doubly-linked list
+ * whose first element is pointed to by headp.
+ *
+ * args: head_index -- listhead vector element index.
+ * vector -- vector containing the list
+ * elsize -- size of an element in this vector
+ * offset -- offset in each vector element of this list thread
+ * index_to_add -- index in the vector to add to the list
+ *
+ * Do not call this routine to create the listhead. Simply set
+ * index_dlist->next = index_dlist->prev = index of item.
+ *
+ * Try not to screw up the args.
+ */
+
+void index_dlist_addtail (u32 head_index, u8 *vector, u32 elsize,
+ u32 offset, u32 index_to_add)
+{
+ index_dlist_t *elp;
+ index_dlist_t *elp_next;
+ index_dlist_t *headp;
+
+ headp = (index_dlist_t *)(vector + offset + elsize*head_index);
+ elp = (index_dlist_t *)(vector + offset + elsize*index_to_add);
+ elp->next = index_to_add;
+ elp->prev = index_to_add;
+
+ elp->next = headp->next;
+ headp->next = index_to_add;
+
+ elp_next = (index_dlist_t *)(vector + offset + elsize*elp->next);
+ elp->prev = elp_next->prev;
+ elp_next->prev = index_to_add;
+}
+
+u32 index_dlist_remelem (u32 head_index,
+ u8 *vector, u32 elsize, u32 offset,
+ u32 index_to_delete)
+{
+ u32 rv = head_index;
+ index_dlist_t *headp, *elp, *elp_next;
+
+ elp = (index_dlist_t *)(vector + offset + elsize*index_to_delete);
+
+ /* Deleting the head index? */
+ if (PREDICT_FALSE(head_index == index_to_delete)) {
+ rv = elp->next;
+ /* The only element on the list? */
+ if (PREDICT_FALSE(rv == head_index))
+ rv = EMPTY;
+ }
+
+ headp = (index_dlist_t *)(vector + offset + elsize*elp->prev);
+ headp->next = elp->next;
+ elp_next = (index_dlist_t *)(vector + offset + elsize*elp->next);
+ elp_next->prev = elp->prev;
+
+ elp->next = elp->prev = EMPTY;
+
+ return rv;
+}
+
+
+#ifdef TEST_CODE2
+
+typedef struct tv_ {
+ char junk[43];
+ index_dlist_t l;
+} tv_t;
+
+
+void index_list_test_cmd(int argc, unsigned long *argv)
+{
+ int i, j;
+ u32 head_index;
+ index_dlist_t *headp;
+ tv_t *tp=0;
+
+ vec_validate(tp, 3);
+ head_index = 3;
+
+ memset(tp, 0xa, sizeof(tp[0])*vec_len(tp));
+
+ /* Here's how to set up the head element... */
+ headp = &((tp + head_index)->l);
+ headp->next = headp->prev = head_index;
+
+ for (i = 0; i < 3; i++) {
+ index_dlist_addtail(head_index, (u8 *)tp, sizeof(tp[0]),
+ STRUCT_OFFSET_OF(tv_t, l), i);
+ printf("headp next %d prev %d\n",
+ headp->next, headp->prev);
+ for (j = 0; j <= 3; j++) {
+ printf ("[%d]: next %d prev %d\n", j,
+ tp[j].l.next, tp[j].l.prev);
+ }
+ printf("---------------\n");
+
+ }
+
+ printf("After all adds:\n");
+
+ printf("headp next %d prev %d\n",
+ headp->next, headp->prev);
+
+ for (j = 0; j <= 3; j++) {
+ printf ("[%d]: next %d prev %d\n", j,
+ tp[j].l.next, tp[j].l.prev);
+ }
+ printf("---------------\n");
+
+ head_index = index_dlist_remelem (head_index, (u8 *)tp, sizeof(tp[0]),
+ STRUCT_OFFSET_OF(tv_t, l), 1);
+
+ printf("after delete 1, head index %d\n", head_index);
+ headp = &((tp + head_index)->l);
+ printf("headp next %d prev %d\n",
+ headp->next, headp->prev);
+ for (j = 0; j <= 3; j++) {
+ printf ("[%d]: next %d prev %d\n", j,
+ tp[j].l.next, tp[j].l.prev);
+ }
+ printf("---------------\n");
+
+ index_dlist_addtail(head_index, (u8 *)tp, sizeof(tp[0]),
+ STRUCT_OFFSET_OF(tv_t, l), 1);
+
+ printf("after re-add 1, head index %d\n", head_index);
+ headp = &((tp + head_index)->l);
+ printf("headp next %d prev %d\n",
+ headp->next, headp->prev);
+ for (j = 0; j <= 3; j++) {
+ printf ("[%d]: next %d prev %d\n", j,
+ tp[j].l.next, tp[j].l.prev);
+ }
+ printf("---------------\n");
+
+ for (i = 3; i >= 0; i--) {
+ head_index = index_dlist_remelem (head_index, (u8 *)tp, sizeof(tp[0]),
+ STRUCT_OFFSET_OF(tv_t, l), i);
+ printf("after delete, head index %d\n", head_index);
+ if (head_index != EMPTY) {
+ headp = &((tp + head_index)->l);
+ printf("headp next %d prev %d\n",
+ headp->next, headp->prev);
+ for (j = 0; j <= 3; j++) {
+ printf ("[%d]: next %d prev %d\n", j,
+ tp[j].l.next, tp[j].l.prev);
+ }
+ } else {
+ printf("empty list\n");
+ }
+ printf("---------------\n");
+ }
+}
+#endif /* test code 2 */
+
+#ifdef TEST_CODE
+
+typedef struct tv_ {
+ char junk[43];
+ index_slist_t l;
+} tv_t;
+
+
+void index_list_test_cmd(int argc, unsigned long *argv)
+{
+ int i, j;
+ tv_t *tp = 0;
+ index_slist_t *buckets = 0;
+
+ vec_add1((u32 *)buckets, EMPTY);
+ vec_validate(tp, 9);
+
+ for (i = 0; i < 10; i++) {
+ index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i);
+ }
+
+ printf ("after adds, buckets[0] = %u\n", buckets[0]);
+
+ for (j = 0; j < 10; j++) {
+ printf("tp[%d] next %u\n", j, tp[j].l);
+
+ }
+
+ for (i = 0; i < 10; i++) {
+ if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i))) {
+ printf("OUCH: remelem failure at index %d\n", i);
+ }
+ if (PREDICT_FALSE(tp[i].l.next != EMPTY)) {
+ printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
+ }
+ }
+
+ printf ("after deletes, buckets[0] = %x\n", buckets[0]);
+
+ for (i = 0; i < 10; i++) {
+ index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i);
+ }
+
+ printf ("after adds, buckets[0] = %u\n", buckets[0]);
+
+ for (j = 0; j < 10; j++) {
+ printf("tp[%d] next %u\n", j, tp[j].l);
+
+ }
+
+ for (i = 9; i >= 0; i--) {
+ if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i))) {
+ printf("OUCH: remelem failure at index %d\n", i);
+ }
+ if ((tp[i].l.next != EMPTY)) {
+ printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
+ }
+ }
+
+ printf ("after deletes, buckets[0] = %x\n", buckets[0]);
+
+ printf("add evens, then odds...\n");
+
+ for (i = 0; i < 10; i += 2) {
+ index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i);
+
+ printf ("head = buckets[0].next = %d\n", buckets[0].next);
+ for (j = 0; j < 10; j++) {
+ printf("tp[%d] next %u\n", j, tp[j].l);
+ }
+ printf("-------------\n");
+ }
+
+ for (i = 1; i < 10; i += 2) {
+ index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i);
+
+ printf ("head = buckets[0].next = %d\n", buckets[0].next);
+ for (j = 0; j < 10; j++) {
+ printf("tp[%d] next %u\n", j, tp[j].l);
+ }
+ printf("-------------\n");
+ }
+
+ printf ("after adds, buckets[0] = %u\n", buckets[0]);
+
+ for (j = 0; j < 10; j++) {
+ printf("tp[%d] next %u\n", j, tp[j].l);
+
+ }
+
+ for (i = 9; i >= 0; i--) {
+ if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
+ STRUCT_OFFSET_OF(tv_t, l), i))) {
+ printf("OUCH: remelem failure at index %d\n", i);
+ }
+ if (PREDICT_FALSE(tp[i].l.next != EMPTY)) {
+ printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
+ }
+ }
+
+ printf ("after deletes, buckets[0] = %x\n", buckets[0]);
+
+ vec_free(buckets);
+ vec_free(tp);
+}
+#endif /* test code */