cachesim/queues.c

   1
   2 //
   3 //  queues.c
   4 //
   5 //  Created by pete on 1/29/16.
   6 //  Copyright © 2016-2020 Pete. All rights reserved.
   7 //
   8
   9
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #define EXTERN extern
  13
  14 #include "types.h"
  15 #include "queues.h"
  16
  17
  18 /*
  19 simpleQueues 1.0v4 [May 3 2020]
  20         - changed the qBlock header to include an int64 key
  21         - added an insert blcok in order function
  22
  23
  24  // older:
  25
  26  1.0v0 January 16 2017
  27  - rebuild of old code with old testing harness and new names for the API
  28  - we no longer try to keep count of the elements in a queue
  29
  30  1.0v1
  31  - now #include types.h from the utilities project
  32  - now include utilities.c and .h to provide timenow()
  33
  34  1.0v2 [May 8 2017]
  35  - changed qAppendQTail and qAppendQHead to NOT free the Queue structure that's supplying the list
  36
  37  1.0v3 [April 7 2018]
  38  - changed Queue * qNewQs(uint64 count, char * name) to check for the existence of the malloc'd queues before initialising them
  39  */
  40
  41
  42 static char * name_and_version = "simpleQueues 1.0v4 [May 3 2020]";
  43
  44 // ---------------------- qNameAndVersion --------------
  45
  46 char * qNameAndVersion(void) {
  47     return name_and_version;
  48 }
  49
  50 // ------------------ qError ---------------
  51
  52 void qError(char * msg, char * s1, char * s2) {
  53         printf("\n\n==qERROR: %s %s %s\n", msg, s1 ? s1 : "", s2? s2: "");
  54 }
  55
  56 // ------------------ qCheckQ ------------------
  57
  58 uint32 qCheckQ(Queue * q) {
  59     // checks the specified queue for consistency
  60     uint32 errors = qCheckSlice("queue", q -> head, q -> tail);
  61     return errors;
  62 }
  63
  64
  65 // ------------------ qCheckSlice ------------------
  66
  67 uint32 qCheckSlice(char * msg, qBlock * b0, qBlock * b1) {
  68     // checks the specified slice of blocks for consistency
  69     // check forward
  70     qBlock * front, * back;
  71     uint32 fwd = 0, bwd = 0;
  72     uint32 errors  = 0;
  73     front = b0;
  74     back = b1;
  75     // check going from front arrives at back
  76     while (b0 && (b0 != back)) {
  77         b0 = b0 -> next;
  78         fwd++;
  79     }
  80     if (b0 != back) {
  81         printf("\n\terror in traversing %s forward from %p..%p", msg, front, back);
  82         errors++;
  83     }
  84
  85     // check going from back to front arrives at front
  86     b0 = back;
  87     while (b0 && (b0 != front)) {
  88         b0 = b0 -> prev;
  89         bwd++;
  90     }
  91
  92     if (b0 != front) {
  93         printf("\n\terror in traversing %s backward from %p..%p", msg, front, back);
  94         errors++;
  95     }
  96
  97     if (fwd != bwd) {
  98         printf("\n\tcount error in traversing %s from %p..%p; fwdcount=%d, bwdcount=%d", msg, front, back, fwd, bwd);
  99         errors++;
 100     }
 101     return errors;
 102 }
 103
 104 // ------------------ qCountQ ----------------------
 105
 106 uint64 qCountQ(Queue * q) {
 107     uint64 n = 0;
 108     qBlock * b, * t;
 109     b = q -> head;
 110     t = q -> tail;
 111     if (b && t) {
 112         while (b) {
 113             n++;
 114             b = b -> next;
 115         }
 116         return n;
 117     }
 118     else {
 119         return 0;
 120     }
 121 }
 122
 123 // ------------------ qSetQEmpty ----------------
 124
 125 void qSetQEmpty(Queue * q) {
 126         q -> head = NULL;
 127         q -> tail = NULL;
 128 }
 129
 130 // -------------------------- qInitQ --------------------------
 131
 132 void qInitQ(Queue * q, char * name, uint64 n) {
 133     // initialise created queue
 134     if (name) {
 135         int l = (int)strlen(name);
 136         q -> qname = malloc(l + 16);
 137         sprintf(q -> qname, "%s[%llu]", name, n);
 138     }
 139     else q -> qname = NULL;
 140
 141         qSetQEmpty(q);
 142
 143 //      q -> bt = btAny;
 144 }
 145
 146 //// --------------- qSetQType -------------
 147 //
 148 //void qSetQType(Queue * q, blockType bt) {
 149 //      q -> bt = bt;
 150 //      uint64 size = strlen(q -> qname) + strlen(btName(bt)) + 16;
 151 //      char * n = malloc(size);
 152 //      strcpy(n, q -> qname);
 153 //      strcat(n, "-'");
 154 //      strcat(n, btName(bt));
 155 //      strcat(n, "'");
 156 //      //printf("\nqSetQType: freeing '%s' and setting '%s'", q -> qname, n);
 157 //      free(q -> qname);
 158 //      q -> qname = n;
 159 //}
 160 //
 161 // -------------------------- qNewQ ---------------------------
 162
 163 Queue * qNewQ(char * name) {
 164     // create and initialise just one queue
 165     return qNewQs(1, name);
 166 }
 167
 168 // -------------------------- qNewQs -------------------------
 169
 170 Queue * qNewQs(uint64 count, char * name) {
 171     // creates and initialises an array of 'count' queues
 172     Queue * q;
 173     uint64 i;
 174     q = malloc(count * sizeof(Queue));
 175     if (q) {
 176         for (i = 0; i < count; i++) {
 177             qInitQ(&q[i], name, i);
 178         }
 179     }
 180     return q;
 181 }
 182
 183 // -------------------------- qKillQs ------------------------
 184
 185 void qKillQs(Queue * qs, uint64 count) {
 186     // kills the array of count queues at q
 187     free(qs);
 188 }
 189
 190 // ------------------------- qKillQEntries --------------------------
 191
 192 void qKillQEntries(Queue * q) {
 193     // removes and frees all entries on the specified queue
 194     // must ONLY be used when the blocks were malloc()'d
 195     // does not free any memory associated with the blocks
 196     qBlock * ptr;
 197     ptr = qGetBlock(q);
 198     while (ptr) {
 199         free(ptr);
 200         ptr = qGetBlock(q);
 201     }
 202 }
 203
 204 // --------------------------- AddQHead ---------------------------
 205
 206 void qAddQHead(Queue * q, qBlock * start, qBlock * end) {
 207     // adds the list of blocks to the head of q
 208     if (start && end) {
 209         start -> prev = NULL;
 210         end -> next = q -> head;
 211         if (q -> head) {
 212             // the queue is non-empty
 213             q -> head -> prev = end;
 214             q -> head = start;
 215         }
 216         else {
 217             // queue is empty
 218             q -> head = start;
 219             q -> tail = end;
 220         }
 221     }
 222 }
 223
 224 // ---------------------------- qAddQTail -------------------------
 225
 226 void qAddQTail(Queue * q, qBlock * start, qBlock * end) {
 227     // adds the list of blocks to the tail of q
 228     if (start && end) {
 229         end -> next = NULL;
 230         start -> prev = q -> tail;
 231         if (q -> head) {
 232             // the queue is non-empty
 233             q -> tail -> next = start;
 234             q -> tail = end;
 235         }
 236         else {
 237             // the queue is empty
 238             q -> head = start;
 239             q -> tail = end;
 240         }
 241
 242     }
 243 }
 244
 245 // --------------------------- qAppendQTail --------------------
 246
 247 void qAppendQTail(Queue * qd, Queue * qs) {
 248     // places all the elements of qs on the tail of qd
 249     qBlock * start, *end;
 250     start = qFirstBlock(qs);
 251     end = qLastBlock(qs);
 252
 253     qCutQ(qs, start, end);
 254     qAddQTail(qd, start, end);
 255 }
 256
 257 // --------------------------- qAppendQHead --------------------
 258
 259 void qAppendQHead(Queue * qd, Queue * qs) {
 260     // places all the elements of qs at the head of qd
 261     qBlock * start, *end;
 262     start = qFirstBlock(qs);
 263     end = qLastBlock(qs);
 264
 265     qCutQ(qs, start, end);
 266     qAddQHead(qd, start, end);
 267 }
 268
 269 // --------------------------- qCutQ -------------------------
 270
 271 void qCutQ(Queue * q, qBlock * start, qBlock * end) {
 272     // cuts the blocks start..end out of queue q
 273     if ((start == NULL) || (end == NULL)) {
 274         return;            // no action if no slice
 275     }
 276     if ((q -> head == start) && (q -> tail == end)) {
 277         // whole queue
 278         q -> head = NULL;
 279         q -> tail = NULL;
 280     }
 281     else if (q -> head == start) {
 282         // cut from start to some way down
 283         q -> head = end -> next;
 284         end -> next -> prev = NULL;
 285     }
 286     else if (q -> tail == end) {
 287         // cut from middle to end
 288         q -> tail = start -> prev;
 289         start -> prev -> next = NULL;
 290     }
 291     else {
 292         // cut from middle
 293         start -> prev -> next = end -> next;
 294         end -> next -> prev = start -> prev;
 295     }
 296 }
 297
 298 // --------------------------- qCutBlock -------------------------
 299
 300 void qCutBlock(Queue * q, qBlock * block) {
 301     // cuts the block 'block' out of queue q,
 302     if (block == NULL) return;
 303
 304     if ((q -> head == block) && (q -> tail == block)) {
 305         // whole queue
 306         q -> head = NULL;
 307         q -> tail = NULL;
 308     }
 309     else if (q -> head == block) {
 310         // remove first block
 311         q -> head = block -> next;
 312         block -> next -> prev = NULL;
 313     }
 314     else if (q -> tail == block) {
 315         // cut last block
 316         q -> tail = block -> prev;
 317         block -> prev -> next = NULL;
 318     }
 319     else {
 320         // cut from middle
 321         block -> prev -> next = block -> next;
 322         block -> next -> prev = block -> prev;
 323     }
 324 }
 325
 326 // --------------------------- qAddBlock -------------------------
 327
 328 void qAddBlock(Queue * q, qBlock * block) {
 329     // add block to tail of queue
 330
 331 //      if (q -> bt != btAny) {
 332 //              if (q -> bt != block -> bt) {
 333 //                      qError("mismatched queue and block type", btName(q -> bt), btName(block -> bt));
 334 //              }
 335 //      }
 336     if (block) {
 337         block -> next = NULL;
 338         block -> prev = q -> tail;
 339         if (q -> head ) {
 340             // non-empty queue
 341             q -> tail -> next = block;
 342             q -> tail = block;
 343         }
 344         else {
 345             // empty queue
 346             q -> head = block;
 347             q -> tail = block;
 348         }
 349     }
 350 }
 351
 352 // --------------------------- qAddBlockBefore -------------------------
 353
 354 void qAddBlockBefore(Queue * q, qBlock * block, qBlock * here) {
 355     // add 'block' to queue immediately before block 'here'
 356     // if q is empty, make block the q
 357     // if 'here' is NULL, add to end
 358
 359     if (block == NULL) return;
 360     if (qFirstBlock(q) == NULL) {
 361         qAddBlock(q, block);
 362     }
 363     else if (here == NULL) {
 364         // didn't find anywhere; just add to tail
 365         qAddBlock(q, block);
 366     }
 367     else if (here -> prev == NULL) {
 368         // add to front
 369         qAddBlockHead(q, block);
 370     }
 371     else {
 372         // it's in the middle; chain in block after here->prev
 373         qAddBlockAfter(q, block, here->prev);
 374     }
 375 }
 376
 377 // --------------------------- qAddBlockBeforeHead -------------------------
 378
 379 void qAddBlockBeforeHead(Queue * q, qBlock * block, qBlock * here) {
 380     // add 'block' to queue immediately before block 'here'
 381     // if q is empty, make block the q
 382     // if 'here' is NULL, add to head
 383
 384     if (block == NULL) return;
 385     if (qFirstBlock(q) == NULL) {
 386         qAddBlock(q, block);
 387     }
 388     else if ((here == NULL) || (here -> prev == NULL)) {
 389         // add to front
 390         qAddBlockHead(q, block);
 391     }
 392     else {
 393         // it's in the middle; chain in block after here->prev
 394         qAddBlockAfter(q, block, here->prev);
 395     }
 396 }
 397
 398 // --------------------------- AddBlockAfter -------------------------
 399
 400 void qAddBlockAfter(Queue * q, qBlock * block, qBlock * here) {
 401     // add block to queue immediately after block here
 402
 403     if (block == NULL) return;
 404     if (qFirstBlock(q) == NULL) {
 405         // no queue: add to head
 406         qAddBlockHead(q, block);
 407     }
 408     else if ((here == NULL) || (here -> next == NULL)) {
 409         // no place to add, or 'here' is the tail of the queue, so add to tail
 410         qAddBlock(q, block);
 411     }
 412     else {
 413         // 'here' is in the middle; chain in block after here
 414         qBlock * next;
 415
 416         next = here -> next;
 417         block -> next = next;
 418         block -> prev = here;
 419         here -> next = block;
 420         next -> prev = block;
 421     }
 422 }
 423
 424 // --------------------------- qAddBlockAfterHead -------------------------
 425
 426 void qAddBlockAfterHead(Queue * q, qBlock * block, qBlock * here) {
 427     // add block to queue immediately after block here
 428     // add to front of queue if 'here' is NULL
 429
 430     if (block == NULL) return;
 431     if ((qFirstBlock(q) == NULL) || (here == NULL)) {
 432         // no queue: add to head
 433         qAddBlockHead(q, block);
 434     }
 435     else if (here == q -> tail) {
 436         // add to tail in normal manner
 437         qAddBlock(q, block);
 438     }
 439     else {
 440         // 'here' is in the middle; chain in block after here
 441         qBlock * next;
 442
 443         next = here -> next;
 444         block -> next = next;
 445         block -> prev = here;
 446         here -> next = block;
 447         next -> prev = block;
 448     }
 449 }
 450
 451 void printSymQ(char * msg, void * st, Queue * q);
 452
 453 // --------------------------- qAddBlockHead -------------------------
 454
 455 void qAddBlockHead(Queue * q, qBlock * block) {
 456
 457         // there's something wrong with this
 458
 459     // add block to FRONT of queue
 460     if (block == NULL) return;
 461
 462         qBlock * head = qFirst(q);
 463
 464      if (head) {
 465         // non-empty queue. point old head at new block. don't touch tail.
 466         head -> prev = block;
 467                 // point new block at old head
 468                 block -> next = head;
 469                  // make it have no prevs
 470                 block -> prev = NULL;
 471                 // set block as the head.
 472         q -> head = block;
 473     }
 474     else {
 475         // empty queue
 476         q -> head = block;
 477         q -> tail = block;
 478     }
 479 }
 480
 481 // ----------------------- qGetBlockTail ----------------
 482
 483 qBlock * qGetBlockTail(Queue * q) {
 484         // gets the tail of the queue
 485         qBlock * block = q -> tail;
 486         qCutBlock(q, block);
 487         return block;
 488 }
 489 // ---------------------------- qGetBlock ----------------------
 490
 491 qBlock * qGetBlock(Queue * q) {
 492     // removes the first block on 'q' and returns it
 493     qBlock * block;
 494
 495     block = q -> head;
 496
 497     if (block) {
 498         // non-empty queue
 499         if (q -> tail == block) {
 500             // just one in queue; empty the queue
 501             qSetQEmpty(q);                    // empty the queue
 502         }
 503         else {
 504             q -> head = block -> next;        // move head
 505             block -> next -> prev = NULL;    // mark new head
 506         }
 507     }
 508     return block;
 509 }
 510
 511 // -------------------------- qPushBlock ----------------------
 512
 513 void qPushBlock(Queue * q,qBlock * block) {
 514     // push and pop run a queue as a stack; push puts block on front of queue
 515     qAddBlockHead(q, block);
 516 }
 517
 518 // -------------------------- qPushBlock ----------------------
 519
 520 qBlock * qPopBlock(Queue * q) {
 521     // push and pop run a queue as a stack; pop gets block from front of queue
 522     return qGetBlock(q);
 523 }
 524
 525 // --------------------------- qInitBlock ---------------------
 526
 527 void qInitBlock(qBlock * block) {
 528     // initialise block pointers to values which will surely trap if used
 529     block -> next = NULL;
 530     block -> prev = NULL;
 531 //      block -> bt = btAny;
 532 }
 533
 534
 535 //// ----------------- qSetBlockType ---------------
 536 //
 537 //void qSetBlockType(qBlock * b, blockType bt) {
 538 //      b -> bt = bt;
 539 //}
 540 //
 541 // --------------------------- qNewBlock -----------------------
 542
 543 void * qNewBlock(uint32 size) {
 544     // creates and initialises a new block of the desired size
 545     qBlock * block = malloc(size);
 546     if (block) qInitBlock(block);
 547     return block;
 548 }
 549
 550 // ------------- qInsertKeyBlockInOrder --------------
 551
 552 void qInsertBlockInOrder(Queue * q, qBlock * block) {
 553         // q is a key-ordered queue of qKeyBlocks
 554         // it is not in any queue (pointers are NULL)
 555         // run down the queue looking for the insertion point, which is
 556         // in front of the first block with the same or later time
 557
 558 //      if (block -> key < 300) printf("\n--qInsertKeyBlockInOrder: block %p time %lld", block, block -> key);
 559         qBlock * here = qFirst(q);
 560         while (here) {
 561 //              if (block -> key < 300) printf("\n\tchecking block %p at time %lld", here, here -> key);
 562                 if (here -> key >= block -> key) break;
 563                 here = qNext(here);
 564         }
 565
 566         if (here) {
 567                 // insert before here
 568 //              if (block -> key < 300) printf("\n\t.. insert before block %p key %lld", here, here -> key);
 569                 qAddBlockBefore(q, block, here);
 570         }
 571         else {
 572                 qAddBlock(q, block);
 573 //              if (block -> key < 300) printf("\t.. add to tail");
 574         }
 575 }
 576
 577 // ------------- qPrintKeyQ ---------------
 578
 579 void qPrintKeyQ(Queue * q) {
 580         printf("\nKey Queue %p '%s'", q, q -> qname);
 581         qBlock * b = qFirst(q);
 582         while (b) {
 583                 printf("\n\tblock %p has key %lld", b, b -> key);
 584                 b = qNext(b);
 585         }
 586 }